Your cart is empty
Combinations without repetition, Pascal’s triangle
Last time we chose a few elements out of different elements with respect to the order (arrangement); now let us see the same but without respect to the order this time.
Example 1
A pentathlon relay team consists of three athletes. If five athletes are preparing for the Olympic Games, then in how many different ways can the three athletes be chosen out of them for the relay team?
Solution I
The first athlete can be chosen in \latex{5} different ways, the second one in \latex{4} different ways, and the third one in \latex{3} different ways, thus the three athletes can be chosen in succession in \latex{5\times 4 \times 3=\frac{5!}{2!}=\frac{5!}{\left(5-3\right)!}=60} different ways. The same three athletes were chosen as many times in as many ways the three athletes can be arranged, it is \latex{3! = 6}. As the order of choices is irrelevant, the number of possibilities to choose the three team members is one sixth of the number of the previous cases, i.e. it is
\latex{\frac{5\times4\times3}{3\times2}=\frac{5!}{3!\times\left(5-3\right)!}=10}.
For the sake of easy writing we introduce a new notation for this:
\latex{\frac{5!}{3!\times\left(5-3\right)!}=\dbinom{5}{3} },
which is pronounced as \latex{5} choose \latex{3}.
In general, if \latex{n \geq k \geq 0} and these are integers, then \latex{n} choose \latex{k} is:
\latex{\dbinom{n}{k}=\frac{n!}{k!\times\left(n-k\right)!}}.
\latex{\dbinom{n}{k}=\frac{n!}{k!\times\left(n-k\right)!}}The three athletes taking part in the relay can also be determined by choosing the two, who do not take part in the relay.
As it can be done in \latex{\dbinom{5}{2}} different ways, and the results obtained in the two different ways need to be equal, therefore: \latex{\dbinom{5}{2}=\dbinom{5}{3}}.
Solution II
The picking can also be done by writing a + sign under the name, if the person is chosen, and a – sign, if the person is not chosen. As we choose three athletes for the relay, we write three + signs and two – signs under the names.
As there is a unique sequence of signs for every picking, and there is a unique picking for every sequence of signs, the number of pickings is the same in as many different ways we can write + or – signs under the names, i.e. in as many different ways the three + signs and the two – signs can be arranged. Thus the number of possibilities can be calculated based on the permutation with repetition: \latex{\frac{5!}{3!\times2!}}.
As there is a unique sequence of signs for every picking, and there is a unique picking for every sequence of signs, the number of pickings is the same in as many different ways we can write + or – signs under the names, i.e. in as many different ways the three + signs and the two – signs can be arranged. Thus the number of possibilities can be calculated based on the permutation with repetition: \latex{\frac{5!}{3!\times2!}}.
We can see that the same result is obtained with this way of thinking as previously.
In the example we had to choose \latex{3} people out of \latex{5} different people so that the order of choices did not matter.
In the example we had to choose \latex{3} people out of \latex{5} different people so that the order of choices did not matter.
DEFINITION: If we choose \latex{k} elements out of \latex{n} different elements without respect to the order (arrangement), a \latex{k}-element combination without repetition of \latex{n} different elements (\latex{0 \leq k \leq n} integers) is obtained.
THEOREM: The number of the \latex{k}-element combinations without repetition of \latex{n} different elements (\latex{0 \leq k \leq n} integers) is: \latex{\dbinom {n}{k}}.
Proof I
The number of possibilities to choose \latex{k} elements out of \latex{n} different elements with respect to the order is \latex{\frac{n!}{\left(n-k\right)! } }. It is \latex{k!} times the number of cases when the order of the \latex{k} elements chosen does not matter, thus the number of the combinations without repetition of the \latex{n} different elements is
\latex{\frac{n!}{\left(n-k\right)!\times k! }=\dbinom{n}{k}}.
The combinations without repetition could be originated in the variations without repetition.
It can also be seen from the proof that the k elements can be chosen in as many ways as the \latex{(n – k)} elements not chosen can be chosen.
It can also be seen from the proof that the k elements can be chosen in as many ways as the \latex{(n – k)} elements not chosen can be chosen.
Proof II
Let us assign + signs to the \latex{k} elements chosen out of the \latex{n} different elements, and let us assign – signs to the other \latex{(n – k)} elements. Thus we created a one-to-one correspondence between the picking of the \latex{k} elements irrespectively of the order and the arrangements of the \latex{k} + signs and the \latex{(n – k)} – signs. The number of the possible arrangements of the \latex{k} + signs and the \latex{(n – k)} – signs is:
\latex{\frac{n!}{k!\times\left(n-k\right)!}=\dbinom{n}{k}}.
In this proof the combinations without repetition could be originated in the permutations with repetition.
The proof of the following theorem can also be seen from the previous proof:
The proof of the following theorem can also be seen from the previous proof:
THEOREM: For arbitrary whole numbers \latex{0 \leq k \leq n}
\latex{\dbinom{n}{k}=\dbinom{n}{n-k}}.
Example 2
At most how many intersection points can \latex{6} straight lines have? And what about \latex{n} straight lines?
Solution I
Let us draw the straight lines one by one, and let us count the intersection points. (Figure 2)
- Two straight lines can have at most one intersection point.
- When drawing the third straight line the most possible intersection points are obtained, if the straight line intersects both already existing straight lines, thus the number of the intersection points is: \latex{1 + 2}.
- When drawing the fourth straight line the most possible intersection points are obtained, if it intersects all three already existing straight lines, it means \latex{3} new intersection points, so the total is: \latex{1 + 2 + 3}.
- In the same way when drawing the fifth straight line the number of the intersection points increases by \latex{4}, when drawing the sixth straight line it increases by \latex{5}, so the total number of intersection points is: \latex{1 + 2 + 3 + 4 + 5 = 15}.
- By continuing this process when drawing the \latex{n^{th}} straight line the most possible intersection points are obtained, if the straight line intersects all the \latex{n – 1} already existing straight lines, it means \latex{n – 1} new intersection points, so the total is:
Figure 2\latex{1 + 2 + 3 +\dots + (n – 1)}.
Solution II
Six straight lines have the most intersection points, if any two of them intersect each other. Therefore the number of intersection points is as many in as many ways two straight lines can be chosen out of \latex{6} so that the order of choices does not matter. It is:
\latex{\dbinom{6}{2}=\frac{6\times5}{2}=15}.
In the same way \latex{n} straight lines have the most intersection points, if any two of them intersect each other. Therefore the number of intersection points is as many in as many ways two straight lines can be chosen out of \latex{n} so that the order of choices does not matter. It is:
\latex{\dbinom{n}{2}=\frac{n\times(n-1)}{2}}.
It is worth thinking it over also without the formula: the first straight line can be chosen in \latex{n} different ways, the second one in \latex{(n – 1)} different ways, since the order of choosing the two straight lines does not matter, the number of possibilities is:
\latex{\frac{n\times(n-1)}{2}}.
The two solutions give the same result, therefore the following is true for every whole number \latex{n \geq 2}:
\latex{1+2+3+\dots+\left(n-1\right)=\frac{n \times\left(n-1\right)}{2}}.
So with this relation we can easily calculate the sum of the first \latex{n – 1} positive whole numbers.
\latex{1+2+3+\dots+\left(n-1\right)=\\=\frac{n \times\left(n-1\right)}{2}}Example 3
There are only one-way streets on the map in figure \latex{3}; at the junctions we can go only into the directions represented by the arrows. In how many different ways can we get from the point \latex{A} to the other points denoted by letters? (Two routes are different if any parts of them are different.)
Figure 3Solution I (with summation)
We apply the summation method we got familiar with in example \latex{1} of lesson \latex{1}; the solution can be followed in figure \latex{4}.
It can be seen that we can get to the points \latex{B,D,G,K,C,F,J,O} in 1 way. We can get to the point \latex{E} from \latex{B} and from \latex{C}, and 1 route lead to these points each, thus we can get to the point \latex{E} in \latex{2} different ways.
We can get to the point \latex{H} from the points \latex{D} and \latex{E}. \latex{1} route lead from \latex{A} to \latex{D}, thus there is \latex{1} route from \latex{A} to \latex{H} through \latex{D}. \latex{2} routes lead from \latex{A} to \latex{E}, thus there are \latex{2} routes from \latex{A} to \latex{H} through \latex{E}. So from \latex{A} to \latex{H} there are \latex{1+ 2 = \bold3} routes.
We can get to the point \latex{I} from the points \latex{E} and \latex{F}, similarly to the previous one \latex{2 +1 = \bold3} routes lead to \latex{I}.
We can get to the point \latex{L} from \latex{G} and from \latex{H}. As \latex{1} route lead to \latex{G}, thus we can get to \latex{L} through \latex{G} in one way, \latex{3} routes lead to \latex{H}, thus we can get to \latex{L} through \latex{H} in \latex{3} different ways, a total of \latex{1+ 3 = \bold4} routes lead from \latex{A} to \latex{L}.
We can get to the point \latex{M} from \latex{H} and from \latex{I}, through \latex{H} in \latex{3} different ways, through \latex{I} also in \latex{3} different ways, so in a total of \latex{3 + 3 = \bold6} different ways.
We can get to the point \latex{N} in just as many ways as to \latex{L: 3 +1 = \bold4} different ways.
We can observe the following:
It can be seen that we can get to the points \latex{B,D,G,K,C,F,J,O} in 1 way. We can get to the point \latex{E} from \latex{B} and from \latex{C}, and 1 route lead to these points each, thus we can get to the point \latex{E} in \latex{2} different ways.
We can get to the point \latex{H} from the points \latex{D} and \latex{E}. \latex{1} route lead from \latex{A} to \latex{D}, thus there is \latex{1} route from \latex{A} to \latex{H} through \latex{D}. \latex{2} routes lead from \latex{A} to \latex{E}, thus there are \latex{2} routes from \latex{A} to \latex{H} through \latex{E}. So from \latex{A} to \latex{H} there are \latex{1+ 2 = \bold3} routes.
We can get to the point \latex{I} from the points \latex{E} and \latex{F}, similarly to the previous one \latex{2 +1 = \bold3} routes lead to \latex{I}.
We can get to the point \latex{L} from \latex{G} and from \latex{H}. As \latex{1} route lead to \latex{G}, thus we can get to \latex{L} through \latex{G} in one way, \latex{3} routes lead to \latex{H}, thus we can get to \latex{L} through \latex{H} in \latex{3} different ways, a total of \latex{1+ 3 = \bold4} routes lead from \latex{A} to \latex{L}.
We can get to the point \latex{M} from \latex{H} and from \latex{I}, through \latex{H} in \latex{3} different ways, through \latex{I} also in \latex{3} different ways, so in a total of \latex{3 + 3 = \bold6} different ways.
We can get to the point \latex{N} in just as many ways as to \latex{L: 3 +1 = \bold4} different ways.
We can observe the following:
- We can get to each point in as many ways as the sum of the number of routes leading to the starting points of the arrows pointing to these points.
- The figure is symmetric about the axis passing through the points \latex{A, E, M}.
Figure 4Solution II (by counting the combinations)
Let us examine in how many ways we can get to the point \latex{L}. For this we have to tour 4 stages (between two points), 3 stages leading to the left and 1 leading to the right. If we determined on which stage we want to go to the right, the route is fixed, since we have to turn to the left on all the other stages.
The one stage to the right can be any of the 4 stages, thus we can get from \latex{A} to \latex{L} in \latex{\dbinom{4}{1}= 4} different ways.
The one stage to the right can be any of the 4 stages, thus we can get from \latex{A} to \latex{L} in \latex{\dbinom{4}{1}= 4} different ways.
We can get to the point \latex{M} also through 4 stages, actually on 2 stages to the left and on 2 stages to the right. We can choose the 2 stages to the right arbitrarily out of the 4 stages, and with this we have determined the route, thus the number of these is: \latex{\dbinom{4}{2}= 6}
We can get to the point \latex{N} on 4 stages so that we turn left once and turn right 3 times. As the choice of the 3 stages to the right determines the route just as the choice of the 1 stage to the left; the number of the routes leading to \latex{N} is: \latex{\dbinom{4}{3}= \dbinom{4}{1}=4}.
By counting the number of the routes leading to the other points the triangle in figure 5 is obtained; the numbers written in it are equal to the numbers written to the corresponding places in the triangle in figure 4 based on solution I.
We can get to the point \latex{N} on 4 stages so that we turn left once and turn right 3 times. As the choice of the 3 stages to the right determines the route just as the choice of the 1 stage to the left; the number of the routes leading to \latex{N} is: \latex{\dbinom{4}{3}= \dbinom{4}{1}=4}.
By counting the number of the routes leading to the other points the triangle in figure 5 is obtained; the numbers written in it are equal to the numbers written to the corresponding places in the triangle in figure 4 based on solution I.
Figure 5This triangle is called the Pascal's triangle, and it can be continued either with the summation applied in solution I or with the counting of the combinations in solution II.
Because of the symmetry of the Pascal's triangle:
Because of the symmetry of the Pascal's triangle:
\latex{\dbinom{n}{k}=\dbinom{n}{n-k}}.
As the same triangle is obtained with the two methods, the sum of two adjacent elements of the \latex{n – 1^{th}} row is equal to the element below them in the \latex{n^{th}} row, thus the following relation is true:
\latex{\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}},
if \latex{n} and \latex{k} are whole numbers for which: \latex{2 \leq k + 1 \leq n}.
THEOREM: \latex{\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}}, if \latex{n} and \latex{k} are whole numbers for which: \latex{2 \leq k + 1 \leq n}.
Example 4
There are \latex{28} registered players (Matthew is one of them) in a football team. Before the match on Saturday \latex{11} players should be named for the starting team.
- In how many different ways is it possible if any player can be in the starting team?
- How many possibilities are there when Matthew is in the starting team?
- How many possibilities are there when Matthew is not in the starting team? What can be realised?
- Let us solve the problem for the case of \latex{n} players and \latex{k} starting players.
Solution (a)
When choosing the players for the starting team the order of choices does not matter, thus the number of possibilities is:
\latex{\dbinom{28}{11}=\frac{28!}{11!\times17!}=\frac{28 \times 27\times 26\times 25\times 24\times 23\times 22\times 21\times 20\times 19\times 18}{11\times 10 \times9 \times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1 }= 21 474 180}.
Solution (b)
If Matthew is in the starting team, then we have to choose \latex{10} players out of the remaining \latex{27} players; there are
\latex{\dbinom{27}{10}=\frac{27!}{10!\times17!}=\frac{27\times 26\times 25\times 24\times 23\times 22\times 21\times 20\times 19\times 18}{10 \times9 \times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1 }= 8 436 285}.
possibilities for this.
Solution (c)
If Matthew is surely not chosen to be in the starting team, then we have to choose the \latex{11} starting players out of the remaining \latex{27} players; there are
\latex{\dbinom{27}{11}=\frac{27!}{11!\times16!}=\frac{27\times 26\times 25\times 24\times 23\times 22\times 21\times 20\times 19\times 18\times 17}{11\times 10 \times9 \times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1 }= 13 037 895}
possibilities for this.
It can be realised that Matthew is either in the starting team or he is not, thus we can choose the starting team in as many different ways as Matthew is in the staring team plus as Matthew is not in the staring team.
Based on this:
Based on this:
\latex{\dbinom{28}{11}=\dbinom{27}{11}+\dbinom{27}{10}}.
(It can also be checked by adding the final results.)
Solution (d)
If the number of the players we can choose from is \latex{n}, and the number of the players in the starting team is \latex{k}, then the players of the starting team can be chosen in \latex{\dbinom{n}{k}} different ways.
If Matthew is in the starting team, then there are \latex{\dbinom{n-1}{k-1}} possibilities to choose the players of the starting team, if he is not in the starting team, then there are \latex{\dbinom{n-1}{k}} possibilities.
These together give the number of all the possibilities of choosing the players of the starting team:
If Matthew is in the starting team, then there are \latex{\dbinom{n-1}{k-1}} possibilities to choose the players of the starting team, if he is not in the starting team, then there are \latex{\dbinom{n-1}{k}} possibilities.
These together give the number of all the possibilities of choosing the players of the starting team:
\latex{\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}}.
With this a new proof is obtained for the previous theorem.
Exercises
{{exercise_number}}. We draw \latex{8} cards at once from the Hungarian pack of \latex{32} cards. (In a Hungarian pack of cards there are \latex{4} suits: Hearts, Bells, Leaves and Acorns, the numbering includes VII, VIII, IX, X, Under, Over, King and Ace.)
- In how many different ways can it be done?
- In how many different ways can it be done so that Heart seven is surely among the cards drawn?
- In how many different ways can it be done so that there is a Heart among the cards drawn?
{{exercise_number}}. How many triangles are there the vertices of which are chosen out of the vertices \latex{A, B, C, D, E, F, G, H} of a cube? How many triangles are there if we do not distinguish the congruent ones?
{{exercise_number}}. A delegation of five is chosen from a class of \latex{32} to represent them in the students' parliament. In how many different ways can we choose the \latex{5} delegates?
{{exercise_number}}. At most how many intersection points can \latex{12} distinct straight lines have?
{{exercise_number}}. Into at most how many different parts can \latex{6} distinct straight lines divide the plane?
{{exercise_number}}. How many different routes lead from \latex{A} to \latex{B} in the following maps, if one can go only to the right or down along the sides of the squares?
{{exercise_number}}. Imagine a \latex{10 \times19} board coloured like a chessboard. Let the top row be the first row, its tenth square is white and a figure is standing on it. This figure moves one down-right or down-left in every step. Thus it always stays on white squares. Let us write to the white squares in how many different ways the figure could get to these squares from the starting point by following the rules above.
{{exercise_number}}. In how many different ways can you read out the word MOZAIK from the figure if you can read only to the right or downwards?
{{exercise_number}}. How many body diagonals are there in a regular
- dodecahedron? (A regular dodecahedron has \latex{12} faces, which are regular pentagons, and at every vertex \latex{3} pentagons meet.)
- icosahedron? (A regular icosahedron has \latex{20} faces, which are regular triangles, and at every vertex \latex{5} triangles meet.)
{{exercise_number}}. In a handball tournament every team plays exactly once against all the other teams. Currently each team has two more matches to play. So far \latex{77} matches were played altogether. How many teams take part in the tournament?
{{exercise_number}}. Some people would like to go floor eight with an elevator for four. In how many different ways can they do it if the elevator turns the least possible times, it always goes directly to floor eight and no one comes back who had got to floor eight already. The number of people is:
- \latex{12};
- \latex{15}.
{{exercise_number}}. Five friends play the card game called “Crazy Eights”. At the beginning \latex{4} cards are dealt each from the Hungarian pack of \latex{32} cards. (In a Hungarian pack of cards there are \latex{4} suits: Hearts, Bells, Leaves and Acorns, the numbering includes VII, VIII, IX, X, Under, Over, King and Ace.) In how many different ways can it be done?
{{exercise_number}}. \latex{10} people sit down at a round table. Everyone shakes hands with everyone else above the table. How many pairs of handshakes cross each other?
