As Gerry Myerson pointed out, what you are asking is equivalent to asking how many solutions there are to the equation $$x_1 + x_2 + x_3 + x_4 = 4$$ in the non-negative integers, where $x_1$ represents the number of $a$'s in the string, $x_2$ represents the number of $b$'s, $x_3$ represents the number of $c$'s, and $x_4$ represents the number of $d$'s. The number of solutions of this equation is the number of ways we can insert three addition signs in a list of four ones. For instance, $$1 1 + + 1 + 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 0$, $x_3 = 1$, and $x_4 = 1$, while $$+ 1 + 1 + 1 1$$ corresponds to the solution $x_1 = 0$, $x_2 = 1$, $x_3 = 1$, and $x_4 = 2$. The number of solutions is thus the number of ways of selecting three addition signs from $4 + 3 = 7$ symbols, which is $$\binom{4 + 3}{3} = 35$$ Using similar reasoning, you can show that the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the non-negative integers is $$\binom{n + k - 1}{k - 1}$$ Show The number of ways of arranging n unlike objects in a line is n! (pronounced ‘n factorial’). n! = n × (n – 1) × (n – 2) ×…× 3 × 2 × 1 Example How many different ways can the letters P, Q, R, S be arranged? The answer is 4! = 24. This is because there are four spaces to be filled: _, _, _, _ The first space can be filled by any one of the four letters. The second space can be filled by any of the remaining 3 letters. The third space can be filled by any of the 2 remaining letters and the final space must be filled by the one remaining letter. The total number of possible arrangements is therefore 4 × 3 × 2 × 1 = 4!
n! . Example In how many ways can the letters in the word: STATISTICS be arranged? There are 3 S’s, 2 I’s and 3 T’s in this word, therefore, the number of ways of arranging the letters are: 10!=50 400 Rings and Roundabouts
When clockwise and anti-clockwise arrangements are the same, the number of ways is ½ (n – 1)! Example Ten people go to a party. How many different ways can they be seated? Anti-clockwise and clockwise arrangements are the same. Therefore, the total number of ways is ½ (10-1)! = 181 440 Combinations The number of ways of selecting r objects from n unlike objects is:  Example There are 10 balls in a bag numbered from 1 to 10. Three balls are selected at random. How many different ways are there of selecting the three balls? 10C3 =10!=10 × 9 × 8= 120 Permutations A permutation is an ordered arrangement.
nPr = n! . Example In the Match of the Day’s goal of the month competition, you had to pick the top 3 goals out of 10. Since the order is important, it is the permutation formula which we use. 10P3 =10! = 720 There are therefore 720 different ways of picking the top three goals. Probability The above facts can be used to help solve problems in probability. Example In the National Lottery, 6 numbers are chosen from 49. You win if the 6 balls you pick match the six balls selected by the machine. What is the probability of winning the National Lottery? The number of ways of choosing 6 numbers from 49 is 49C6 = 13 983 816 . Therefore the probability of winning the lottery is 1/13983816 = 0.000 000 071 5 (3sf), which is about a 1 in 14 million chance. Remember what it means for a function to be bijective: each element in the codomain must be the image of exactly one element of the domain. Using two-line notation, we could write one of these bijections as \begin{equation*} f = \twoline{1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8} {3 \amp 1 \amp 5 \amp 8 \amp 7 \amp 6 \amp 2 \amp 4} \end{equation*}What we are really doing is just rearranging the elements of the codomain, so we are creating a permutation of 8 elements. In fact, “permutation” is another term used to describe bijective functions from a finite set to itself. If you believe this, then you see the answer must be \(8! = 8 \cdot 7 \cdot\cdots\cdot 1 = 40320\text{.}\) You can see this directly as well: for each element of the domain, we must pick a distinct element of the codomain to map to. There are 8 choices for where to send 1, then 7 choices for where to send 2, and so on. We multiply using the multiplicative principle. Example1.3.5You decide to have a dinner party. Even though you are incredibly popular and have 14 different friends, you only have enough chairs to invite 6 of them.
Solution You must simply choose 6 friends from a group of 14. This can be done in \({14 \choose 6}\) ways. We can find this number either by using Pascal's triangle or the closed formula: \(\frac{14!}{8!\cdot 6!} = 3003\text{.}\) Here you must count all the ways you can permute 6 friends chosen from a group of 14. So the answer is \(P(14, 6)\text{,}\) which can be calculated as \(\frac{14!}{8!} = 2192190\text{.}\) Notice that we can think of this counting problem as a question about counting functions: how many injective functions are there from your set of 6 chairs to your set of 14 friends (the functions are injective because you can't have a single chair go to two of your friends). How are these numbers related? Notice that \(P(14,6)\) is much larger than \({14 \choose 6}\text{.}\) This makes sense. \({14 \choose 6}\) picks 6 friends, but \(P(14,6)\) arranges the 6 friends as well as picks them. In fact, we can say exactly how much larger \(P(14,6)\) is. In both counting problems we choose 6 out of 14 friends. For the first one, we stop there, at 3003 ways. But for the second counting problem, each of those 3003 choices of 6 friends can be arranged in exactly \(6!\) ways. So now we have \(3003\cdot 6!\) choices and that is exactly \(2192190\text{.}\) Alternatively, look at the first problem another way. We want to select 6 out of 14 friends, but we do not care about the order they are selected in. To select 6 out of 14 friends, we might try this: This is a reasonable guess, since we have 14 choices for the first guest, then 13 for the second, and so on. But the guess is wrong (in fact, that product is exactly \(2192190 = P(14,6)\)). It distinguishes between the different orders in which we could invite the guests. To correct for this, we could divide by the number of different arrangements of the 6 guests (so that all of these would count as just one outcome). There are precisely \(6!\) ways to arrange 6 guests, so the correct answer to the first question is \begin{equation*} \frac{14 \cdot 13 \cdot 12 \cdot 11\cdot 10 \cdot 9}{6!}. \end{equation*}Note that another way to write this is \begin{equation*} \frac{14!}{8!\cdot 6!}. \end{equation*}which is what we had originally. 6How many of the quadrilaterals possible in the previous problem are:
Solution 5 squares. You need to skip exactly one dot on the top and on the bottom to make the side lengths equal. Once you pick a dot on the top, the other three dots are determined. This is tricky since you need to worry about running out of space. One way to count: break into cases by the location of the top left corner. You get \({7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) = 91\) parallelograms. All of them \({7\choose 2}{7\choose 2} - \left[ {7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) \right]\text{.}\) All of them, except the parallelograms. |
