Product rules in Combinatorics: Why do we multiply and not add or divide?

For each letter of the three letter word, there are two choices, A or B. Hence there are $2^3=2\cdot 2\cdot 2$ choices.


First letter may be A or B, so we have 2 options: enter image description here For each of those 2 options (1st letter A, 1st letter B) we have 2 options for the second letter, namely A or B: enter image description here

So we now have 2 * 2 = 4 options for the first 2 letters, namely AA, AB, BA, BB:enter image description here

And for each of those 2 * 2 (i. e. 4) options for the first 2 letters (AA, AB, BA, BB) we have 2 options for the third letter, namely A or B: enter image description here

So we finally have 2 * 2 * 2 options: AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB: enter image description here


For the first 2 letters we obtain a square 2 x 2, so there are 4 options:

     A    B   
   ┼────┼────┤
 A │ AB │ BB │
   ┼────┼────┤
 B │ BA │ BB │
   ┴────┴────┘

Now we can append either A as the 3rd letter:

      A      B   
   ┼─────┼─────┤
 A │ ABA │ BBA │
   ┼─────┼─────┤
 B │ BAA │ BBA │
   ┴─────┴─────┘

or B as the 3rd letter:

      A      B   
   ┼─────┼─────┤
 A │ ABB │ BBB │
   ┼─────┼─────┤
 B │ BAB │ BBB │
   ┴─────┴─────┘

You may imagine those two 3-letters squares as two layers of the resulting cube, volume of it will be 2.2.2 = 8.

Tags:

Combinatorics

Related

Combinatorial proof of $\sum_{k=1}^n k^2 =\binom{n+1}{3} + \binom{n+2}{3}$ Determine a valid substitution for a differential equation Is the proof of Pythagorean theorem using dot (inner) product circular? Upper bound on expected norm of subgaussian random matrix $ \mu(|f|\geq \alpha) = \frac{1}{\alpha} ||f||_1$ Application of Schwarz lemma and Liouville's theorem Proof by induction with square root in denominator: $\frac1{2\sqrt1}+\frac1{3\sqrt2}+\dots+ \frac1{(n+1)\sqrt n} < 2-\frac2{\sqrt{(n+1)}}$ Methods of making mathematical discovery Looking for where I went wrong: Finding the volume of a solid that lies within both a cylinder and sphere Is it true that $\int_0^1 \big(K(k^{1/2})\big)^2\,dk = \frac{7}2\zeta(3)$? How to solve ode of the form $ a_n(y')^n + a_{n-1}(y')^{n-1} + \cdots + a_1 y' + a_0 =0 $ Permute columns by pre-multiplying and rows by post-multiplying?

Recent Posts