12.25
Exercise 1
We draw in a plane \(n \geq 3\) lines in general position (that is to say that two lines are never parallel, and three lines are never concurrent). How many triangles have we thus drawn?
\(\binom{n}{3}\)
Exercise 2
A company has 18 employees, 8 of whom are women. For a survey, 3 people are chosen at random. What is the number of samples that include at least 2 men?
\(\binom81\cdot\binom{10}{2}+\binom{10}{3}\)
Exercise 3
Let \(A\) be the set of 7-digit numbers that do not contain any "1". Determine the number of elements in the following sets:
- (a) \(A\).
\(\binom81\cdot\binom91^6\) * (b) \(A_1\), set of numbers in \(A\) that have 7 different digits.
\(\binom81\cdot\binom81\cdot\binom71\cdot\binom61\cdot\binom51\cdot\binom41\cdot\binom31\) * (c) \(A_2\), set of even numbers in \(A\).
\(\binom81\cdot\binom91^5\cdot\binom51\) * (d) \(A_3\), set of numbers in \(A\) whose digits form a strictly increasing sequence (in the order they are written).
We have \(\{2,3,4,5,6,7,8,9\}\), then we just choose \(7\) digit from \(8\), which is \(\binom87\)
Exercise 4
Consider a set \(X\) of \(n + 1\) (distinct) integers chosen from \(\{1, \ldots, 2n\}\). Show that among the elements of \(X\), we can always find 2 integers whose sum is \(2n + 1\).
Proof
If the sum of 2 integers is \(2n + 1\), then the possibilities is \(P_1=\{1,2n\},P_2=\{2,2n-1\},...,P_n=\{n,n+1\}\)
Since we have \(n\) possibilities and we have \(n+1\) integers, then by pigeonhole theorem there is at least \(2\) integers in the same pair, then there sum is \(2n+1\)
Exercise 5
Solve the following two equations, with unknown \(n \in \mathbb{N}\):
- (a) \(4 \binom{n}{8} = \binom{n}{9}\), with \(n \geq 9\).
\(\frac{4\cdot n!}{\left(n-8\right)!8!}-\frac{n!}{\left(n-9\right)!9!}=\frac{4\cdot n!\cdot9-n!\cdot\left(n-8\right)}{\left(n-8\right)!9!}=\frac{n!\left(44-n\right)}{\left(n-8\right)!9!}=0\Rightarrow n=44\) * (b) \(\binom{3n}{1} + \binom{3n}{2} + \binom{3n}{3} = 115n\), with \(n \geq 1\).
\(\frac{3n!}{\left(3n-1\right)!}+\frac{3n!}{\left(3n-2\right)!2!}+\frac{3n!}{\left(3n-3\right)!3!}=115n\Rightarrow3n+\frac{3n\left(3n-1\right)}{2}+\frac{3n\left(3n-1\right)\left(3n-2\right)}{6}=115n\)
Then \(9n^2=225\Rightarrow n=5\)
Exercise 6
Let \(E\) be the 12-element set \(\{a, b, c, d, e, f, g, h, i, j, k, l\}\).
-
(a) Count the 5-element parts of \(E\) that contain:
-
(i) \(a\) and \(b\);
\(\binom{10}{3}\) * (ii) \(a\) but not \(b\);
\(\binom{10}{4}\) * (iii) \(b\) but not \(a\);
\(\binom{10}{4}\) * (iv) neither \(a\) nor \(b\).
\(\binom{10}{5}\) * (b) Deduce the relation \(\binom{12}{5} = \binom{10}{3} + 2 \binom{10}{4} + \binom{10}{5}\).
Yes * (c) Generalize the result obtained by proving, by counting, that for \(2 \leq p \leq n\), we have \(\binom{n}{p} = \binom{n-2}{p-2} + 2 \binom{n-2}{p-1} + \binom{n-2}{p}\).
...... * (d) Find the previous result by applying Pascal’s triangle formula: \(\binom{n}{p} = \binom{n-1}{p} + \binom{n-1}{p-1}\), for \(1 \leq p \leq n-1\).
\(\binom{n-2}{p-2}+\binom{n-2}{p-1}+\binom{n-2}{p-1}+\binom{n-2}{p}=\binom{n-1}{p-1}+\binom{n-1}{p}=\binom{n}{p}\).
Exercise 7
Let \(1 \leq p \leq n\). Consider \(n\) balls and two boxes \(A\) and \(B\). A sample consists of one ball in box \(A\) and \(p-1\) balls in box \(B\). By counting these samples in two different ways, establish the formula: \(n \binom{n-1}{p-1} = p \binom{n}{p}\). Find this formula by a computation.
On one hand, First we choose one ball from \(n\) to put into \(A\), then we have \(n\) possibilities
Then there are \(n-1\) balls and we need to put \(p-1\) balls into \(B\), which is \(\binom{n-1}{p-1}\)
Then all the possibilities is \(n\binom{n-1}{p-1}\)
On another hand, First we choose \(p\) balls from \(n\) balls, which is \(\binom{n}{p}\).
Then we choose one ball into \(A\) from it which is \(p\) possibilities, then put the remaining into \(B\)
Then the all possibilities is \(p\binom{n}{p}\)
Exercise 8
A book has 14 chapters.
- (a) How many ways are there to choose 3 chapters in this book?
\(\binom{14}{3}\) * (b) For \(k = 3, \ldots, 14\), count the choices of 3 chapters for which \(k\) is the largest number of the chosen chapters.
\(\binom{k-1}{2}\) * (c) Deduce that \(\binom{14}{3} = \binom{13}{2} + \binom{12}{2} + \cdots + \binom{3}{2} + \binom{2}{2}\).
\(k=3,...,14\)
The sum of the largest \(k\) cases
* (d) Generalize the previous counts to show that, for \(1 \leq p \leq n\), we have:
\(\sum_{k=p}^{n} \binom{k}{p} = \binom{n+1}{p+1}\)
\(\sum_{k=p}^{n}\binom{k}{p}=\sum_{k=p}^{n}\left(\binom{k+1}{p+1}-\binom{k}{p+1}\right)=\binom{p+1}{p+1}-\binom{p}{p+1}+\binom{p+2}{p+1}-\binom{p+1}{p+1}+\binom{p+3}{p+1}-\binom{p+2}{p+1}+\cdots+\binom{n}{p+1}-\binom{n-1}{p+1}+\binom{n+1}{p+1}-\binom{n}{p+1}\)
\(\sum_{k=p}^{n}\binom{k}{p}=-\binom{p}{p+1}+\binom{n+1}{p+1}=\binom{n+1}{p+1}\) * (e) Notice that for \(k > p\), we have \(\binom{k}{p} = \binom{k+1}{p+1} - \binom{k}{p+1}\). Use this to prove the previous formula.
Above
Exercise 9 (⋆)
Let \(p, q, m\) be natural integers, with \(q \leq p \leq m\). Prove by counting that: \(\binom{m}{p} = \sum_{j=0}^{q} \binom{q}{j} \binom{m-q}{p-j}\)
We need to choose \(p\) objects from \(m\) objects. On the left hand, we choose directly.
On the right hand, we first separate \(m\) objects into Box A which has \(q\) objects and Box B which has \(m-q\) objects
Then we can choose \(j\) objects from A which is \(\binom{q}{j}\), then we can choose the remaining \(p-j\) objects from \(B\) which is \(\binom{m-q}{p-j}\)
Then for one particular \(j\) we have \(\binom{q}{j}\binom{m-q}{p-j}\), then \(j\) can take from \(0\) to \(q\) which is \(\sum_{j=0}^{q}\binom{q}{j}\binom{m-q}{p-j}\)
Exercise 10 (⋆)
In my house, there is a staircase with 17 steps. To go down this staircase, I can go down one step at a time, down two steps, or down three steps at a time. How many ways are there to go down this staircase?
Method 1
Combinatorial Enumeration Approach
Step 1: Define Variables
Let’s denote:
- x \= number of 1-step moves
- y \= number of 2-step moves
- z \= number of 3-step moves
These variables must satisfy the equation:
\(x + 2y + 3z = 17\)where \(x, y, z \geq 0\) are integers.
Step 2: Find All Possible (y, z) Combinations
We'll iterate through all possible values of \(z\) (since taking 3 steps reduces the remaining steps more quickly) and, for each \(z\), find the corresponding \(y\) and \(x\).
-
For \(z = 0\) :
\(x + 2y = 17\)- \(y\) can range from 0 to 8 (since \(2 \times 8 = 16\), leaving \(x = 1\))
-
For \(z = 1\) :
\(x + 2y = 14\)- \(y\) can range from 0 to 7
-
For \(z = 2\) :
\(x + 2y = 11\)- \(y\) can range from 0 to 5
-
For \(z = 3\) :
\(x + 2y = 8\)- \(y\) can range from 0 to 4
-
For \(z = 4\) :
\(x + 2y = 5\)- \(y\) can range from 0 to 2
-
For \(z = 5\) :
\(x + 2y = 2\)- \(y\) can range from 0 to 1
Any higher value of \(z\) would make \(x\) negative, which is not possible.
Step 3: Calculate Permutations for Each Combination
For each valid combination of \(x, y, z\), the number of distinct ways to arrange these steps is given by the multinomial coefficient:
\(\text{Number of ways} = \frac{(x + y + z)!}{x! \cdot y! \cdot z!}\)Let's compute this for each \(z\) and corresponding \(y\):
1. \(z = 0\) : \(x + 2y = 17\)
| \(y\) | \(x = 17 - 2y\) | Total Steps (\(x + y\)) | Permutations\(\frac{(x+y)!}{x!y!}\) |
|---|---|---|---|
| 0 | 17 | 17 | \(\frac{17!}{17!0!} = 1\) |
| 1 | 15 | 16 | \(\frac{16!}{15!1!} = 16\) |
| 2 | 13 | 15 | \(\frac{15!}{13!2!} = 105\) |
| 3 | 11 | 14 | \(\frac{14!}{11!3!} = 364\) |
| 4 | 9 | 13 | \(\frac{13!}{9!4!} = 715\) |
| 5 | 7 | 12 | \(\frac{12!}{7!5!} = 792\) |
| 6 | 5 | 11 | \(\frac{11!}{5!6!} = 462\) |
| 7 | 3 | 10 | \(\frac{10!}{3!7!} = 120\) |
| 8 | 1 | 9 | \(\frac{9!}{1!8!} = 9\) |
Subtotal for \(z = 0\) :
\(1 + 16 + 105 + 364 + 715 + 792 + 462 + 120 + 9 = 2,584\)
2. \(z = 1\) : \(x + 2y = 14\)
| \(y\) | \(x = 14 - 2y\) | Total Steps (\(x + y + 1\)) | Permutations\(\frac{(x+y+1)!}{x!y!1!}\) |
|---|---|---|---|
| 0 | 14 | 15 | \(\frac{15!}{14!0!1!} = 15\) |
| 1 | 12 | 14 | \(\frac{14!}{12!1!1!} = 182\) |
| 2 | 10 | 13 | \(\frac{13!}{10!2!1!} = 858\) |
| 3 | 8 | 12 | \(\frac{12!}{8!3!1!} = 1,980\) |
| 4 | 6 | 11 | \(\frac{11!}{6!4!1!} = 2,310\) |
| 5 | 4 | 10 | \(\frac{10!}{4!5!1!} = 1,260\) |
| 6 | 2 | 9 | \(\frac{9!}{2!6!1!} = 252\) |
| 7 | 0 | 8 | \(\frac{8!}{0!7!1!} = 8\) |
Subtotal for \(z = 1\) :
\(15 + 182 + 858 + 1,980 + 2,310 + 1,260 + 252 + 8 = 6,865\)
3. \(z = 2\) : \(x + 2y = 11\)
| \(y\) | \(x = 11 - 2y\) | Total Steps (\(x + y + 2\)) | Permutations\(\frac{(x+y+2)!}{x!y!2!}\) |
|---|---|---|---|
| 0 | 11 | 13 | \(\frac{13!}{11!0!2!} = 78\) |
| 1 | 9 | 12 | \(\frac{12!}{9!1!2!} = 660\) |
| 2 | 7 | 11 | \(\frac{11!}{7!2!2!} = 1,980\) |
| 3 | 5 | 10 | \(\frac{10!}{5!3!2!} = 2,520\) |
| 4 | 3 | 9 | \(\frac{9!}{3!4!2!} = 1,260\) |
| 5 | 1 | 8 | \(\frac{8!}{1!5!2!} = 168\) |
Subtotal for \(z = 2\) :
\(78 + 660 + 1,980 + 2,520 + 1,260 + 168 = 6,666\)
4. \(z = 3\) : \(x + 2y = 8\)
| \(y\) | \(x = 8 - 2y\) | Total Steps (\(x + y + 3\)) | Permutations\(\frac{(x+y+3)!}{x!y!3!}\) |
|---|---|---|---|
| 0 | 8 | 11 | \(\frac{11!}{8!0!3!} = 165\) |
| 1 | 6 | 10 | \(\frac{10!}{6!1!3!} = 840\) |
| 2 | 4 | 9 | \(\frac{9!}{4!2!3!} = 1,260\) |
| 3 | 2 | 8 | \(\frac{8!}{2!3!3!} = 560\) |
| 4 | 0 | 7 | \(\frac{7!}{0!4!3!} = 35\) |
Subtotal for \(z = 3\) :
\(165 + 840 + 1,260 + 560 + 35 = 2,860\)
5. \(z = 4\) : \(x + 2y = 5\)
| \(y\) | \(x = 5 - 2y\) | Total Steps (\(x + y + 4\)) | Permutations\(\frac{(x+y+4)!}{x!y!4!}\) |
|---|---|---|---|
| 0 | 5 | 9 | \(\frac{9!}{5!0!4!} = 126\) |
| 1 | 3 | 8 | \(\frac{8!}{3!1!4!} = 280\) |
| 2 | 1 | 7 | \(\frac{7!}{1!2!4!} = 105\) |
Subtotal for \(z = 4\) :
\(126 + 280 + 105 = 511\)
6. \(z = 5\) : \(x + 2y = 2\)
| \(y\) | \(x = 2 - 2y\) | Total Steps (\(x + y + 5\)) | Permutations\(\frac{(x+y+5)!}{x!y!5!}\) |
|---|---|---|---|
| 0 | 2 | 7 | \(\frac{7!}{2!0!5!} = 21\) |
| 1 | 0 | 6 | \(\frac{6!}{0!1!5!} = 6\) |
Subtotal for \(z = 5\) :
\(21 + 6 = 27\)
Step 4: Sum All Subtotals
Add up all the subtotals from each \(z\):
Total Number of Ways: 19,513
Method 2
To determine the number of ways to descend a staircase with 17 steps when you can take 1, 2, or 3 steps at a time, there's a systematic and efficient method you can use without having to list all possible combinations. This approach utilizes recursion and dynamic programming principles.
Let's denote:
- f(n) as the number of ways to descend n steps.
Given that you can take 1, 2, or 3 steps at a time, the number of ways to reach the n-th step is the sum of the ways to reach the three preceding steps:
- f(n) = f(n-1) + f(n-2) + f(n-3)
This is because:
- From step n-1, you take 1 step to reach n.
- From step n-2, you take 2 steps to reach n.
- From step n-3, you take 3 steps to reach n.
Base Cases
To use this recursive formula, we need to define the base cases:
- f(0) = 1: There's one way to stay at the bottom without taking any steps.
- f(1) = 1: Only one way to take a single step.
- f(2) = 2: Either take two 1-steps or one 2-step.
Calculating f(n) Step-by-Step
Using the recursive relation and the base cases, let's compute f(n) from n = 3 up to n = 17.
| Step (n) | f(n) Calculation | f(n) Value |
|---|---|---|
| 0 | - | 1 |
| 1 | - | 1 |
| 2 | - | 2 |
| 3 | f(2) + f(1) + f(0) | 2 + 1 + 1 \= 4 |
| 4 | f(3) + f(2) + f(1) | 4 + 2 + 1 \= 7 |
| 5 | f(4) + f(3) + f(2) | 7 + 4 + 2 \= 13 |
| 6 | f(5) + f(4) + f(3) | 13 + 7 + 4 \= 24 |
| 7 | f(6) + f(5) + f(4) | 24 + 13 + 7 \= 44 |
| 8 | f(7) + f(6) + f(5) | 44 + 24 + 13 \= 81 |
| 9 | f(8) + f(7) + f(6) | 81 + 44 + 24 \= 149 |
| 10 | f(9) + f(8) + f(7) | 149 + 81 + 44 \= 274 |
| 11 | f(10) + f(9) + f(8) | 274 + 149 + 81 \= 504 |
| 12 | f(11) + f(10) + f(9) | 504 + 274 + 149 \= 927 |
| 13 | f(12) + f(11) + f(10) | 927 + 504 + 274 \= 1705 |
| 14 | f(13) + f(12) + f(11) | 1705 + 927 + 504 \= 3136 |
| 15 | f(14) + f(13) + f(12) | 3136 + 1705 + 927 \= 5768 |
| 16 | f(15) + f(14) + f(13) | 5768 + 3136 + 1705 \= 10609 |
| 17 | f(16) + f(15) + f(14) | 10609 + 5768 + 3136 \=19513 |
Final Answer
There are 19,513 distinct ways to descend a staircase of 17 steps by taking 1, 2, or 3 steps at a time.
Exercise 11 (⋆)
Let \(n, p \geq 1\) be two integers.
\(p\) must less or equal to \(n\)
- How many strictly increasing functions are there from \(\{1, \ldots, p\}\) to \(\{1, \ldots, n\}\)?
\(\binom{n}{p}\) *
-
Let \(f : \{1, \ldots, p\} \to \{1, \ldots, n\}\) be an increasing function. Let \(\phi(f)\) be the function defined on \(\{1, \ldots, p\}\), with values in \(\{1, \ldots, n + p - 1\}\), by \(\phi(f)(k) = f(k) + k - 1\). Prove that \(\phi(f)\) is strictly increasing.
Take \(\phi(f)(a)-\phi(f)(b)=f(a)-f(b)\)
-
Let \(g : \{1, \ldots, p\} \to \{1, \ldots, n + p - 1\}\) be a strictly increasing function. Let \(\psi(g)\) be the function defined on \(\{1, \ldots, p\}\), with values in \(\{1, \ldots, n\}\), by \(\psi(g)(k) = g(k) - k + 1\). Show that \(\psi(g)\) is increasing.
Same
-
How many increasing functions are there from \(\{1, \ldots, p\}\) to \(\{1, \ldots, n\}\)?
\(\binom{n+p-1}{p}\)