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

Simply speaking, my question is as such: why do we use multiplication? For instance, let's suppose I have two elements in set $$\{A,B\}$$ and want to know how many possible ways there are illustrating them as words with 3 letters, I know this is $$2*2*2=8$$ , $$\{AAA,AAB,ABB,...,BBB\}$$ but could someone explain why this works?

• Just think about two letter words with an $n$ letter alphabet. For each choice of the first letter there are $n$ choices for the second, hence the total is $\underbrace {n+\cdots +n}_{\text {n times}}=n^2$. And so on. – lulu Feb 15 '19 at 0:06
• i absolutely agree, but im asking weather there is proper proof for that or is it simply a fact ? – MathsGuys Feb 15 '19 at 0:06
• If you like, use my last comment to give an inductive proof. – lulu Feb 15 '19 at 0:07
• @lulu i know how to do it but i am asking for the theory behind it or whether there is a proof or is it simply a fact ? – MathsGuys Feb 15 '19 at 0:08
• @fleablood that was the answer i was looking for, thanks for that. not more than that, simply wanted to know the theory behind it, as in every textbook they had taken it simply for granted, as it actually is, but i just wanted to be sure. – MathsGuys Feb 15 '19 at 0:23

$$\newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)} \newcommand{\ive}[1]{\left[ #1 \right]}$$ I assume that you are looking for proofs of the following facts (specifically Theorem 3, but you will soon want the others too):

Theorem 1 (binary product principle, direct product version). Let $$A$$ and $$B$$ be two finite sets. Then, $$\abs{A \times B} = \abs{A} \cdot \abs{B}$$.

(Bear with me, the next ones are a bit complicated, but I will explain their meaning soon.)

Theorem 2 (binary product principle, path diagram version). Let $$W$$ and $$S$$ be finite sets, and let $$f : S \to W$$ be any map. Let $$b$$ be a nonnegative integer. Assume that for each $$w \in W$$, there are exactly $$b$$ many elements $$s \in S$$ satisfying $$f \tup{s} = w$$. Then, $$\abs{S} = \abs{W} \cdot b$$.

Theorem 3 ($$n$$-ary product principle, direct product version). Let $$A_1, A_2, \ldots, A_n$$ be $$n$$ finite sets. Then, $$\abs{A_1 \times A_2 \times \cdots \times A_n} = \abs{A_1} \cdot \abs{A_2} \cdot \cdots \cdot \abs{A_n}$$.

Theorem 4 ($$n$$-ary product principle, path diagram version). Let $$S_0, S_1, \ldots, S_n$$ be any $$n$$ finite sets. Let $$f_i : S_i \to S_{i-1}$$ be a map for each $$i \in \set{1, 2, \ldots, n}$$. Let $$b_1, b_2, \ldots, b_n$$ be nonnegative integers. Assume that for each $$i \in \set{1, 2, \ldots, n}$$ and each $$w \in S_{i-1}$$, there are exactly $$b_i$$ many elements $$s \in S_i$$ such that $$f_i \tup{s} = w$$. Then, $$\abs{S_n} = \abs{S_0} \cdot b_1 b_2 \cdots b_n$$.

Theorem 1 says that if you have two finite sets $$A$$ and $$B$$ of sizes $$a$$ and $$b$$, then there are $$ab$$ ways to choose an ordered pair $$\tup{x, y} \in A \times B$$. Theorem 3 is an analogous fact for $$n$$-tuples; this is what you are using in your example.

Theorems 2 and 4 represent a more complicated situation, when you are making multiple choices and the choices available at one point may depend on your previously made choices. For example, if we want to count all pairs $$\tup{x, y} \in \set{1,2,3,4,5}^2$$ satisfying $$x \neq y$$, then we can do this by first choosing $$x$$ (there are $$5$$ ways to do so), and then choosing $$y$$ (there are $$4$$ ways to do so, since we must avoid the value $$x$$). The result is $$5 \cdot 4$$, but this is not because we are looking at the size of a Cartesian product of a $$5$$-element set with a $$4$$-element set. Rather, we are looking at a large set $$S$$ consisting of all our pairs $$\tup{x, y}$$ satisfying $$x \neq y$$, and at a smaller set $$W = \set{1,2,3,4,5}$$ representing the choices available at the first step. We know that after choosing an $$x$$ at the first step, there are exactly $$4$$ valid choices for $$y$$. In other words, each $$x \in W$$ can be extended to a pair $$\tup{x, y} \in S$$ in exactly $$4$$ ways. In other words, for each $$w \in W$$, there are exactly $$4$$ elements $$s = \tup{x, y} \in S$$ satisfying $$x = w$$. In other words, if we define a map $$f : S \to W$$ by $$f\tup{\tup{x, y}} = x$$, then for each $$w \in W$$, there are exactly $$4$$ many elements $$s \in S$$ satisfying $$f \tup{s} = w$$. Thus, we are looking at the situation of Theorem 2 with $$b = 4$$. Hence the theorem yields $$\abs{S} = \abs{W} \cdot 4 = 5 \cdot 4$$, which is exactly what the informal idea of multiplying numbers of options suggests. The answer by @MarianD visualizes this sort of thinking nicely using "path diagrams"; that's why I called Theorem 2 the "path diagram version". Theorem 4 is, again, an analogue of Theorem 2 for multiple choices (where $$S_i$$ stands for the set of possible states after making the first $$i$$ choices, and $$b_i$$ stands for the number of possible options for the $$i$$-th choice). Note that I have thrown in an extra bit of generality in Theorem 4 by allowing the set $$S_0$$ to have more than one element (i.e., even for the initial state there may be several options).

Seeing that all of these claims are intuitively obvious once stated in the common tongue (and Bourbaki have never gotten around to publishing a Combinatoire tome), it is not surprising that almost no text explicitly proves them. The only exception is Nicholas Loehr's Bijective Combinatorics (2011), which proves Theorems 1 and 3 in Sections 1.2--1.3 and 1.6, and somehow avoids explicitly stating Theorems 2 and 4.

I don't have the time to write down full proofs of the above four theorems right now, but let me give some hints. First of all, Theorems 3 and 4 follow by induction (on $$n$$) from Theorems 1 and 2, respectively. Thus, it remains to prove the latter two theorems. Second, Theorem 1 follows from Theorem 2 (applied to $$S = A \times B$$ and $$W = A$$ and $$b = \abs{B}$$ and $$f = \tup{\text{the map A \times B \to A sending each \tup{x, y} to x}}$$). Thus, it remains to prove Theorem 2. The simplest -- to me -- way of doing so is by reducing it to the following fact:

Theorem 5 (sum splitting principle). Let $$W$$ and $$S$$ be sets, and let $$f : S \to W$$ be any map. Let $$a_s$$ be a number (e.g., integer) for each $$s \in S$$. Then, \begin{align} \sum_{s \in S} a_s = \sum_{w \in W} \sum_{\substack{s \in S; \\ f\tup{s} = w}} a_s . \end{align}

This is a basic property of finite sums, saying that you can split a finite sum up into a bunch of smaller sums, each of which combines the addends of the original sum with a certain value of $$f\tup{s}$$. For example, this is the principle behind rewriting $$1 + 2 + 3 + \cdots + 2n$$ as $$\tup{1 + 3 + 5 + \cdots + \tup{2n-1}} + \tup{2 + 4 + 6 + \cdots + 2n}$$ (here, $$S = \set{1,2,3,\ldots,2n}$$ and $$W = \set{0, 1}$$ and $$a_s = s$$, and $$f$$ is the map sending each integer $$s \in S$$ to its remainder upon division by $$2$$). Now, Theorem 5 is an algebraic statement and likely to actually be in Bourbaki; anyway it is also Theorem 2.127 in my Notes on the combinatorial fundamentals of algebra where I prove it in all detail. Once you accept Theorem 5, it is easy to prove Theorem 2:

Proof of Theorem 2. Theorem 5 (applied to $$a_s = 1$$) yields \begin{align} \sum_{s \in S} 1 = \sum_{w \in W} \sum_{\substack{s \in S; \\ f\tup{s} = w}} 1 = \sum_{w \in W} \sum_{s \in \set{t \in S \mid f\tup{t} = w}} 1. \label{darij1.pf.t2.1} \tag{1} \end{align} But each finite set $$P$$ satisfies $$\sum_{s \in P} 1 = \abs{P}$$. Hence, $$\sum_{s \in S} 1 = \abs{S}$$. For the same reason, each $$w \in W$$ satisfies $$\sum_{s \in \set{t \in S \mid f\tup{t} = w}} 1 = \abs{\set{t \in S \mid f\tup{t} = w}} = \abs{\set{s \in S \mid f\tup{s} = w}} = b$$ (by the assumption that there are exactly $$b$$ many elements $$s \in S$$ satisfying $$f\tup{s} = w$$). Thus, \eqref{darij1.pf.t2.1} rewrites as \begin{align} \abs{S} = \sum_{w \in W} b = \abs{W} \cdot b . \end{align} This proves Theorem 2. $$\blacksquare$$

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.

• I know, but is there a proper proof of that or is it simply because of reality of numbers and multiplication ? – MathsGuys Feb 15 '19 at 0:05
• Is there a proper proof that 3 bags of groceries each with 2 items is $3\times 2$ items? I suppose there could be with specific axioms and definitions but I'd say this is the "reality of numbers and multiplication". – fleablood Feb 15 '19 at 0:08
• thank you i was asking for that. – MathsGuys Feb 15 '19 at 0:09

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

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

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:

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

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.

What are you really doing to obtain all 3-letters words from the set $$S = \left\{A, B\right\}$$, is the Cartesian product

$$S \times S \times S$$

Its cardinal number (number of elements) is consequently

$$2\cdot2\cdot2 = 8$$

The product of two nonnegative integers is defined recursively as $$0\times b=0\hspace{2.7cm}\\ a\times b=b+(a-1)\times b$$ Let $$P(a,b)$$ be the number two letters words where they are $$a$$ possibilities for the first letter and $$b$$ for the second. You can show that $$P(a,b)$$ obeys the same recursion with the same base cases: $$P(0,b)=0\hspace{2.7cm}\\ P(a,b)=b+P(a-1,b)$$ Proof:

• If there are zero choices for the first letter, then there must be zero choices for the pair of letters.

• If $$x$$ is a particular choice for the first letter, then there are $$b$$ strings whose first letter is $$x$$, and there are $$P(a-1,b)$$ whose first letter is not $$x$$, as there are $$a-1$$ remaining possibilities for the first letter.

These two equation let you prove that $$P(a,b)=a\times b$$ by induction on $$a$$. You then use another induction argument to show that the number of words of $$k$$ letters where there are $$a_i$$ choices for the $$i^{th}$$ letter is $$a_1\times a_2\times \dots \times a_k$$.