Vaša košarica je prazna
Binomial coefficients, combination with repetition
We learnt about the square and the cube of binomial sums in algebra. Let us examine them more general.
Example 1
Let us observe the coefficients of the terms in the powers of a binomial sum. What can we say?
Solution
We might realise that the coefficients of the terms in the powers of a binomial sum are the numbers from the corresponding rows of the Pascal's triangle.
the powers of a binomial sum
Pascal’s triangle
\latex{\left(a+b\right)^0=\color{red}{1}}
\latex{\left(a+b\right)^1={\color{red}{1}}\times a + {\color{red}{1}}\times b}
\latex{\left(a+b\right)^2={\color{red}{1}}\times a^2 + {\color{red}{2}} \times ab + {\color{red}{1}}\times b^2}
\latex{\left(a+b\right)^3={\color{red}{1}}\times a^3 + {\color{red}{3}} \times a^2b + {\color{red}{3}}\times ab^2+ {\color{red}{1}}\times b^3}
\latex{\left(a+b\right)^4={\color{red}{1}}\times a^4 + {\color{red}{4}} \times a^3b + {\color{red}{6}}\times a^2b^2+{\color{red}{4}}\times ab^3+ {\color{red}{1}}\times b^4}
\latex{1}
\latex{1\qquad1}
\latex{1\qquad2\qquad1}
\latex{1\qquad3\qquad3\qquad1}
\latex{1\qquad4\qquad6\qquad4\qquad1}
While performing the multiplication
\latex{\left(a+b\right)^4=\left(a+b\right)\times\left(a+b\right)\times\left(a+b\right)\times\left(a+b\right)}
a term is obtained by choosing either \latex{a} or \latex{b} from each factor and then by multiplying them together. Thus the sum of the exponents of \latex{a} and \latex{b} is \latex{4} in every term, and the number of possibilities of choices gives the corresponding coefficient.
- \latex{a^4} is obtained if we choose \latex{a} out of \latex{4} factors, and we choose \latex{b} out of \latex{0} factors, and we multiply these together. It can be done in \latex{\binom{4}{0}= 1} different ways.
- \latex{a^3b} is obtained if we choose \latex{a} out of \latex{3} factors, and we choose \latex{b} out of \latex{1} factor; it can be done in \latex{\binom{4}{1}= 4} different ways.
- \latex{a^2b^2} is obtained if we choose \latex{a} out of \latex{2} factors, and we choose \latex{b} out of \latex{2} factors; it can be done in \latex{\binom{4}{2}= 6} different ways.
- \latex{ab^3} is obtained if we choose \latex{a} out of \latex{1} factor, and we choose \latex{b} out of \latex{3} factors; it can be done in \latex{\binom{4}{3}= 4} different ways.
- \latex{b^4} is obtained if we choose \latex{a} out of \latex{0} factors, and we choose \latex{b} out of \latex{4} factors; it can be done in \latex{\binom{4}{4}= 1} different ways.
Based on this
\latex{\left( a+ b \right)^4 = \binom{4}{0} \times a^4+\binom{4}{1} \times a^3b+\binom{4}{2}\times a^2b^2+\binom{4}{3}\times ab^3 + \binom{4}{4} \times b^4}.
The following holds in general too:
BINOMIAL THEOREM:
\latex{\left(a+b\right)^n=\binom{n}{0}\times a^n + \binom{n}{1}\times a^{n-1}b+\binom{n}{2}\times a^{n-2}b^2 + ... +}
\latex{+\binom{n}{k}\times a^{n-k}b^k+...+\binom{n}{n-1}\times ab^{n-1}+\binom{n}{n}\times b^n}.
Proof
Let us express \latex{\left(a + b\right)^n} as a product with \latex{n} factors:
\latex{{{\scriptsize }\atop{\left(a+b\right)^n=}}{{\scriptsize 1.}\atop{\left(a+b\right)\times}}{{\scriptsize 2.}\atop{\left(a+b\right)\times}}{{\scriptsize n-1.}\atop{\left(a+b\right)}}{{\scriptsize }\atop{\times\space...\space \times}}{{\scriptsize n.}\atop{\left(a+b\right)}.}}
While performing the multiplication a term is obtained by choosing either \latex{a} or \latex{b} from each factor and then by multiplying them together. Thus the sum of the exponents of \latex{a} and \latex{b} is \latex{n} in every term.
\latex{a^{n-k}b^k} is obtained if we choose \latex{a} out of \latex{n-k} factors, and we choose \latex{b} out of \latex{k} factors, and we multiply these together. It can be done in \latex{\binom{n}{k}} different ways, therefore it is going to be the coefficient of \latex{a^{n-k}b^k} in the sum form of the power.
The coefficients of the terms in the powers of a two-term (binomial) sum are called binomial coefficients, based on the word binom \latex{=} two-term.
Note: The binomial coefficients were applied to solve combinatorial exercises in connection with chess games in India in the \latex{2}nd century BC, and by the \latex{12}th century the binomial theorem was also known there.
Example 2
Let us calculate the sum in every row of the Pascal’s triangle, if
- we write \latex{+} signs everywhere between the numbers.
- we write \latex{-} and \latex{+} signs in turns between the numbers.
Let us explain the regularity.
Solution (a)
To justify the equality relating to the \latex{5}th row of part a) let us write down the binomial theorem for the case \latex{a = 1}, \latex{b = 1}, \latex{n = 5}:
\latex{\binom{5}{0}\times1^5+\binom{5}{1}\times 1^4 \times 1^1 + \binom{5}{2} \times 1^3 \times 1^2+\binom{5}{3}\times1^2 \times1^3 + \binom{5}{4}\times 1^1\times 1^4 + \binom{5}{5}\times1^5=}
\latex{=\left(1+1\right)^5=2^5}.
\latex{=2^0}
\latex{=2^1}
\latex{1+1}
\latex{1}
\latex{=2^2}
\latex{=2^3}
\latex{=2^4}
\latex{=2^5}
\latex{1+2+1}
\latex{1+3+3+1}
\latex{1+4+6+4+1}
\latex{1+5+10+10+5+1}
The sum is always
a power of \latex{2}.
Solution (b)
To justify the equality relating to the \latex{5}th row of part b) let us write down the binomial theorem for the case \latex{a = 1}, \latex{b = -1}, \latex{n = 5}:
\latex{\binom{5}{0}\times1^5+\binom{5}{1}\times 1^4 \times \left(-1\right)^1 + \binom{5}{2} \times 1^3 \times \left(-1\right)^2+\binom{5}{3}\times1^2 \times\left(-1\right)^3 +}
\latex{+\binom{5}{4}\times 1^1\times \left(-1\right)^4 + \binom{5}{5}\times\left(-1\right)^5=\binom{5}{0}-\binom{5}{1}+\binom{5}{2}-\binom{5}{3}+\binom{5}{4}-\binom{5}{5}}=
\latex{=0}
\latex{=0}
\latex{1-1}
\latex{1}
\latex{=0}
\latex{=0}
\latex{=0}
\latex{=0}
\latex{1-2+1}
\latex{1-3+3-1}
\latex{1-4+6-4+1}
\latex{1-5+10-10+5-1}
\latex{=\left(1-1\right)^5=0}.
With this method the regularity above can also be justified in general.
If we write down the binomial theorem for an arbitrary integer exponent \latex{n \geq 1} and for the case \latex{a=1} and \latex{b=1}, and then for the case \latex{a = 1} and \latex{b = -1}, the following theorem relating to the binomial coefficients is obtained:
THEOREM: For every whole number \latex{n\geq1}:
\latex{\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n-1}+\binom{n}{n}=\left(1+1\right)^n=2^n},
\latex{\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-...+\left(-1\right)^{n-1}\times\binom{n}{n-1}+\left(-1\right)^n \times \binom{n}{n}=\left(1-1\right)^4=0}.
Example 3
- How many subsets with \latex{3} elements does a set with \latex{5} elements have?
- How many subsets does a set with \latex{5} elements have?
- How many subsets does a set with \latex{n} elements have?
We use the fact that the order of the elements in a set does not matter.
Solution (a)
\latex{3} elements need to be chosen out of the \latex{5} elements of the set for the subset so that the order of choices of the elements does not matter; it can be done in \latex{\binom{5}{3}=10} different ways. So a set with \latex{5} elements has \latex{\binom{5}{3}=10} subsets with \latex{3} elements.
Solution (b)
Method I
The number of the subsets of a set with \latex{5} elements is equal to the total number of its subsets with \latex{0;\, 1;\, 2;\, 3;\, 4} or \latex{5} elements.
- There is \latex{\binom{5}{0}=1} subset with \latex{0} elements; it is the empty set.
- There are \latex{\binom{5}{1}=5} subsets with \latex{1} element; one element can be chosen in \latex{5} different ways.
- The number of the subsets with \latex{2} elements is equal to the number of the subsets with \latex{3} elements, \latex{\binom{5}{2}=\binom{5}{3}=10}.
- The number of the subsets with \latex{4} elements is as many in as many ways we can choose \latex{4} elements or in as many ways we can omit one element: \latex{\binom{5}{4} = \binom{5}{1}=5}.
- There is \latex{\binom{5}{5}=1} subset with \latex{5} elements; it is the set itself.
Thus the total number of the subsets of a set with \latex{5} elements is:
\latex{\binom{5}{0}+\binom{5}{1}+\binom{5}{2}+\binom{5}{3}+\binom{5}{4}+\binom{5}{5}=1+5+10+10+5+1=32}.
Method II
The selection of a subset is performed so that we write \latex{+} signs below the elements chosen, and we write \latex{-} signs below the other elements. Thus we write either a \latex{+} or a \latex{-} sign below every element of the set.
For example the subsets of the set \latex{\lbrace a; b; c; d; e\rbrace} with \latex{5} elements can be written as follows:
- \latex{\lbrace a; c\rbrace\quad}corresponding to the sequence of signs \latex{+-+--},
- \latex{\lbrace c; d\rbrace\quad}corresponding to the sequence of signs \latex{--++-},
- \latex{\lbrace a; b; d; e\rbrace\quad}corresponding to the sequence of signs \latex{++-++}.
As there is a sequence of signs unambiguously belonging to every subset and there is a subset unambiguously belonging to every sequence of signs, the set has as many subsets in as many ways we can write the signs \latex{+} or \latex{-} below its elements.
As there is a sequence of signs unambiguously belonging to every subset and there is a subset unambiguously belonging to every sequence of signs, the set has as many subsets in as many ways we can write the signs \latex{+} or \latex{-} below its elements.
We can choose between two possibilities for every element, thus the number of the possible sequences of signs, i.e. the number of the subsets of the set with \latex{5} elements is: \latex{2^5 = 32}.
The same result should be obtained for the number of the subsets of a set with \latex{5} elements with both methods, therefore
\latex{\binom{5}{0}+\binom{5}{1}+\binom{5}{2}+\binom{5}{3}+\binom{5}{4}+\binom{5}{5}=2^5}.
Solution (c)
Method I
The set with \latex{n} elements has as many subsets with \latex{k} elements in as many ways we can choose \latex{k} elements out of \latex{n} elements regardless of the order; it is \latex{\binom{n}{k}}.
The number of the subsets of the set with n elements is as many as the total number of the subsets with \latex{0;\, 1;\, 2;\, …;\, n – 1} or \latex{n} elements; it is
\latex{\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n-1}+\binom{n}{n}}.
Method I
When choosing a subset of the set with \latex{n} elements we either choose (write a \latex{+} sign below) or not choose (write a \latex{-} sign below) every single element. As there is a sequence of signs unambiguously belonging to every subset and there is a subset unambiguously belonging to every sequence of signs, the set has as many subsets in as many ways we can write the signs \latex{+} or \latex{-} below its elements. We can choose between two possibilities for every element, thus the number of the possible sequences of signs, i.e. the number of the subsets of the set with \latex{n} elements is: \latex{2^n}.
The same result should be obtained for the number of the subsets of a set with \latex{n} elements with both methods, therefore
\latex{\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n-1}+\binom{n}{n}=2^n},
thus we managed to prove the previous theorem also with combinatorial considerations.
We have also justified the following:
THEOREM: For every natural number \latex{n} the number of the subsets of a set with \latex{n} elements is:
\latex{\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n-1}+\binom{n}{n}=2^n}.
Combination with repetition
Example 4
There is a sale for five different plant types in a gardening catalogue: petunia, pelargonium, rose, delphinium, lavender. Esther orders \latex{12} plants. In how many different ways can she do it if she can order more than one piece of each plant type?
Solution
A possible order is represented in the table: the number of the \latex{ + } signs denotes the number of plants she ordered from each type. With the alike \latex{ + } signs we can assure that the order of ordering the plants does not matter, the only important thing is the number of \latex{ + } signs in each row.
pelargonium
petunia
rose
delphinium
lavender
flower
pieces
\latex{++++}
\latex{++++++}
\latex{++}
By leaving away the table this notation is still possible, if we write \latex{4} \latex{|} separator signs between the \latex{12} \latex{+} signs to separate the plant types. The order represented in the table can be written in the form
\latex{|++++|\space|++++++|++}
with this method.
The separator sign at the beginning (or at the end) of the sequence of signs means that she did not order from the first (last) plant type. The number of the \latex{+} signs between two separator signs means that she ordered that many pieces from the corresponding plant type. If there are two separator signs next to each other, then she did not order from that plant type.
Every order can unambiguously be described with such sequence of signs, and there is an order unambiguously corresponding to every sequence of signs. So the number of possible orders is as many in as many ways the \latex{12} \latex{+} signs and the \latex{4} \latex{|} separator signs can be arranged.
All the possible arrangements of the \latex{12 + 4 = 16} signs, if there are \latex{12} alike ones and \latex{4} alike ones among them, is:
\latex{\frac{16!}{12! \times 4!}=\frac{\left(12+5-1\right)!}{12! \times\left( 5-1\right)!}=\binom{12+5-1}{12}=1820}.
DEFINITION: If we choose \latex{n} elements out of \latex{k} different elements so that the order of choices does not matter and we can choose several ones out of each type, a \latex{k}-element combination with repetition of \latex{n} different elements is obtained.
THEOREM: The number of the \latex{k}-element combinations with repetition of \latex{n} different elements is:
\latex{\binom{k+n-1}{k}}.
By using the one-to-one correspondence applied in the example the number of the \latex{k}-element combinations with repetition of \latex{n} different elements is the same as all the possible arrangements of \latex{k} \latex{+} signs and \latex{n - 1} \latex{|} separator signs, i.e. it is
\latex{\frac{\left( k+n-1\right)!}{k! \times \left( n-1 \right)!}=\binom{k+n-1}{k}}.
Exercises
{{exercise_number}}. Give the following powers with the help of the binomial theorem:
- \latex{\left( x-2 \right)^5};
- \latex{\left( 3n+2 \right)^5};
- \latex{\left( y-1 \right)^{10}};
- \latex{\left( a-b \right)^n}.
{{exercise_number}}. Give the index form of the following sums:
- \latex{x^4-4x^3+6x^2-4x+1};
- \latex{a^5+10a^4+40a^3+80a^2+80a+32}.
{{exercise_number}}.
a) How many subsets does the set of players of a volleyball team being in the court at once (\latex{6} players) have?
b) How many subsets does the set of players in the court have Peter is in?
c) How many subsets does the set of players in the court have Peter is not in?
b) How many subsets does the set of players in the court have Peter is in?
c) How many subsets does the set of players in the court have Peter is not in?
{{exercise_number}}. Sue bought \latex{18} postcards in Paris, which she chose out of \latex{8} different card types. In how many different ways could she do it?
{{exercise_number}}. How many solutions does the equation \latex{x + y + z = 9} have
- on the set of natural numbers?
- on the set of positive whole numbers?
- on the set of whole numbers?