TABLE OF CONTENTS
・Permutation
・Combination
・Permutations with repetitions
・Binomial theorem/Multinomial theorem
Kaya
This time, I will explain permutations and combinations, which are concepts related to counting objects,
as well as their applications: the binomial theorem and the multinomial theorem. Let’s start with
permutations.
Permutation
\[ \text{Permutation}\]
Arranging \( r \) objects in a row, selected from \( n \) distinct objects, is called a
permutation of \( r \) objects from \( n \), and the total number of such arrangements is denoted
by \( _n \rm P _ \it r \).
The total number of permutations is given by the following formula:
\[ _n \rm P _ \it r \rm = \it n \rm( \it n \rm -1)( \it n \rm -2) \cdots ( \it n \rm - \it r \rm + 1) \]
This is easy to understand if you think about counting the number of ways to place \( n \) numbered balls
into \( r \) boxes from left to right.
When putting a ball into the leftmost box, you choose one ball from the \( n \) balls, giving \( n \)
possibilities.
When putting a ball into the second box from the left, you choose one ball from the remaining \( n-1 \)
balls, giving \( n-1 \) possibilities.
Continuing in the same way, the above formula is obtained.
Note that we use multiplication rather than addition because, for each choice of a ball placed in one box,
there are corresponding choices for the ball placed in the next box.
For example, when \( n = 3 \) and \( r = 2 \),
\[ {}_3 \mathrm{P}_2 = 3 \times 2 = 6 \]
possible arrangements, as shown in the diagram below.
Such a diagram is called a tree diagram.
Nayumi
A tree diagram, huh. Now that you mention it, it really does look like tree branches spreading out.
Kaya
Right. And the total number of permutations can be written more simply using factorials.
Factorial is the product of all natural numbers less than or equal to a given natural number.
That is, the factorial of \( n \), written \( n! \), is expressed by the following formula.
\[ n! = n(n-1)(n-2) \cdots 3 \cdot 2 \cdot 1 \]
Nayumi
So the exclamation mark is the symbol for factorial! That’s kind of funny!
Kaya
Yeah. And we define \( 0! = 1 \).
Nayumi
Why?
Kaya
Because it makes things work out nicely in many situations—for example, like this.
\[ \begin{align}
3! &= 3 \cdot 2 \cdot 1 \\\\
2! &= 2 \cdot 1 = \frac{3!}{3} \\\\
1! &= 1 = \frac{2!}{2} \\\\
0! &= 1 = \frac{1!}{1}
\end{align}\]
To make the relation
\[ n! = \frac{(n+1)!}{n+1} \]
hold even for \( n=0 \), it is convenient to define \( 0! = 1 \).
Using factorials, the formula for the total number of permutations can be written as follows.
\[ \begin{align}
_n \rm P _ \it r &= \it n \rm( \it n \rm -1)( \it n \rm -2) \cdots ( \it n \rm - \it r \rm + 1) \\\\
&= \frac{\it n \rm( \it n \rm -1)( \it n \rm -2) \cdots 1}{\rm ( \it n-r \rm ) \rm( \it n-r \rm -1) \rm
( \it n-r \rm -2) \cdots 1} \\\\
&= \frac{\it n \rm !}{\rm \left( \it n \rm - \it r \rm \right) !}
\end{align}\]
Nayumi
When you simplify the second line, it turns into the first line.
Kaya
Right. Now let’s move on to combinations.
Combination
Nayumi
Combinations… combinations?
Kaya
Well, yes—but let’s write down the definition.
\[ \text{Combination}\]
The number of combination of \( n \) objects taken \( r \) at a time is denoted by \( _n \rm C
\it _r \).
Nayumi
This is a situation where students are randomly assigned to seats, and then groups of four are formed
based on nearby seats.
Kaya
In that case, if there are 40 students in the class, the total number of possible combinations for the
three people who end up in the same group as me would be \( _{39} \rm C _3 \).
Nayumi
We’re choosing three people from the remaining 39 students, excluding myself. So how do we calculate the
total number of such combinations?
A permutation is an arrangement in a line of \( r \) objects chosen from \( n \) distinct objects.
A combination can be thought of as removing the operation “arranging in a line” from a permutation.
Therefore, the formula for the total number of combinations is obtained by dividing the formula for the
total number of permutations by “the number of ways to arrange \( r \) objects in a line.”
The “number of ways to arrange \( r \) objects in a line” can also be described as “the total number of permutations obtained by choosing all \( r \) objects from \( r \) distinct objects.” Hence, \[ {}_r \mathrm{P}_r = \frac{r!}{(r - r)!} = \frac{r!}{0!} = r! \] Therefore, the formula for the total number of combinations is given by the following expression.
The “number of ways to arrange \( r \) objects in a line” can also be described as “the total number of permutations obtained by choosing all \( r \) objects from \( r \) distinct objects.” Hence, \[ {}_r \mathrm{P}_r = \frac{r!}{(r - r)!} = \frac{r!}{0!} = r! \] Therefore, the formula for the total number of combinations is given by the following expression.
\[ \begin{align}
_n \rm C \it _r &= \frac{_n \rm P \it _r}{r!} \\\\
&= \frac{n!}{r!(n-r)!}
\end{align}\]
When actually doing calculations, it is easier to use the first-line expression
\[ \frac{{}_n \mathrm{P}_r}{r!} \]
because it involves fewer factorial computations.
Also, the number of combinations of choosing \( r \) objects from \( n \) objects is equal to the number of combinations of choosing \( n - r \) objects from \( n \) objects, so \[ _n \rm C \it _r \rm = {} \it _n \rm C \it _{n-r} \] holds. This is because once one side of a group is chosen, the other side is determined automatically.
Also, the number of combinations of choosing \( r \) objects from \( n \) objects is equal to the number of combinations of choosing \( n - r \) objects from \( n \) objects, so \[ _n \rm C \it _r \rm = {} \it _n \rm C \it _{n-r} \] holds. This is because once one side of a group is chosen, the other side is determined automatically.
Nayumi
“All right, let’s practice by actually computing the total number of possible groups in that class.
\[ _{39} \rm C _3 = \frac{39 \cdot 38 \cdot 37}{3 \cdot 2 \cdot 1} = 9139\]
Nayumi
So this group was chosen from among 9,139 possible combinations. If everyone in the group happens to be
close friends, it really does feel like a small miracle, doesn’t it?
Kaya
Calling it a miracle might be a bit much, but things like that probably don’t happen very often.
Nayumi
Just put it in a nice way.
Kaya
Fair enough. Next, let’s introduce permutations with repetitions.
Permutations with repetitions
Nayumi
So it means that among the balls being arranged in a permutation, some of them are identical.
Kaya
That’s right. In this case, we don’t distinguish between different orders of identical balls, so in the
same way that we obtained the number of combinations by dividing the number of permutations by the
number of orderings, we can think about it like this.
\[ \text{Permutations with repetitions} \]
If there are \( n \) objects consisting of \( m \) different types of characters, where the number of
occurrences of character \( L_i \) is \( n_i \), then the total number of ways to arrange them in a row
is given by:
\[ \frac{n!}{n_1 ! n_2 ! \cdots n_m !} \]
where
\[ n = \sum _{i=1} ^m n_i \]
Nayumi
This time you switched from balls to letters. By the way, that \( \sum \) symbol is new to me.
Kaya
\( \sum \) is the capital Greek letter ‘sigma.’ It’s called the summation symbol, and it’s used like
this.
\[ \text{Summation symbol} \ \sum \]
Let \( n \lt m \).
The sum of the terms of the sequence \( \{ a_k \} \) from \( a_n \) to \( a_m \) is represented as
\[ \sum _{k=n} ^m a_k\]
That is,
\[ \sum _{k=n} ^m a_k = a_n + a_{n+1} + \cdots + a_{m-1} + a_m .\]
The formula for the total number of combinations introduced earlier is equal to the formula for the total
number of arrangements of permutations with repetitions, in the case where two types of letters are
arranged.
\[ _n \rm C \it _r \rm = \frac{\it n \rm !}{\it r \rm ! \rm ( \it n \rm - \it r \rm )!}\]
\[ n = r + (n-r) \]
This is because choosing \( r \) objects from \( n \) distinct objects to form a group is equivalent to
preparing \( r \) copies of the symbol “○” and \( n - r \) copies of the symbol “×,” arranging them in a
row, and then selecting the objects corresponding to the positions where “○” appears.
If we take \( {}_9 \mathrm{C}_5 \) as an example, this can be illustrated as shown in the diagram below.
Nayumi
I see. That makes sense.
Kaya
All right, let’s finish by introducing the binomial theorem and the multinomial theorem.
Binomial theorem/Multinomial theorem
Nayumi
So we start with the binomial theorem?
Kaya
Yes. The binomial theorem goes like this.
\[ \text{Binomial theorem}\]
The following equation is called the binomial theorem.
\[ \left( a + b \right) ^n = \sum _{k=0} ^{n} {}_{n} \rm C \it _{k} a^{n-k} b^{k} \ \ \rm \left( \it n
\rm = 1, 2, \ldots \right) \]
The coefficients \( {}_{n} \rm C \it _{k} \) are called binomial coefficients.
Nayumi
Hmm, it’s nicely compact, but just looking at this, I don’t really get it.
Kaya
That’s fair. Let’s look at a concrete example—say, the case where \( n = 3 \).
\[ \begin{align}
(a+b)^3 &= (a+b)(a+b)(a+b) \\\\
&= (a^2 + 2ab + b^2)(a+b) \\\\
&= a^3 + a^2 b + 2a^2b + 2ab^2 +ab^2 + b^3 \\\\
&= a^3 + 3a^2b + 3ab^2 + b^3 \\\\
&= {}_3 \rm C _0 \it a \rm ^3 + {}_3 \rm C _1 \it a \rm ^2 \it b \rm + {}_3 \rm C _2 \it ab \rm ^2 +
{}_3 \rm C _3 \it b \rm ^3
\end{align}\]
Nayumi
Yeah, it does work out. But why does it?
Kaya
You can think of it as choosing either \( a \) or \( b \) from each pair of parentheses and multiplying
them together. Then the terms are grouped according to how many times \( b \) is chosen from the three
parentheses.
Since the order of multiplication does not matter, the terms are classified by how many times \( b \) is
multiplied.
Therefore, the number of parentheses from which \( b \) is chosen out of the three appears as the
coefficient.
Extending this idea to a general \( n \) gives the binomial theorem.
Nayumi
I understand it well now. Then what about the multinomial theorem?
Kaya
The multinomial theorem is the case where there are more than two terms inside the parentheses.
\[ \text{Multinomial theorem}\]
Let \( n \) be a natural number. The following equation is called the Multinomial Theorem:
\[ \left( a_1 + a_2 + \cdots + a_m \right) ^n = \sum _{p_i} \frac{n!}{n_1!n_2! \cdots n_m!} a_1
^{n_1} a_2 ^{n_2} \cdots a_m ^{n_m} \]
where \( p_i \) represents an ordered set of integers \( (n_1, n_2, \dots, n_m) \) satisfying \( n_1
\geq 0 \), \( n_2 \geq 0 \), …, \( n_m \geq 0 \), and \( \sum _{k=1} ^m n_k = n \). The summation on the
right-hand side extends over all such sets \( p_i \).
The coefficients of each term in the multinomial theorem are called multinomial coefficients.
Nayumi
It looks like a rather formidable formula, but basically it’s just using the idea of permutations with
repetitions, right?
Kaya
Exactly. The exponent of each \( a_i \) represents how many times \( a_i \) is chosen in the product of
the parentheses, and that’s why it appears in the denominator of the multinomial coefficient.
Nayumi
Right. The idea itself isn’t that hard, but actually carrying out the calculations looks tough.
Kaya
Probably so. It doesn’t seem like the kind of calculation you’d do by hand these days.
Nayumi
We should be grateful to computers.
Kaya
Indeed.
Reference：
[1] 宮西正宜 24 others, 高等学校 数学A 改訂版, 新興出版社啓林館, December 10, 2008
[2] 松坂和夫, 現代数学序説 ──集合と代数, 筑摩書房, December 6, 2017
Previous
Ep. 14
Set
Set
Next
Ep. 16
Probability
Probability