Intro:
I'm a sixth form student from an A-level background studying the national curriculum in Bangladesh. One of the topics covered in the syllabus are the aforementioned rules of counting. There are mostly theorems and definitions and proofs in the books. The examples that are there build up on these theorems but I don't understand all of the theorems to begin with.
I found a tree diagram in a Cambridge A level S1 book that explained the permutations of three letters ABC.
Now, from the tree diagram, I understand that for the first position we can have three letters and for the second position we are left with two letters and so on - meaning each of the three main branches have two sub-branches and each of the two sub-branches each have one branch. This shows that there are 3*2*1 arrangements. Extending this concept, they showed that for n unique objects there are n*(n-1)*(n-2)*...*3*2*1 permutations which is denoted by n!.
tl;dr
Can you explain the product rule in layman's terms? I don't understand the part about independence and dependence of events on which the rule being used depends. Please include examples which illustrate the concept. :(
A product in ordinary arithmetic is just a repeated sum: $3 \times 5 = 3 + 3 + 3 + 3 + 3$. The same goes for the product rule in combinatorics: it is just a repeated application of the sum rule.
I'm going to assume you're happy with the sum rule: this is the idea that if we're counting things (arrangements, outcomes, whatever) that fall under several non-overlapping cases, we count each case separately, then add them up.
The product rule happens when there are many non-overlapping cases that are counted in the exact same way. In that case, you're going to add them all up, and if there are $n$ cases and $k$ outcomes in each case, you're going to get $\underbrace{k + k + \dots + k}_n = nk$.
For example, suppose we want to count the number of permutations of the letters A,B,C,D. We split these up into $4$ cases: the case where A is first, the case where B is first, the case where C is first, and the case where D is first. Then we notice that each of these cases is identical: in each of them, we have three letters left over, and three slots to place them in. This is a problem you've already solved: there are $3\cdot2\cdot1 = 6$ permutations of A,B,C, so there are $6$ permutations of any three letters. If we have $4$ cases and $6$ permutations in each case, then there are $4 \cdot 6$ permutations in total.
A large part of the product rule is just becoming familiar enough with this idea that you do it on autopilot. If you want to know the number of $4$-letter sequences from the English alphabet, the argument above suggests that you
But once you become familiar with the pattern, you get to step 3 or so and realize "oh, this is just going to repeat like this" and jump straight to $26 \cdot 26\cdot 26 \cdot 26$. Once you become even more familiar with the pattern, you don't even have to think about this.
(The tree diagram you're mentioning is one way to describe cases, subcases, subsubcases, and so on, so it's another way to show the same thing I'm describing here.)
Finally, what's the deal with "independence"? This is just the "realize that each case is identical" step. If not every case is identical, then we need to handle the different cases separately, and can't use the product rule.
For example, suppose we're counting sequences of $4$ English letters where the letters are in ascending-or-equal order alphabetically: "GOOP" counts, since G goes before O and O goes before P, but "BOOK" doesn't, since O goes after K. Then we could start splitting up into cases based on the first letter, but quickly realize:
So this is an example where the product rule cannot be used, because the cases are not identical.