Vaša košarica je prazna
Miscellaneous counting exercises
(extra-curricular topic)
Previously we got familiar with some main types of combinatorial exercises and their solutions. In the case of particular exercises it is not easy to decide which type they are rated to, thus we have to try for the understanding application of the solution methods instead of the formulae.
Example 1
In how many different ways can we get from the bottom left corner of the chessboard to the top right corner with a castle by moving closer to the target with every step (Figure 6):
Figure 6
- in \latex{14} steps;
- in \latex{13} steps;
- in \latex{12} steps?
Solution (a)
We can get from the bottom left corner to the top right corner in \latex{14} steps, if we move one square every time, \latex{7} times to the right and \latex{7} times upwards. These steps can be arranged in \latex{\frac{14!}{7!\times7!}=20,592} different ways, so this is the number of the possible distinct routes.
Solution (b)
We can get from the bottom left corner to the top right corner in \latex{13} steps, if we move two squares once, and we move one square in the other steps. We can do this so that
- we move to the right \latex{ 2 } squares once and one square \latex{ 5 } times and we move upwards one square \latex{ 7 } times, or
- we move to the right one square \latex{ 7 } times and we move upwards \latex{ 2 } squares once and one square \latex{ 5 } times.
Thus the number of possibilities is: \latex{\frac{13!}{5!\times7!}\times2=20,592}.
Solution (c)
We can get from the bottom left corner to the top right corner in \latex{12} steps, if
- we move to the right \latex{3} squares once and one square four times and we move upwards one square \latex{7} times, or
- we move upwards \latex{3} squares once and one square four times and we move to the right one square \latex{7} times, or
- we move to the right \latex{2} squares once and one square \latex{ 5 } times and we move upwards \latex{2} squares once and one square \latex{5} times, or
- we move to the right \latex{2} squares twice and one square \latex{3} times and we move upwards one square \latex{7} times, or
- we move upwards \latex{2} squares twice and one square \latex{3} times and we move to the right one square \latex{7} times.
Thus the number of possibilities is:
\latex{\frac{12!}{4!\times7!}\times2+\frac{12!}{5!\times5!}+\frac{12!}{2!\times3!\times7!}\times2=57,024}.
Example 2
In a French deck of \latex{52} cards there are \latex{4} suits (hearts, diamonds, spades and clubs) and \latex{13} ranks \latex{(2;\, 3;\, 4;\, 5;\, 6;\, 7;\, 8;\, 9;\, 10;\, J;\, Q;\, K;\, A)} of each suit. In how many different ways can we choose \latex{5} cards so that the order does not matter and
- there are no two cards of the same rank;
- there are exactly two cards of the same rank (one pair);
- there are exactly two pairs of cards of the same rank (two pairs);
- there are exactly three cards of the same rank (three of a kind);
- there are three cards of one rank and two cards of another rank (full house);
- there are four cards of the same rank (four of a kind);
- the ranks are adjacent ones, but their suits do not matter (straight);
- the ranks are adjacent ones, and they are the same suit (straight flush).
Solution (a)
We can choose the \latex{5} cards in \latex{\dbinom{52}{5}=2,598,960} different ways without respect to the order. Each of the five cards can be of \latex{4} suits, and we have to choose five out of the \latex{13} ranks; the number of possibilities is:
\latex{4^5\times\dbinom{13}{5}=1,317,888}.
Solution (b)
The suit of the two alike ranks can be chosen in \latex{\dbinom{4}{2}} different ways and the suit of the other \latex{3} distinct ranks in \latex{4^3} different ways. We can choose the rank of the pair in \latex{13} different ways, the other \latex{3} ranks can be chosen out of the remaining \latex{12}, thus the number of possibilities is:
\latex{\dbinom{4}{2}\times4^3\times13\times\dbinom{12}{3}=1,098,240}.
Solution (c)
The suits of the two pairs of alike ranks can be chosen in \latex{\dbinom{4}{2}\times\dbinom{4}{2}} different ways, and the suit of the fifth card in \latex{4} different ways. The rank of the fifth card can be chosen after the two ranks of the two pairs of cards in \latex{11} different ways, thus the number of possibilities is:
\latex{\dbinom{4}{2}\times\dbinom{4}{2}\times 4\times\dbinom{13}{2}\times 11=123,552}.
Solution (d)
The suit of the three alike ranks can be chosen in \latex{\dbinom{4}{3}=4} different ways and the suit of the other \latex{2} distinct ranks in \latex{4^2} different ways. We can choose the rank of the three of a kind cards in \latex{13} different ways, the other two ranks can be chosen out of \latex{12}, thus the number of possibilities is:
\latex{4^3\times13\times\dbinom{12}{2}=54,912}.
Solution (e)
The suit of the three alike ranks can be chosen in \latex{\dbinom{4}{3}= 4} different ways and the suit of the two alike ranks in \latex{\dbinom{4}{2}} different ways. We can choose the rank of the three of a kind cards in \latex{13} different ways, and the rank of the pair in \latex{12} different ways, thus the number of possibilities is:
\latex{4\times\dbinom{4}{2}\times13\times12=3,744}.
Solution (f)
If there are four of a kind of one rank, then all \latex{4} suits are there, it is possible in one way only; the \latex{5}th card can be any of the \latex{4} suits. We can choose the rank of the four of a kind cards in \latex{13} different ways, and the rank of the remaining card in \latex{12} different ways, thus the number of possibilities is: \latex{4 \times13 \times12 = 624}.
Solution (g)
Each of the \latex{5} cards can be of \latex{4} suits, and the \latex{5} adjacent ranks can be chosen in \latex{9} different ways, thus the number of possibilities is: \latex{4^5 \times 9 = 9,216}.
Solution (h)
The suit of the \latex{5} cards of the same suit can be chosen out of \latex{4} suits, and the \latex{5} adjacent ranks can be chosen in \latex{9} different ways, thus the number of possibilities is: \latex{4 \times 9 = 36}.
Example 3
\latex{10} different books are drawn among the students of a class of \latex{30} so that one student can win several books. In how many different ways is it possible that Sue (there is only one Sue in the class)
- wins the Paris travel guide and nothing else?
- wins the Paris travel guide?
- wins exactly one book?
- wins at least one book?
Solution (a)
Sue can win the Paris travel guide in one way only, the other \latex{9} books can be drawn among the other \latex{29} students; the number of possibilities is: \latex{1\times 29^9}.
Solution (b)
Sue wins the Paris travel guide, the other \latex{9} books can be drawn among the \latex{30} students; the number of possibilities is: \latex{30^9}.
Solution (c)
We can choose the book Sue wins in \latex{10} different ways, the other \latex{9} books can be drawn among \latex{29} students; the number of possibilities is: \latex{10\times 29^9}.
Solution (d)
Sue can win at least one book if she wins \latex{1;\, 2;\, 3;\, 4;\, 5;\, 6;\, 7;\, 8;\, 9} or \latex{10} books; counting these cases takes a lot of time.
The solution is obtained faster if we subtract from all the \latex{30^{10}} possibilities those, when Sue does not win any book, and it is \latex{29^{10}} possibilities; thus she can win at least one book in a total of \latex{30^{10} -29^{10}} different ways.
Exercises
{{exercise_number}}. The teacher realised that every student of the class shook hands with \latex{6} girls and \latex{8} boys. The number of handshakes between a boy and a girl is \latex{5} less than the number of all the other handshakes. How many students are there in the class?
{{exercise_number}}. How many positive whole numbers are there for which exactly three of the following five characteristics hold: has two digits; is a square number; is even; is divisible by \latex{3}, but is not divisible by \latex{9}; is a prime?
{{exercise_number}}. Steven, Zack and Alan went fishing together. All three of them caught fish, which they put in their own buckets. Together they caught five fish: a meagre, a carp, a pike, a catfish and a wall eye. In how many different ways can the fish be arranged in the buckets of the three anglers? (Two arrangements are considered to be different, if there is a fish that is not in the same bucket.)
{{exercise_number}}. The big cat tamer would like to walk out \latex{5} lions and \latex{4} tigers into the ring, but two tigers should not follow each other. In how many different ways can he order the animals, if we distinguish the tigers and also the lions? Generalise for the case of \latex{n} lions and \latex{k} tigers.
{{exercise_number}}. In how many different ways can five red, three white and two blue balls be arranged so that no two white balls are next to each other? (The balls of same colour are considered to be alike.)
{{exercise_number}}. Three children picked \latex{40} apples, then (without cutting any) they shared them.
- How many distributions are possible if the apples are distinguished?
- How many distributions are possible if the apples are not distinguished?
- How many distributions are possible if the apples are not distinguished, but it is restricted that each child should get at least one apple?
- Generalise!
{{exercise_number}}. Into at most how many parts do(es) \latex{1;\, 2;\, 3;\, 4;\, 5} and in general \latex{n} circles divide the plane?
Puzzle
Six different coloured balloons are hanging on three strings in a shooting gallery according to the figure. In how many different orders can all the balloons be shot, if one can shoot only at a balloon, which is the lowest intact one on its string
