Section6.2Counting
-
Exercise 2.0.2 Let \(n\) be odd first, like it was with \(n=199\text{.}\) Then if we rearrange the summands (first with last, second with one but last, etc.). then the middle term will remain, which is \(\frac{n+1}{2}\text{:}\)
\begin{align*} \amp 1 + 2 + \dots + \left(n-1\right) + n = \left(1 + n\right) + \left(2 + n-1\right) + \dots\\ \amp + \left(\frac{n-1}{2} + \frac{n+3}{2} \right) + \frac{n+1}{2} = (n+1) + (n+1) + \dots\\ \amp + (n+1) + \frac{n+1}{2} = \left( n+1 \right) \cdot \frac{n-1}{2} + \frac{n+1}{2}\\ \amp = \left( n+1 \right) \cdot \left( \frac{n-1}{2} + \frac{1}{2} \right) = \frac{(n+1) \cdot n}{2}\text{.} \end{align*}If \(n\) is even, then after rearranging the summands, no term will remain:
\begin{align*} \amp 1 + 2 + \dots + \left(n-1\right) + n = \left(1 + n\right) + \left(2 + n-1\right) + \dots\\ \amp + \left(\frac{n}{2} + \frac{n+2}{2} \right) = (n+1) + (n+1) + \dots\\ \amp + (n+1) = \left( n+1 \right) \cdot \frac{n}{2} = \frac{(n+1) \cdot n}{2}\text{.} \end{align*} Exercise 2.0.4 If everyone shakes hands with three other, then they do not shake hand with exactly one person. It is easier to consider who does not shake hand with whom. The first person does not shake hand with someone. Then of the remaining three people the first does not shake hand with someone from these three. That leaves one person, who does not shake hand with someone else, but everybody else has already been accounted for about not shaking hands with somebody. Thus, it is not possible that each of the five people shake hands with three others. This argument does not work if someone is allowed to shake hands with someone else more than once. Nevertheless, the answer is still no. Use the same argument we used for proving Corollary 2.0.3. If we sum up all the handshakes for everyone, we obtain \(5 \cdot 3 = 15\text{,}\) as each of the 5 people shakes hand with 3 others. This way, we counted every handshake twice, thus to obtain the number of handshakes we need to divide it by 2. But \(15/2\) is not an integer, while the number of handshakes should be an integer. This contradiction proves that it is not possible that each of 5 people shakes hand with 3 others. For 7 people we can use this argument, again. If we sum up all the handshakes for everyone, we obtain \(7 \cdot 3 = 21\text{,}\) as each of the 7 people shakes hand with 3 others. This way, we counted every handshake twice, thus to obtain the number of handshakes we need to divide it by 2. But \(21/2\) is not an integer, while the number of handshakes should be an integer. This contradiction proves that it is not possible that each of 7 people shakes hand with 3 others.
Exercise 2.0.5 The four boys shake hands with each other, that is, \(\frac{4 \cdot 3}{2} = 6\) handshakes. The four girls kisses each other, those are \(\frac{4 \cdot 3}{2} = 6\) kisses by the same formula we use for handshakes. Finally, a boy and a girl kisses, as well. All four boys kiss all four girls on the cheek, which is \(4 \cdot 4 = 16\) more kisses. Ultimately, there are 6 handshakes and 22 kisses.
-
Not possible. If there are five packs, each of them containing odd many rabbits, then altogether in the five packs there are odd many rabbits (odd\(+\)odd\(+\)odd\(+\)odd\(+\)odd is odd). As 100 is not an odd number, it is not possible to do the required distribution.
It is possible, e.g. \(3 \cdot 3 \cdot 1 \cdot 1\cdot 1\text{.}\) Another possibility could be \(9 \cdot 1 \cdot (-1) \cdot 1 \cdot (-1)\text{,}\) or simply \(9\) (as only one integer).
It is possible, e.g. \(3 \cdot 3 \cdot 1 \cdot 1\cdot 1\cdot 1 \cdot (-1) \cdot 1 \cdot (-1)\text{,}\) or another possibility is \(9 \cdot 1 \cdot (-1) \cdot 1 \cdot (-1) \cdot 1 \cdot (-1) \cdot 1 \cdot (-1)\text{.}\)
Not possible. If the product of integer numbers is 9, then all of them are odd. But then the sum of 9 odd integer numbers is odd again, and hence cannot be 0.
-
-
We can apply Proposition 2.0.1 and obtain
\begin{equation*} 1 + 2 + 3 + \dots + 23 + 24 = \frac{24\cdot 25}{2} = 300\text{.} \end{equation*} -
This is a bit more tricky, but not much. One needs to calculate the denominator, as we just calculated the numerator. Now,
\begin{align*} 1-2+3-4+ \dots + 23-24 \amp = (1-2) + (3-4) + \dots + (23-24)\\ (-1) + (-1) + \dots + (-1) \amp = -12\text{.} \end{align*}Thus the fraction we needed to compute is \(\frac{300}{-12} = -25\text{.}\) Another way to calculate the denominator could have been the following:
\begin{align*} \amp 1-2+3-4+ \dots + 23-24 = 1+2 + 3+4 + \dots + 23+24\\ \amp - 2 \cdot (2 + 4 + \dots + 24) = 300 - 2 \cdot 2 \cdot (1 + 2 + \dots + 12)\\ \amp = 300 - 4 \cdot \frac{12\cdot 13}{2} = 300- 312 = -12\text{.} \end{align*}
-
-
Exercise 2.1.1 There is only one possibility for the first digit (it cannot be 0, only 1), and there are two possibilities for every other digit. Thus, the number of \(n\)-digit positive integers in base 2 is
\begin{equation*} 1 \cdot \underbrace{2 \cdot \dots \cdot 2}_{n-1} = 2^{n-1}\text{.} \end{equation*} -
Exercise 2.1.5 If \(abc_{10}\) is a base 10 three-digit palindrome number, then \(a = c\text{,}\) and \(a \neq 0\text{.}\) Thus we can choose \(a\) in 9-many ways and \(b\) in 10-many ways, and hence the number of three-digit palindrome numbers is \(9 \cdot 10 = 90\text{.}\) For determining the at most three-digit palindrome numbers, we need to find the one-digit long and two-digit long palindrome numbers. Every one-digit number is a palindrome number. There are exactly 9 two-digit palindrome numbers: the \(aa_{10}\) numbers for \(a\neq 0\text{.}\) That is, there are \(9+9+90=108\) at most three-digit palindrome numbers. Now, consider the number of \(n\)-digit palindrome numbers in base \(k\text{.}\) One thing to note is that the first half of the number determines the back half completely. Thus we need to count how many ways can we choose the first half. Let \(n\) be even first. Then the first digit is the same as the last digit and differs from 0: there are \((k-1)\)-many possibilities to choose for the first digit. The second digit is the same as the one but last: there are \(k\)-possibilities to choose this digit, etc. Finally, the digit at the \(n/2\) position is the same as the digit at the \(n/2+1\) position: there are \(k\) possibilities to choose this digit. Thus, altogether the number of \(n\)-digit base \(k\) palindrome numbers (for even \(n\)) is
\begin{equation*} (k-1) \cdot \underbrace{k \cdot \dots \cdot k}_{n/2-1} = (k-1) \cdot k^{n/2-1}\text{.} \end{equation*}If \(n\) is odd, then the same argument works, except that the middle digit will not have a pair. Thus, altogether the number of \(n\)-digit base \(k\) palindrome numbers (for odd \(n\)) is
\begin{equation*} (k-1) \cdot \underbrace{k \cdot \dots \cdot k}_{(n-1)/2} = (k-1) \cdot k^{(n-1)/2}\text{.} \end{equation*} Exercise 2.1.6 There are 44 letters in the Hungarian alphabet, therefore there are \(44^{n}\)-many \(n\) letter long words in Hungarian by Theorem 2.1.4. That is, \(44^5 , 44^7, 44^{10}\)-many \(5, 7, 10\) letter long words can be created, respectively.
-
Exercise 2.1.7 There are three possibilities for every game, there are 14 games, thus the number of required tickets is
\begin{equation*} \underbrace{3 \cdot 3 \cdot \dots \cdot 3}_{14} = 3^{14} = 4~782~969\text{.} \end{equation*} -
Exercise 2.1.8 We apply Theorem 2.1.4. Now, we allow spaces, thus the alphabet contains 27 letters. There are \(27^{20}\) possibilities for a 20 letter long string (name), 2 possibilities for the gender, \(27^{10}\) possibilities for a 10 letter long string (job title), and \(10^8\) possibilities for an at most 8 digit long base 10 number (payment). Thus, the number of possibilities is
\begin{equation*} 27^{20} \cdot 2 \cdot 27^{10} \cdot 10^{8}\text{.} \end{equation*} Exercise 2.2.1 The subsets of \(\halmaz{1, 2, 3}\) are \(\halmaz{} = \emptyset\text{,}\) \(\halmaz{1}\text{,}\) \(\halmaz{2}\text{,}\) \(\halmaz{3}\text{,}\) \(\halmaz{1, 2}\text{,}\) \(\halmaz{1, 3}\text{,}\) \(\halmaz{2, 3}\text{,}\) \(\halmaz{1, 2, 3}\text{.}\) The subsets of \(\halmaz{a, b, c}\) are \(\halmaz{} = \emptyset\text{,}\) \(\halmaz{a}\text{,}\) \(\halmaz{b}\text{,}\) \(\halmaz{c}\text{,}\) \(\halmaz{a, b}\text{,}\) \(\halmaz{a, c}\text{,}\) \(\halmaz{b, c}\text{,}\) \(\halmaz{a, b, c}\text{.}\) The subsets of \(\halmaz{\text{ Alice, Beth, Carrie } }\) are \(\halmaz{} = \emptyset\text{,}\) \(\halmaz{\text{ Alice } }\text{,}\) \(\halmaz{\text{ Beth } }\text{,}\) \(\halmaz{\text{ Carrie } }\text{,}\) \(\halmaz{\text{ Alice, Beth } }\text{,}\) \(\halmaz{\text{ Alice, Carrie } }\text{,}\) \(\halmaz{\text{ Beth, Carrie } }\text{,}\) and finally \(\halmaz{\text{ Alice, Beth, Carrie } }\text{.}\) The subsets of \(\halmaz{apple, banana, cherry}\) are \(\halmaz{} = \emptyset\text{,}\) \(\halmaz{\text{ apple } }\text{,}\) \(\halmaz{\text{ banana } }\text{,}\) \(\halmaz{\text{ cherry } }\text{,}\) \(\halmaz{\text{ apple, banana } }\text{,}\) \(\halmaz{\text{ apple, cherry } }\text{,}\) \(\halmaz{\text{ banana, cherry } }\text{,}\) and \(\halmaz{\text{ apple, banana, cherry } }\text{.}\) All sets have 8 subsets.
Exercise 2.2.4 The set \(\halmaz{a, b, c, d}\) has 16 subsets: \(\halmaz{} = \emptyset\text{,}\) \(\halmaz{a}\text{,}\) \(\halmaz{b}\text{,}\) \(\halmaz{c}\text{,}\) \(\halmaz{d}\text{,}\) \(\halmaz{a, b}\text{,}\) \(\halmaz{a, c}\text{,}\) \(\halmaz{a, d}\text{,}\) \(\halmaz{b, c}\text{,}\) \(\halmaz{b, d}\text{,}\) \(\halmaz{c, d}\text{,}\) \(\halmaz{a, b, c}\text{,}\) \(\halmaz{a, b, d}\text{,}\) \(\halmaz{a, c, d}\text{,}\) \(\halmaz{b, c, d}\text{,}\) \(\halmaz{a, b, c, d}\text{.}\) The set \(\halmaz{a, b, c, d, e}\) has 32 subsets: \(\halmaz{} = \emptyset\text{,}\) \(\halmaz{a}\text{,}\) \(\halmaz{b}\text{,}\) \(\halmaz{c}\text{,}\) \(\halmaz{d}\text{,}\) \(\halmaz{e}\text{,}\) \(\halmaz{a, b}\text{,}\) \(\halmaz{a, c}\text{,}\) \(\halmaz{a, d}\text{,}\) \(\halmaz{a, e}\text{,}\) \(\halmaz{b, c}\text{,}\) \(\halmaz{b, d}\text{,}\) \(\halmaz{b, e}\text{,}\) \(\halmaz{c, d}\text{,}\) \(\halmaz{c, e}\text{,}\) \(\halmaz{d, e}\text{,}\) \(\halmaz{a, b, c}\text{,}\) \(\halmaz{a, b, d}\text{,}\) \(\halmaz{a, b, e}\text{,}\) \(\halmaz{a, c, d}\text{,}\) \(\halmaz{a, c, e}\text{,}\) \(\halmaz{a, d, e}\text{,}\) \(\halmaz{b, c, d}\text{,}\) \(\halmaz{b, c, e}\text{,}\) \(\halmaz{b, d, e}\text{,}\) \(\halmaz{c, d, e}\text{,}\) \(\halmaz{a, b, c, d}\text{,}\) \(\halmaz{a, b, c, e}\text{,}\) \(\halmaz{a, b, d, e}\text{,}\) \(\halmaz{a, c, d, e}\text{,}\) \(\halmaz{b, c, d, e}\text{,}\) \(\halmaz{a, b, c, d, e}\text{.}\)
Exercise 2.2.6 The decision algorithm is collected in the following table (\(T\) is the subset of \(S = \halmaz{a, b, c}\)):
First we decide whether or not \(a \in T\text{,}\) then (independently on our first choice) we decide whether or not \(b \in T\text{,}\) then (independently on our earlier choices) we decide whether or not \(c \in T\text{.}\) That way, we obtain \(2 \cdot 2 \cdot 2 = 8\) subsets.\(a \in T\) \(a \notin T\) \(b \in T\) \(b \notin T\) \(b \in T\) \(b \notin T\) \(c \in T\) \(c \notin T\) \(c \in T\) \(c \notin T\) \(c \in T\) \(c \notin T\) \(c \in T\) \(c \notin T\) \(\halmaz{a, b, c}\) \(\halmaz{a, b}\) \(\halmaz{a, c}\) \(\halmaz{a}\) \(\halmaz{b, c}\) \(\halmaz{b}\) \(\halmaz{c}\) \(\halmaz{} = \emptyset\) Exercise 2.2.7 There are 8 subsets of \(\halmaz{a, b, c, d}\) not containing \(d\text{:}\) \(\halmaz{} = \emptyset\text{,}\) \(\halmaz{a}\text{,}\) \(\halmaz{b}\text{,}\) \(\halmaz{c}\text{,}\) \(\halmaz{a, b}\text{,}\) \(\halmaz{a, c}\text{,}\) \(\halmaz{b, c}\text{,}\) \(\halmaz{a, b, c}\text{.}\) These are the subsets of \(\halmaz{a, b, c}\text{.}\) There are 8 subsets of \(\halmaz{a, b, c, d}\) containing \(d\text{:}\) \(\halmaz{d}\text{,}\) \(\halmaz{a, d}\text{,}\) \(\halmaz{b, d}\text{,}\) \(\halmaz{c, d}\text{,}\) \(\halmaz{a, b, d}\text{,}\) \(\halmaz{a, c, d}\text{,}\) \(\halmaz{b, c, d}\text{,}\) \(\halmaz{a, b, c, d}\text{.}\) These are the subsets of \(\halmaz{a, b, c}\) with the element \(d\) added to them.
Exercise 2.2.8 The binary representation of the subsets of \(\halmaz{a, b, c, d}\) can be seen in Table 6.2.1 on page 6.2.1.
subset of \(\halmaz{a, b, c, d}\) binary number decimal number \(\halmaz{}\) \(0000_2\) 0 \(\halmaz{a}\) \(0001_2\) 1 \(\halmaz{b}\) \(0010_2\) 2 \(\halmaz{a, b}\) \(0011_2\) 3 \(\halmaz{c}\) \(0100_2\) 4 \(\halmaz{a, c}\) \(0101_2\) 5 \(\halmaz{b, c}\) \(0110_2\) 6 \(\halmaz{a, b,c }\) \(0111_2\) 7 \(\halmaz{d}\) \(1000_2\) 8 \(\halmaz{a, d}\) \(1001_2\) 9 \(\halmaz{b, d}\) \(1010_2\) 10 \(\halmaz{a, b, d}\) \(1011_2\) 11 \(\halmaz{c, d}\) \(1100_2\) 12 \(\halmaz{a, c, d}\) \(1101_2\) 13 \(\halmaz{b, c, d}\) \(1110_2\) 14 \(\halmaz{a, b, c, d}\) \(1111_2\) 15 Table6.2.1Subsets of \(\halmaz{a, b, c, d}\) represented as binary numbers Exercise 2.2.9 After computing the binary representation, we just add the elements corresponding to the places where the digits are 1.
decimal number binary number subset of \(S\) 11 \(1011_2\) \(\halmaz{a_0, a_1, a_3}\) 7 \(0111_2\) \(\halmaz{a_0, a_1, a_2}\) 15 \(1111_2\) \(\halmaz{a_0, a_1, a_2, a_3}\) Exercise 2.2.10 After computing the binary representation, we just add the elements corresponding to the places where the digits are 1.
Note, that the encoding was defined in such a way, that the subset of \(\halmaz{a_0, a_1, a_2, a_3}\) corresponding to \(k\) is the same as the subset of \(\halmaz{a_0, a_1, a_2, a_3, a_4}\) corresponding to \(k\) (for arbitrary \(0\leq k\leq 15\)).decimal number binary number subset of \(S\) 11 \(01011_2\) \(\halmaz{a_0, a_1, a_3}\) 7 \(00111_2\) \(\halmaz{a_0, a_1, a_2}\) 15 \(01111_2\) \(\halmaz{a_0, a_1, a_2, a_3}\) 16 \(10000_2\) \(\halmaz{a_4}\) 31 \(11111_2\) \(\halmaz{a_0, a_1, a_2, a_3, a_4}\) Exercise 2.2.11 After computing the binary representation, we just add the elements corresponding to the places where the digits are 1.
decimal number binary number subset of \(S\) 49 \(110001_2\) \(\halmaz{a_0, a_4, a_5}\) Exercise 2.2.12 After computing the binary representation, we just add the elements corresponding to the places where the digits are 1.
decimal number binary number subset of \(S\) 101 \(1100101_2\) \(\halmaz{a_0, a_2, a_5, a_6}\) Exercise 2.2.13 After computing the binary representation, we just add the elements corresponding to the places where the digits are 1.
decimal number binary number subset of \(S\) 199 \(11000111_2\) \(\halmaz{a_0, a_1, a_2, a_6, a_7}\) Exercise 2.3.2 All possibilities are listed in Table 6.2.2 on page 6.2.2.
first second third fourth Ed Frank George Hugo Ed Frank Hugo George Ed George Frank Hugo Ed George Hugo Frank Ed Hugo Frank George Ed Hugo George Frank Frank Ed George Hugo Frank Ed Hugo George Frank George Ed Hugo Frank George Hugo Ed Frank Hugo Ed George Frank Hugo George Ed George Ed Frank Hugo George Ed Hugo Frank George Frank Ed Hugo George Frank Hugo Ed George Hugo Ed Frank George Hugo Frank Ed Hugo Ed Frank George Hugo Ed George Frank Hugo Frank Ed George Hugo Frank George Ed Hugo George Ed Frank Hugo George Frank Ed Table6.2.2The orders in which Ed, Frank, George and Hugo can take the exam Exercise 2.3.4 The number of permutations of \(\halmaz{1, 2, 3, 4}\) is \(4! =24\text{.}\)
Exercise 2.3.5 The number of permutations of \(\halmaz{a, b, c, d}\) is \(4! =24\text{.}\)
Exercise 2.3.6 The number of permutations of 8 people is \(8! = 40~320\text{.}\) If the boys sit on seats from 1 to 5, and girls sit on seats from 6 to 8, then we need to count the number of permutations of the boys and girls separately. The boys can sit on their seats in \(5! = 120\)-many ways. The girls (independently on how the boys sit) can sit on their seats in \(3! = 6\)-many ways. Altogether, they can sit in \(6 \cdot 120 = 720\)-many ways.
Exercise 2.4.1 The number of anagrams of ‘retinas’ is the same as the number of permutations of the letters ‘r’, ‘e’, ‘t’, ‘i’, ‘n’, ‘a’ and ‘s’. There are 7 different letters, hence the number of permutations is \(7! = 5~040\text{.}\)
Exercise 2.4.3 Again, let us color the ‘p’s in the anagrams by three colors: red, green, blue. This way, there will be \(5!=120\)-many coloured anagrams of puppy, the same as the number of permutations of five different elements. Now, group together those anagrams, which only differ by their colouring. For example the group ‘puppy’ would contain ‘puppy’, ‘puppy’, ‘puppy’, ‘puppy’, ‘puppy’, ‘puppy’. How do we know that there are six coloured ‘puppy’s? The coloured ‘puppy’s only differ in the colourings of the ‘p’s. The first ‘p’ can be coloured by 3 different colours, the next ‘p’ (right after the ‘u’) can be coloured by two different colours (it cannot be coloured by the same colour as the first ‘p’), then the last ‘p’ should be coloured by the remaining colour. Thus, there are \(3 \cdot 2 \cdot 1 = 6\)-many coloured ‘puppy’s. Similarly, there are 6 coloured versions of every anagram. Therefore there are \(\frac{120}{6} = 20\) (uncoloured) anagrams of ‘puppy’. These are ‘pppuy’, ‘pppyu’, ‘ppupy’, ‘ppypu’, ‘ppuyp’, ‘ppyup’, ‘puppy’, ‘pyppu’, ‘pupyp’, ‘pypup’, ‘puypp’, ‘pyupp’, ‘upppy’, ‘ypppu’, ‘uppyp’, ‘yppup’, ‘upypp’, ‘ypupp’, ‘uyppp’, ‘yuppp’.
-
-
The word ‘college’ contains 7 letters, two of them are ‘e’s and two of them are ‘l’s, thus the number of anagrams is
\begin{equation*} \frac{7!}{2! \cdot 2!} = \frac{5~040}{2 \cdot 2} = 1~260\text{.} \end{equation*} -
The word ‘discrete’ contains 8 letters, two of them are ‘e’s, thus the number of anagrams is
\begin{equation*} \frac{8!}{2!} = \frac{40~320}{2} = 20~160\text{.} \end{equation*} -
The word ‘mathematics’ contains 11 letters, two of them are ‘a’s, two of them are ‘m’s and two of them are ‘t’s, thus the number of anagrams is
\begin{equation*} \frac{11!}{2! \cdot 2! \cdot 2!} = \frac{39~916~800}{2 \cdot 2 \cdot 2} = 4~989~600\text{.} \end{equation*} -
The expression ‘discrete mathematics’ contains 19 letters, two of them are ‘i’s, two of them are ‘s’s, two of them are ‘c’s, three of them are ‘e’s, three of them are ‘t’s, two of them are ‘m’s and two of them are ‘a’s, thus the number of anagrams is
\begin{align*} \frac{19!}{2! \cdot 2! \cdot 2! \cdot 3! \cdot 3! \cdot 2! \cdot 2!} \amp = \frac{121~645~100~408~832~000}{2 \cdot 2 \cdot 2 \cdot 6 \cdot 6 \cdot 2 \cdot 2}\\ \amp = 105~594~705~216~000\text{.} \end{align*} -
The expression ‘college discrete mathematics’ contains 26 letters, three of them are ‘c’s, two of them are ‘l’s, five of them are ‘e’s, two of them are ‘i’s, two of them are ‘s’s, three of them are ‘t’s, two of them are ‘m’s and two of them are ‘a’s, thus the number of anagrams is
\begin{align*} \frac{26!}{3! \cdot 2! \cdot 5! \cdot 2! \cdot 2! \cdot 3! \cdot 2! \cdot 2!} \amp = \frac{403~291~461~126~605~635~584~000~000}{6 \cdot 2 \cdot 120 \cdot 2 \cdot 2 \cdot 6 \cdot 2 \cdot 2}\\ \amp = 2~917~328~277~825~561~600~000\text{.} \end{align*}
-
-
Exercise 2.4.6 First solution. Let us create the (not meaningful) word ‘aaaaabbbbccc’, and consider its anagrams. Put the bouquets into one particular order, and consider an anagram. This anagram represents a distribution of the bouquets among the triplets: if a letter is ‘a’ in the anagram, the corresponding bouquet will be taken by Alice, if a letter is ‘b’ in the anagram, the corresponding bouquet will be taken by Beth, if a letter is ‘c’ in the anagram, the corresponding bouquet will be taken by Carrie. For example, the distribution for the anagram ‘abcbbaaaccba’ is that Alice takes the first, sixth, seventh, eighth and twelfth bouquets, Beth takes the second, fourth, fifth and eleventh bouquets, and Carrie takes the third, ninth and tenth bouquets. This gives a one-to-one correspondence between the possible distributions of the bouquets and the anagrams of ‘aaaaabbbbccc’. Therefore by Theorem 2.4.4 the number of distributions is
\begin{equation*} \frac{12!}{5! \cdot 4! \cdot 3!} = \frac{479~001~600}{120 \cdot 24 \cdot 6} = 27~720\text{.} \end{equation*}Second solution. Imagine that the triplets put the 12 bouquets in some order, and then Alice takes the first 5, Beth takes the next four, and Carrie takes the last three. Thus, the original order of the bouquets determine who gets which bouquet. Of course, some of these orders give the same result: if we only permute the first five elements or the next four elements, or the final three elements, then clearly everyone obtains exactly the same bouquets. Thus, the number of possible distributions is the number of permutations of the 12 bouquets, divided by the number of permutations of the first five elements, the number of permutations of the next four elements, the number of permutations of the last three elements. That is, the number of possible distributions is
\begin{equation*} \frac{12!}{5! \cdot 4! \cdot 3!} = \frac{479~001~600}{120 \cdot 24 \cdot 6} = 27~720\text{.} \end{equation*} -
Exercise 2.5.1 The two numbers are equal, as the following calculation shows
\begin{equation*} \frac{22!}{16!} = \frac{22 \cdot 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17 \cdot 16!}{16!} = 22 \cdot 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17\text{.} \end{equation*} -
Exercise 2.5.3 Altogether there are \(n!\) possible orders for the \(n\) elements (this is the number of permutations of \(n\) elements). But not all of these are considered to be different, because we are only interested in the first \(k\) elements. Those cases will be considered the same where the first \(k\) elements are the same (and in the same order). That is, we group together those permutations of the \(n\) elements, where the order of the first \(k\) elements is the same. We can name every group with the order of the first \(k\) elements. Thus, we are interested in the number of groups we have. In one group there are those permutations, where the order of the first \(k\) elements is the same, thus they only differ in the last \((n-k)\) elements. There are \((n-k)!\) possible permutations of the last \((n-k)\) elements, therefore every group contains \((n-k)!\) orderings of the \(n\) elements. Hence, the number of ordered \(k\)-element subsets is
\begin{align*} \frac{n!}{(n-k)!} \amp = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+1) \cdot (n-k)!}{(n-k)!}\\ \amp = n \cdot (n-1) \cdot \dots \cdot (n-k+1)\text{.} \end{align*} -
Exercise 2.5.4 By Theorem 2.5.2 the number of possibilities
-
for the first eight cars is
\begin{equation*} 22 \cdot 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15 = 12~893~126~400\text{,} \end{equation*} -
for the first ten cars is
\begin{equation*} 22 \cdot 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 = 2~346~549~004~800\text{.} \end{equation*}
-
-
Exercise 2.5.5 By Theorem 2.5.2 the number of ordered subsets is
- \begin{equation*} 10 \cdot 9 \cdot 8 = 720\text{,} \end{equation*}
- \begin{equation*} 12 \cdot 11 \cdot 10 = 1~320\text{,} \end{equation*}
- \begin{equation*} 10 \cdot 9 \cdot 8 \cdot 7 = 5~040\text{,} \end{equation*}
- \begin{equation*} 12 \cdot 11 \cdot 10 \cdot 9 = 11~880\text{,} \end{equation*}
- \begin{equation*} 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 6~720\text{,} \end{equation*}
- \begin{equation*} 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6= 30~240\text{.} \end{equation*}
-
Exercise 2.6.1 The two numbers are equal, as the following calculation shows
\begin{equation*} \frac{90!}{5! \cdot 85!} = \frac{90 \cdot 89 \cdot 88 \cdot 87 \cdot 86 \cdot 85!}{5! \cdot 85!} = \frac{90 \cdot 89 \cdot 88 \cdot 87 \cdot 86}{5!}\text{.} \end{equation*} Exercise 2.6.3 The required binomial coefficients are computed and arranged into a triangle in Table 6.2.3 on page 6.2.3.
\(\binom{0}{0} = 1\) \(\binom{1}{0} = 1\) \(\binom{1}{1} = 1\) \(\binom{2}{0} = 1\) \(\binom{2}{1} = 2\) \(\binom{2}{2} = 1\) \(\binom{3}{0} = 1\) \(\binom{3}{1} = 3\) \(\binom{3}{2} = 3\) \(\binom{3}{3} = 1\) \(\binom{4}{0} = 1\) \(\binom{4}{1} = 4\) \(\binom{4}{2} = 6\) \(\binom{4}{3} = 4\) \(\binom{4}{4} = 1\) \(\binom{5}{0} = 1\) \(\binom{5}{1} = 5\) \(\binom{5}{2} = 10\) \(\binom{5}{3} = 10\) \(\binom{5}{4} = 5\) \(\binom{5}{5} = 1\) \(\binom{6}{0} = 1\) \(\binom{6}{1} = 6\) \(\binom{6}{2} = 15\) \(\binom{6}{3} = 20\) \(\binom{6}{4} = 15\) \(\binom{6}{5} = 6\) \(\binom{6}{6} = 1\) Table6.2.3Small binomial coefficients. -
Exercise 2.6.6 By the definition
\begin{align*} \binom{n}{0} \amp = \frac{n!}{0! \cdot (n-0)!} = \frac{n!}{0! \cdot n!} = \frac{1}{0!} = \frac{1}{1} = 1,\\ \binom{n}{1} \amp = \frac{n!}{1! \cdot (n-1)!} = \frac{n \cdot (n-1)!}{1! \cdot (n-1)!} = \frac{n}{1!} = \frac{n}{1} = n,\\ \binom{n}{2} \amp = \frac{n!}{2! \cdot (n-2)!} = \frac{n \cdot (n-1) \cdot (n-2)!}{2! \cdot (n-2)!} = \frac{n \cdot (n-1)}{2!} = \frac{n \cdot (n-1)}{2},\\ \binom{n}{n-2} \amp = \frac{n!}{(n-2)! \cdot (n-(n-2))!} = \frac{n \cdot (n-1) \cdot (n-2)!}{(n-2)! \cdot 2!} = \frac{n \cdot (n-1)}{2!}\\ \amp = \frac{n \cdot (n-1)}{2},\\ \binom{n}{n-1} \amp = \frac{n!}{(n-1)! \cdot (n-(n-1))!} = \frac{n \cdot (n-1)!}{(n-1)! \cdot 1!} = \frac{n}{1!} = \frac{n}{1} = n,\\ \binom{n}{n} \amp = \frac{n!}{n! \cdot (n-n)!} = \frac{n!}{n! \cdot 0!} = \frac{1}{0!} = \frac{1}{1} = 1\text{.} \end{align*} -
Exercise 2.6.8 Using Table 6.2.3 from Exercise 2.6.3, it is not hard to determine the required sums:
\begin{align*} \sum_{k=0}^0 \binom{0}{k} \amp = \binom{0}{0} = 1,\\ \sum_{k=0}^1 \binom{1}{k} \amp = \binom{1}{0} + \binom{1}{1} = 1 + 1 = 2,\\ \sum_{k=0}^2 \binom{2}{k} \amp = \binom{2}{0} + \binom{2}{1} + \binom{2}{2} = 1 + 2 + 1 = 4,\\ \sum_{k=0}^3 \binom{3}{k} \amp = \binom{3}{0} + \binom{3}{1} + \binom{3}{2} + \binom{3}{3} = 1 + 3 + 3 + 1 = 8,\\ \sum_{k=0}^4 \binom{4}{k} \amp = \binom{4}{0} + \binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4}\\ \amp = 1 + 4 + 6 + 4 + 1 = 16,\\ \sum_{k=0}^5 \binom{5}{k} \amp = \binom{5}{0} + \binom{5}{1} + \binom{5}{2} + \binom{5}{3} + \binom{5}{4} + \binom{5}{5}\\ \amp = 1 + 5 + 10 + 10 + 5 + 1 = 32,\\ \sum_{k=0}^6 \binom{6}{k} \amp = \binom{6}{0} + \binom{6}{1} + \binom{6}{2} + \binom{6}{3} + \binom{6}{4} + \binom{6}{5} + \binom{6}{6}\\ \amp = 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64\text{.} \end{align*} -
Exercise 2.6.10 Now, \(n\) divides \(\binom{n}{2}\) if and only if the quotient \(\binom{n}{2} / n\) is an integer. Here
\begin{equation*} \frac{\binom{n}{2}}{n} = \frac{\frac{n\cdot (n-1)}{2}}{n} = \frac{n-1}{2}\text{,} \end{equation*}and this is an integer number if and only if \(2 \nmid n\text{,}\) that is, if and only if \(n\) is odd.
-
Exercise 2.6.11 Using the formula for \(\binom{n+1}{2}\) and \(\binom{n}{2}\) we have
\begin{align*} \binom{n+1}{2} + \binom{n}{2} \amp = \frac{(n+1) \cdot n}{2} + \frac{n \cdot (n-1)}{2} = \frac{n^2+n}{2} + \frac{n^2-n}{2}\\ \amp = \frac{n^2 + n + n^2 -n }{2} = \frac{2n^2}{2} = n^2\text{.} \end{align*} Exercise 2.7.3 Let the pirates be \(P_1, \dots , P_n\text{.}\) They put the gold pieces in a line. Then they want to divide it into \(n\) parts by putting sticks between gold pieces. The leftmost part will go to \(P_1\text{,}\) the next part from left goes to \(P_2\text{,}\) etc. The rightmost part will go to \(P_n\text{.}\) To this end, they use \(n-1\) sticks to divide the \(k\) gold pieces into \(n\) parts. What is left from the first stick is for \(P_1\text{,}\) what is between the first and second sticks is for \(P_2\text{,}\) etc., and everything right from the last stick is taken by \(P_n\text{.}\) They can put the sticks between gold pieces. They cannot put a stick before the first gold piece, because then \(P_1\) would not get any pieces. Similarly, they cannot put a stick after the last gold piece, because \(P_n\) needs to receive at least one gold piece. Finally, they cannot put two sticks between the same two gold pieces, because then one of the pirates would not get any gold piece. Thus, they need to put \(n-1\) sticks somewhere in the spaces between the gold pieces, but they cannot put two sticks between the same two gold pieces. That is, they need to find which \(n-1\) places they put sticks to. There are \(k-1\) places between \(k\) gold pieces, and they need to find \(n-1\text{,}\) where they put the \(n-1\) sticks. This can be done in \(\binom{k-1}{n-1}\)-many ways.
Exercise 2.7.6 Let every pirate take one gold piece right at the very beginning. Then there remains \(k-n\) gold pieces to further distribute. Moreover, now every pirate needs one more gold piece. Thus we reduced the problem to the one solved in Theorem 2.7.2: \(n\) pirates want to distribute \(k-n\) gold pieces such that everyone gets at least one gold piece. By Theorem 2.7.2 this can be done in \(\binom{k-n-1}{n-1}\)-many ways.
Exercise 2.7.9 All 15 possibilities are written in Table 6.2.4 on page 6.2.4.
Anne Bonney Black Bellamy Calico Jack 4 1 2 0 5 2 0 1 6 3 2 2 3 1 3 1 4 2 0 4 3 1 1 5 0 2 5 2 3 2 2 1 4 0 3 4 2 2 3 1 3 3 1 2 4 Table6.2.4Possibilities to distribute seven gold pieces among three pirates such that Black Bellamy gets at least one gold piece and Calico Jack gets at least two gold pieces. -
Exercise 2.7.11 By applying Theorem 2.7.10, we obtain
- \begin{equation*} \binom{9 - 1}{3 - 1} = \binom{8}{2} = 28\text{,} \end{equation*}
- \begin{equation*} \binom{8+3 - 1}{3 - 1} = \binom{10}{2} = 45\text{,} \end{equation*}
- \begin{equation*} \binom{7+3 - 1}{3 - 1} = \binom{9}{2} = 36\text{,} \end{equation*}
- \begin{equation*} \binom{11-3 - 1}{3 - 1} = \binom{7}{2} = 21\text{,} \end{equation*}
- \begin{equation*} \binom{9 - 1}{4 - 1} = \binom{8}{3} = 56\text{,} \end{equation*}
- \begin{equation*} \binom{7+4 - 1}{4 - 1} = \binom{10}{3} = 120\text{,} \end{equation*}
- \begin{equation*} \binom{12-4 - 1}{4 - 1} = \binom{7}{3} = 35\text{,} \end{equation*}
- \begin{equation*} \binom{10 -1 -2 -3 +4 - 1}{4 - 1} = \binom{7}{3} = 35\text{,} \end{equation*}
- \begin{equation*} \binom{15 -1 -2 -3 -4+4 - 1}{4 - 1} = \binom{8}{3} = 56\text{,} \end{equation*}
- \begin{equation*} \binom{15 -1 -1 -3 -3+5 - 1}{5 - 1} = \binom{11}{4} = 330\text{.} \end{equation*}
-
Exercise 2.7.14 By applying Corollary 2.7.13, we obtain that the number of solutions is
- \begin{equation*} \binom{9 - 1}{3 - 1} = \binom{8}{2} = 28\text{,} \end{equation*}
- \begin{equation*} \binom{8+3 - 1}{3 - 1} = \binom{10}{2} = 45\text{,} \end{equation*}
- \begin{equation*} \binom{7+3 - 1}{3 - 1} = \binom{9}{2} = 36\text{,} \end{equation*}
- \begin{equation*} \binom{11-3 - 1}{3 - 1} = \binom{7}{2} = 21\text{,} \end{equation*}
- \begin{equation*} \binom{9 - 1}{4 - 1} = \binom{8}{3} = 56\text{,} \end{equation*}
- \begin{equation*} \binom{7+4 - 1}{4 - 1} = \binom{10}{3} = 120\text{,} \end{equation*}
- \begin{equation*} \binom{12-4 - 1}{4 - 1} = \binom{7}{3} = 35\text{,} \end{equation*}
- \begin{equation*} \binom{10 -1 -2 -3 +4 - 1}{4 - 1} = \binom{7}{3} = 35\text{,} \end{equation*}
- \begin{equation*} \binom{15 -1 -2 -3 -4+4 - 1}{4 - 1} = \binom{8}{3} = 56\text{,} \end{equation*}
- \begin{equation*} \binom{15 -1 -1 -3 -3+5 - 1}{5 - 1} = \binom{11}{4} = 330\text{.} \end{equation*}
Exercise 2.7.15 It is the same problem as the gold distribution: imagine that everybody of the three siblings gets the brand they like. Then the problem is equivalent to distributing 10 desserts among the three children such that everyone gets at least one. There are \(\binom{10-1}{3-1} = \binom{9}{2} = 45\)-many ways to do this by Theorem 2.7.10.
-
Exercise 2.8.3 Applying Table 2.8.2 we obtain that the number of choices is
- \begin{equation*} \binom{9 + 3 -1}{3} = \binom{11}{3} = 165\text{,} \end{equation*}
- \begin{equation*} \binom{9 + 3 -1}{9} = \binom{11}{9} = 55\text{,} \end{equation*}
- \begin{equation*} \frac{10!}{5!} = 30~240\text{,} \end{equation*}
- \begin{equation*} 0\text{,} \end{equation*}
- \begin{equation*} \binom{45}{6} = 8~145~060\text{,} \end{equation*}
- \begin{equation*} 0\text{,} \end{equation*}
- \begin{equation*} 100^{10} = 10^{20}\text{,} \end{equation*}
- \begin{equation*} 10^{100}\text{.} \end{equation*}