Вашата кошница е празна
Combinatorics, probability
During the years, we have solved many problems where the task was to enumerate things. We have studied the most common families of these problems during Year \latex{11} and now we will refresh these methods. It is important to note that the problems arising are rarely match one of these families, so it is worth much more to observe the methods used for solving different models rather than the final formulas.
Take four cards with the numbers \latex{1;\, 2;\, 3;\, 4;} we will illustrate the typical types of the studied combinatorial problems.
Permutations without repetition
How many different \latex{4}-digit numbers can be constructed using the \latex{4} cards?
We can choose from \latex{4} cards for the first position, from \latex{3} for the second, from \latex{2} for the third and from \latex{1} for the fourth, thus the four cards can be ordered \latex{4 \times3 \times2 \times1 = 4!} ways, this many different \latex{4}-digit numbers we can construct using the cards.
\latex{4}
\latex{\times}
\latex{\times}
\latex{\times}
\latex{3}
\latex{2}
\latex{1}
DEFINITION: A permutation without repetition of the elements of a set with \latex{n} elements is an arrangement of the n distinct elements. The elements are arranged, if we appoint the first, the second, \latex{\dots} and so on the \latex{n^{th}} element. Two arrangements are the same if the same elements are at the corresponding places.
THEOREM: The number of permutations of a given set with \latex{n} elements is \latex{n!}
Permutations with repetition
How many different \latex{4}-digit numbers can be constructed using the cards \latex{1;\, 2;\, 2;\, 4}?
Let us distinguish the two identical cards with the same digit, then there are \latex{4 \times3 \times2 \times1 = 4!} different orderings. The two distinct \latex{2\text s} can be written in \latex{2} different orders at the same positions. Now we do not distinguish the \latex{2\text s}, thus these two orderings count as one, therefore the number of orderings has to be divided by \latex{2}.
DEFINITION: If there is an element occurring more than once, an arrangement of the elements is called a permutation with repetition.
THEOREM: If there are \latex{p_1}; \latex{p_2}; \latex{\dots}; \latex{p_k} identical elements among \latex{n} elements, \latex{p_1+ p_2+ …+ p_n = n}, then these elements can be ordered in
\latex{\frac{n!}{p_1!\times p_2!\times …\times p_k!}}
different ways.
Variation with repetition
We pick two from the cards \latex{1;\, 2;\, 3;\, 4} such that after picking a card we place it back into the deck. How many possibilities are there?
We can pick a card out of \latex{4} for each position, therefore the number of possibilities is \latex{4^2}.
\latex{4}
\latex{\times}
\latex{4}
DEFINITION: If we choose \latex{k} elements out of \latex{n} elements with respect to the order (one type of element can be chosen several times), the \latex{k}-element variation with repetition of \latex{n} elements is obtained.
THEOREM: The number of the \latex{k}-element variations with repetition of \latex{n} elements is \latex{n^k.}
Variation without repetition
We pick two from the cards \latex{1;\, 2;\, 3;\, 4} such that after picking a card we cannot place it back to the deck. How many possibilities are there?
There are \latex{4} possibilities for the first pick while \latex{3} for the second, thus the number of possibilities is
\latex{4\times3=\frac{4!}{2!}}.
\latex{4}
\latex{\times}
\latex{3}
DEFINITION: If we choose \latex{k} elements out of \latex{n} different elements with respect to the order (arrangement), we obtain a \latex{k}-element variation without repetition of \latex{n} different elements \latex{(0 \leq k \leq n \text{ integers})}.
THEOREM: The number of the \latex{k}-element variations without repetition of \latex{n} different elements is:
\latex{n\times (n-1)\times (n-2)\times ...\times(n-k+1)=\frac{n!}{(n-k)!}}.
Combinations without repetition
We pick two from the cards \latex{1;\, 2;\, 3;\, 4} at the same time such that the order of the picked cards is irrelevant. How many outcomes are there?
There are \latex{4} possibilities for the first and \latex{3} for the second card, but since the order of the picked cards is irrelevant, we have to divide this product by the number of possible orderings of the picked cards, therefore the number of possibilities is
\latex{\frac{4\times3}{2}=\frac{4!}{2!\times2!}=\binom{4}{2}}.
\latex{4}
\latex{\times}
\latex{3}
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 \text{ 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 \text{ integers})} is: \latex{\binom{n}{k}}.
Knowing the previous types helps in solving the following problems, although these problems are complex and it is not enough to substitute into the formulas.
Example 1
We order the letters \latex{ S }, \latex{ A }, \latex{ R }, \latex{ O }, \latex{ K } every possible way and we form a list of the resulting “words” in a lexicographical order. What is the last letter of the \latex{27}th element of the list? What is it if we do the same for the letters \latex{ S }, \latex{ O }, \latex{ R }, \latex{ O }, \latex{ K }?
Solution
The letters \latex{ S }, \latex{ A }, \latex{ R }, \latex{ O }, \latex{ K } can be ordered \latex{5! = 1 \times2\times3\times4\times5 = 120} ways, thus \latex{120} “words” are written. There are \latex{4! = 24} words starting with a given letter, therefore the \latex{27}th word starts with the lexicographically second letter, K. The \latex{25}th word is \latex{ KAORS }, the \latex{26}th word is \latex{ KAOSR }, the \latex{27}th is \latex{ KAROS }, thus the last letter of the \latex{27}th element on the list is \latex{ S }.
Since there are two identical \latex{ O } in the second set of letters, there are only half as many different ordering of the letters as there were in the case of \latex{ S }, \latex{ A }, \latex{ R }, \latex{ O }, \latex{ K }. There are \latex{\frac{4!}{2!}=12} words starting with \latex{ K } because of the two \latex{ O }'s following it, but then there are \latex{4! = 24} words starting with \latex{ O }. This means that the \latex{27}th word is the \latex{15}th one starting with \latex{ O }.
There are \latex{3! = 6} words starting with \latex{ OK }, as well as for \latex{ OO }, which means that the \latex{27}th word is the \latex{3}rd one starting with \latex{ OR }. The words starting with \latex{ OR } in a lexicographical order are \latex{ ORKOS }, \latex{ ORKSO }, \latex{ OROKS }, … that is, the \latex{27}th element on the list is \latex{ OROKS }, whose last letter is \latex{ S }.
There are \latex{3! = 6} words starting with \latex{ OK }, as well as for \latex{ OO }, which means that the \latex{27}th word is the \latex{3}rd one starting with \latex{ OR }. The words starting with \latex{ OR } in a lexicographical order are \latex{ ORKOS }, \latex{ ORKSO }, \latex{ OROKS }, … that is, the \latex{27}th element on the list is \latex{ OROKS }, whose last letter is \latex{ S }.
Example 2
In a round robin tournament (each contestant meets every other contestant once) of table tennis the organizers wanted to reduce the number of matches by \latex{50}, so they invited \latex{4} less people. How many participants were there?
uninvited
players
players
remaining
players
players
Figure 5
Solution
The \latex{4} participants would have played \latex{\binom{4}{2}= \frac{4!}{2!\times2!}=6} games among themselves. The \latex{4} participants would have played \latex{50-6 = 44} games with the other participants \latex{= 11} games/person. Since they would have played with every other contestant, there were \latex{11} participants invited. (Figure 5)
Example 3
In a set of dominoes there is exactly one domino with \latex{0}-\latex{8} dots on both of its sides. By swapping the sides of a domino we end up with the same one and there are dominoes with the same number of dots on both sides.
- How many dominoes are there in the set?
- By picking two dominoes at random from the set, what is the probability that they can be placed next to each other (that is, they have a side with the same number of dots)?
Solution (a)
There are \latex{9} dominoes in the set with the same number of dots on its two sides \latex{(00;\, 11;\, 22;\, 33;\, 44;\, 55;\, 66;\, 77;\, 88)}. If the numbers of dots on the two sides of a domino are different, then we can choose their number \latex{9} ways for one side and \latex{8} ways for the other one. Since the order of the two sides is irrelevant, the number of dominoes with two different sides is
\latex{\frac{9\times 8}{2}=36}.
Thus there are \latex{36 + 9 = 45} dominoes in the set.
Solution (b)
We can choose two out of the \latex{45} dominoes in \latex{\binom{45}{2}= \frac{45\times44}{2}=990} ways, this is the total number of possibilities. The number of favourable possibilities equals the number of ways we can choose two matching dominoes from the set. If one domino is such that there are equal number of dots on its sides then we can choose this domino \latex{9} ways, and there are \latex{8} matching dominoes, this is \latex{9\times8 = 72} possibilities.
\latex{ 8 } possibilities
If none of the two dominoes have the same number of dots on its two sides, then, for example in the case of domino \latex{56}, there are \latex{7} dominoes matching its side of \latex{5} dots since there cannot be neither \latex{5} nor \latex{6} dots on the other side of the second domino. Similarly there are \latex{7} dominoes matching the side of \latex{6} dots, therefore for the \latex{36} dominoes with different sides there are \latex{36\times14 = 504} possibilities, but this way we have counted every matching pair twice, thus we have to divide by \latex{2}, so we have \latex{252}. The number of matching domino pairs is \latex{72 + 252 = 324}. Therefore the probability we are looking for is
\latex{\frac{324}{990}\approx 0.3273}.
\latex{ 7 } possibilities
\latex{ 7 } possibilities
◆ ◆ ◆
We have learned about the probability of events back in Year \latex{10}, which is a number between \latex{0} and \latex{1} which fluctuate around the relative frequency. The classical model of probability can be applied when an experiment have finitely many outcomes and the probabilities of these are equal. In this case the probability of an event is the quotient of the number of favourable possibilities and the total number of possibilities. It is quite common that combinatorics is used to compute these numbers.
\latex{\text{In the classical probabilistic model,}\\\text{probability}=\\=\frac{\text{number of favourable possibilities}}{\text{total number of possibilities}}}.
Example 4
The numbers \latex{1}-\latex{10} are written on \latex{10} cards and were placed in a hat. We draw \latex{3} cards one after another. What is the probability that the numbers are drawn in an increasing order?
Solution
With respect to the order we can draw \latex{3} cards out of \latex{10} cards in \latex{10\times 9\times 8 = \frac{10!}{7!}} ways, this is the total number of possibilities. Since for any \latex{3} drawn cards there is only one increasing ordering, the number of favourable outcomes equals the number of ways \latex{3} cards can be drawn with the order of drawing being irrelevant, that is, \latex{\dbinom{10}{3}=\frac{10!}{3!\times7!}}. Thus the probability we are looking for is
\latex{\frac{\dbinom{10}{3}}{\dfrac{10!}{7!}}=\frac{\dfrac{10!}{3!\times7!}}{\dfrac{10!}{7!}}=\frac{1}{3!}=\frac{1}{6}}.
The simplicity of the result suggests that it is possible to find an easier solution. Since \latex{3} cards can be drawn in \latex{3! = 6} different order and there is only one which is increasing, the probability is \latex{\frac{1}{6}}.
This example demonstrates the correlation between variation without repetitions and combinations.
Example 5
In a bubblegum dispenser there are three kinds of bubblegum, \latex{15} yellow, \latex{18} blue and \latex{20} green. The twin sons of Kathy want to get bubblegums of the same colour. What is the probability that it is enough for Kathy to buy
- two;
- three;
- four bubblegums?
Solution (a)
From the total of \latex{15 + 18 + 20 = 53} bubblegums we can choose two in \latex{\dbinom{53}{2}} ways with no respect to the ordering.
We get two gums of the same colour if we have chosen two of either the \latex{ 15 } yellow or the \latex{ 18 } blue or the \latex{ 20 } green, overall there are \latex{\dbinom{15}{2}+\dbinom{18}{2}+\dbinom{20}{2}} such ways. Therefore the probability is
\latex{\frac{\dbinom{15}{2}+\dbinom{18}{2}+\dbinom{20}{2}}{\dbinom{53}{2}}}.
Solution (b)
Three purchases are enough for getting two of the same colour if we don't choose three different colours, thus this probability is
\latex{1-\frac{15\times18\times20}{\dbinom{53}{3}}}.
If we are interested in the probability of having to purchase exactly three gums, then we have to subtract the probability of having to purchase exactly two from the probability of having to purchase at most three.
Alternatively one can compute the probability of having to purchase exactly three gums directly; the easiest way is to illustrate the possible purchases using a tree graph like the one below, and find the corresponding probability using it. (Figure 6)
\latex{ Y }
\latex{ G }
\latex{ B }
\latex{ Y }
\latex{ G }
\latex{ B }
\latex{ Y }
\latex{ G }
\latex{ B }
\latex{ Y }
\latex{ G }
\latex{ B }
\latex{ Y }
\latex{ G }
\latex{ B }
\latex{ Y }
\latex{ G }
\latex{ B }
\latex{ G }
\latex{ Y }
\latex{ B }
\latex{ B }
\latex{ G }
\latex{ B }
\latex{ G }
\latex{ Y }
\latex{ B }
\latex{ Y }
\latex{ G }
\latex{ \frac {19}{52} }
\latex{ \frac {17}{52} }
\latex{ \frac {14}{52} }
\latex{ \frac {14}{52} }
\latex{ \frac {20}{52} }
\latex{ \frac {18}{52} }
\latex{ \frac {15}{53} }
\latex{ \frac {18}{53} }
\latex{ \frac {20}{53} }
\latex{ \frac {15}{52} }
\latex{ \frac {20}{52} }
\latex{ \frac {15}{52} }
\latex{ \frac {14}{51} }
\latex{ \frac {18}{51} }
\latex{ \frac {15}{51} }
\latex{ \frac {17}{51} }
\latex{ \frac {14}{51} }
\latex{ \frac {17}{51} }
\latex{ \frac {15}{51} }
\latex{ \frac {17}{51} }
\latex{ \frac {17}{51} }
\latex{ \frac {14}{51} }
\latex{ \frac {18}{51} }
\latex{ \frac {14}{51} }
\latex{ \frac {19}{51} }
\latex{ \frac {20}{51} }
\latex{ \frac {19}{51} }
\latex{ \frac {19}{51} }
\latex{ \frac {20}{51} }
\latex{ \frac {19}{51} }
Figure 6
Solution (c)
One can see using the previous tree graph that after purchasing a fourth bubblegum there will always be two of the same colour.
We can reach the same conclusion using the pigeonhole principle: if there are \latex{3} different colours and we buy \latex{4} items, then there always will be a colour which is the colour of two purchased items.
Example 6
We roll a regular die \latex{4} times. What is the probability that either \latex{5} or \latex{6} will occur at least once?
Solution
The number of different series of rolls is \latex{6^4} since every roll has \latex{6} possible outcomes.
If we enumerate the number of favourable series by computing the number of series where there is \latex{1, 2, 3} and \latex{4} rolls of \latex{5} or \latex{6}, then we would have to compute lots of cases. Instead, we should take a look at the event's complement, that is, the event when there is neither \latex{5} nor \latex{6} rolled. We can only roll \latex{4} numbers each times, thus the number of favourable outcomes is \latex{4^4}, therefore the probability we are looking for is
\latex{1-\frac{4^4}{6^4}}.
Example 7
During an extremely violent ice hockey match, \latex{85\%} of the players lost at least one tooth and \latex{70\%} of them broke a finger.
- At least what is the probability that by picking a player at random he had lost a tooth and broke a finger?
- We also know that \latex{75\%} of the players also dislocated an ankle. At least what is the probability that by picking a player at random he has suffered all three injuries?
Solution (a)
The number of players suffered from both types of injury will be minimal if there is no one left intact, that is, the percentage of injured players is \latex{100}%. (Figure 7)
In this case the ratio of players suffered both injuries is
\latex{ 85 }% \latex{ +} \latex{ 70 }% \latex{ - } \latex{100 }% \latex{ = 55 }%.
\latex{ 85 }%
\latex{ 70 }%
\latex{ 100 }%
Figure 7
Therefore by choosing a player at random the probability of him having both types of injuries is at least \latex{0.55}.
Formula of logical sieve:
Formula of logical sieve:
\latex{\mid A\cup B\mid = \mid A\mid +\mid B\mid-\mid A\cap B\mid\Rightarrow\mid A\cap B\mid = \mid A\mid +\mid B\mid -\mid A\cup B\mid}.
For probabilities:
\latex{P(A+B) = P(A) + P(B)-P(A\times B)\Rightarrow P(A×B) = P(A) + P(B)-P(A+ B)}.
Since \latex{P(A+B) \leq 1}, it follows that \latex{P(A \times B)\geq P(A) + P(B)-1}.
Solution (b)
By continuing the above reasoning, at least \latex{55}% of the players lost a tooth and broke a finger and \latex{75}% have a dislocated ankle. Therefore at least \latex{ 55 }% \latex{ + } \latex{ 75 }% \latex{ - } \latex{ 100 }% \latex{=30 }% of the players suffered from all injuries.
Example 8
There are \latex{2} black and \latex{2} white marbles in a box.
- Susy draws a marble from the box and she sees that it is white. Without putting the marble back she proceeds to draw another. Which probability is bigger: that this second marble is black or that it is white?
- Later Gaby draws a marble from the \latex{2} black and \latex{2} white marbles. Without looking at it (or putting it back) she draws another, this time a white one. Which probability is bigger: that the first marble was black or that it was white?
Solution (a)
If Susy takes a white marble there are \latex{2} black ones and \latex{1} white one left, so obviously she has a bigger chance of drawing a black one for next then drawing another white. Probability of drawing a white marble is \latex{\frac{1}{3}} while that of drawing a black one is \latex{\frac{2}{3}}.
Solution (b)
The probability of the marble drawn second being white is \latex{\frac{2}{3}} if the first one was black and \latex{\frac{1}{3}} if the first one was white. Thus for the \latex{\frac{1}{3}} of the possibilities the first marble was white and for \latex{\frac{2}{3}} it was black, therefore it is more likely that Gaby's first marble was black.
The common property of the two cases is that we have drawn two marbles, we have told that one is white and we are looking for the probability of the other one being white as well.
The two consecutive draws can be illustrated with a tree graph, from which the probabilites in question can be read. (Figure 8)
The two consecutive draws can be illustrated with a tree graph, from which the probabilites in question can be read. (Figure 8)
\latex{ \frac{2}{3} }
\latex{ \frac{2}{3} }
\latex{ \frac{1}{3} }
\latex{ \frac{1}{3} }
\latex{ \frac{1}{2} }
\latex{ \frac{1}{2} }
Figure 8
Exercises
{{exercise_number}}. A maritime expedition is being assembled and there are some open positions: \latex{1} team leader, \latex{1} medic, \latex{4} biologists, \latex{2} chemists and \latex{1} engineer are needed. There are \latex{4} applications for the team leader position, \latex{5} for medic, \latex{20} for biologist, \latex{8} for chemist and \latex{3} for engineer. It was not allowed to apply for more than one position. How many ways can the research team be assembled if there are no other positions?
{{exercise_number}}. A letter full of strange symbols was found. The encryption contains \latex{26} symbols, all of which stands for a letter.
- How many possible decryptions are there? (By decryption we mean a one-to-one correspondence between the symbols of the letter and the letters of the English alphabet.)
- How many possible decryptions are there if it has been discovered by analyzing the symbols' positions which \latex{5} letters are the vowels (and thus which \latex{21} are the consonants)?
- How many possible decryptions are there if on top of the previous, by analyzing the frequency of the symbols \latex{2} vowels and \latex{4} consonants has been identified?
{{exercise_number}}. There are \latex{12} participants in some round of a contest. How many results are possible if the rules are the following?
- Three contestants will advance to the next round according the judges' decision, and one more will advance according the votes of the spectators. There is no order between those who advance and those who relegate.
- \latex{5} contestants are relegated and the organizers announce the first, second and third prize's winner and the list of the five contestant who relegate (in alphabetical order).
{{exercise_number}}. We have a rope positioned as seen on the figure. We do not know which part is above and which is below at each crossing (at points \latex{ A }, \latex{ B } and \latex{ C }). Suppose that every setting is equally probable, what is the probability that there is a knot on the rope?
\latex{ A }
\latex{ B }
\latex{ C }
{{exercise_number}}. We roll \latex{3} regular dice and add the resulting three numbers. Which is the more probable, that the sum is odd or that it is even?
{{exercise_number}}. Cards with the numbers \latex{1}-\latex{400} are placed in a hat. What is the probability that the number of a card picked at random is a multiple of \latex{4} or \latex{17}?
{{exercise_number}}. We numbered \latex{50} table tennis balls with the numbers \latex{1}-\latex{50}. One after another \latex{15} children draw a ball, take a look at it and replace it. What is the probability of two children drawing the same ball?
{{exercise_number}}. The spirit of the statue erected in the yard of the high school always tells the truth when replies to a question, but the chance of replying is only \latex{\frac{1}{3}}. A student plans to ask the spirit three times about his maturity exam's result. What is the probability that the spirit replies?
{{exercise_number}}. Dororthy is making a cube shaped Christmas decoration using the grid depicted on the figure. A ladybug lands on a square of the shape picked at random and then it moves to an adjoining square also picked at random.
- What is the probability that the ladybug ends up on the red square?
- How does the probability change if the ladybug lands on one of the faces of the already finished and hanged cube and moves to an adjoining face?
{{exercise_number}}. There are \latex{12} marbles in each of two hats, \latex{6} black and \latex{6} white in the first hat, \latex{12} black in the second. We move a randomly chosen marble from the first hat to the second, then we pick a marble from the second hat. What is the probability that this marble is black?
{{exercise_number}}. In the amusement park, Joe Thunderfists hits the target for the first shot with a probability of \latex{60\%}. The chance of missing after a hit or hitting after a miss is half the according chance of the previous shot. That is, for example if his first shot hits, then the probability of missing the second one is \latex{20\%} (since there was a \latex{40\%} chance for missing the first time). What is the probability of him hitting the target at least twice from three shots?
{{exercise_number}}. A gambler has two coins in his pockets, one regular (heads on one side, tails on the other) and one with heads on both sides. He picks a coin at random and flips it twice. What is the probability that he picked the regular coin if both flips resulted in heads?