Combinatorics/Rule of product

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

Template:EquationNote. Illustration of 3!=6 using rule of product

Template:EquationNote. Should probably remove (see Information theory)

Tree diagrams

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

Template:EquationNoteillustrates a successful effort to establish that there are Template:Math way to order the three integers, $\{1,2,3\}.$ The counting starts with, Template:Math choices. But, since we assume that each integer is included one and only one time, the next step gives us only, Template:Math options. Finally there is only one choice left Template:Math after the first two integers are selected. Counting the items in the leftmost column of Template:EquationNote, we see that the number of of permutations of 123 is, Template:Math The number of permutations for Template:Math objects is Template:Math 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

Template:EquationRef Proof for combination using tree and rule product

The tree diagram of Template:EquationNoteshows 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. Template:EquationNoteis also chaotic, and much larger. But this tree-diagram can be used to solve for the general case. Before we show how Template:EquationNotecan do that, let us first carefully examine it.

First circle. Begin at the center, with $(\genfrac{}{}{0ex}{}{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 Template:Math-chose-Template:Math.

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

Template:Math.

Since there are 2 ways to add subscripts to the pair of Template:Maths, 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$

$(\genfrac{}{}{0ex}{}{11}{4})=330\text{ and }(\genfrac{}{}{0ex}{}{7}{1})=7$

$(\genfrac{}{}{0ex}{}{6}{2})=15\text{ and }(\genfrac{}{}{0ex}{}{4}{4})=1$