Combinatorics/Rule of product

The rule of product^‡ is easy to state if one is counting choices or outcomes based on two choices:

If there are a ways of doing (or counting) something and b ways of doing or counting something else, then the total number of ways to count (or do) both thins is a·b.

Figure 1. Illustration of 3!=6 using rule of product

Figure 2. Should probably remove (see Information theory)

Tree diagrams

Question: Under what conditions can this rule be iterated, for example by concluding that there are a·b·c possible outcomes if we observe a options at the first step, followed by b, and then by c options.

Figure 1illustrates a successful effort to establish that there are 3!=6 way to order the three integers, $\{1,2,3\}.$ The counting starts with, a=3, choices. But, since we assume that each integer is included one and only one time, the next step gives us only, b=2, options. Finally there is only one choice left (c=1) after the first two integers are selected. Counting the items in the leftmost column of Figure 1, we see that the number of of permutations of 123 is, 3!=3·2·1=6. The number of permutations for n objects is n! EDIT THIS

It is not always this easy to apply the rule of product to a tree diagram. In the next section we illustrate this using two tree diagrams that model the same problem. The rule of product is not very useful in analyizing the simplest tree diagram. But a more complex tree diagram can be used to derive formulas involving combinations and multinomial????

Calculating 5-choose-3

Let, {R,R,C,C,C} , be a "bag" (or multiset) of letters. How many words can be created if all five letters are used?

Figure 3 Proof for combination using tree and rule product

The tree diagram of Figure 2shows that the answer is 10 (if you count the words in the left-most column.) Unfortunately the diagram is too chaotic to yield much insight to the general formula if more letters are involved. Figure 3is also chaotic, and much larger. But this tree-diagram can be used to solve for the general case. Before we show how Figure 3can do that, let us first carefully examine it.

First circle. Begin at the center, with ${\tbinom {5}{3}}$, which is the symbol for how many way three objects can be chosen from five distinguishable objects. The answer is obtained by counting the ten dotted lines leading from that symbol. The first circle documents all ten outcomes associated with 5-chose-3.

Second circle. Next, we count how many different words could be created if we declare the to Rs to be not identical. In other words, we count the words that can be created from the multiset,

{R₁,R₂,C,C,C} .

Since there are 2 ways to add subscripts to the pair of Rs, the rule of product informs us that this second circle contains twice as many outcomes.

Mississippi

${\frac {11!}{4!\cdot 7!}}\cdot {\frac {7!}{1!\cdot 6!}}\cdot {\frac {6!}{2!\cdot 4!}}\cdot {\frac {4!}{4!\cdot 0!}}=34650$

${\binom {11}{4}}=330\;{\text{ and }}{\binom {7}{1}}=7\;$

${\binom {6}{2}}=15\;{\text{ and }}{\binom {4}{4}}=1\;$