We work on $\mathbb{R}^n$ for a natural integer $n \geqslant 3$. Let $m \in \mathbb{N}^*$.
Show that the set $$\left\{ (i_1, i_2, \ldots, i_n) \in \mathbb{N}^n \mid i_1 + i_2 + \cdots + i_n = m \right\}$$ has cardinality $\dbinom{n+m-1}{m}$. Deduce the dimension of $\mathcal{P}_m$.

We admit that Vandermonde's identity remains valid for all natural integers $u, v, N$: $$\binom{u+v}{N} = \sum_{k=0}^{N} \binom{u}{k} \binom{v}{N-k}.$$ Give a combinatorial interpretation of Vandermonde's identity.

For $k \in \llbracket 0, n \rrbracket$, show that the number of permutations of $\llbracket 1, n \rrbracket$ having exactly $k$ fixed points is $\binom{n}{k} d_{n-k}$.
Deduce that $P_n\left(X_n = k\right) = \frac{d_{n-k}}{k!(n-k)!}$.

Let $G _ { 0 } = \left( S _ { 0 } , A _ { 0 } \right)$ be a particular fixed graph with $s _ { 0 } = s _ { G _ { 0 } }$, $a _ { 0 } = a _ { G _ { 0 } }$, $s_0 \geq 2$, $a_0 \geq 1$. Let $\mathcal{C}_0$ be the set of copies of $G_0$ whose vertices are included in $\llbracket 1, n \rrbracket$: $$\mathcal { C } _ { 0 } = \left\{ H \mid H \text { is a copy of } G _ { 0 } \text { and } H = \left( S _ { H } , A _ { H } \right) \text { with } S _ { H } \subset \llbracket 1 , n \rrbracket \right\}$$ Let $S _ { 0 } ^ { \prime }$ be a fixed set of cardinality $s _ { 0 }$. We denote by $c _ { 0 }$ the number of graphs whose vertex set is $S _ { 0 } ^ { \prime }$ and which are copies of $G _ { 0 }$. Express the cardinality of $\mathcal { C } _ { 0 }$ using $c _ { 0 }$ and using a simple upper bound for $c _ { 0 }$, justify that the cardinality of $\mathcal { C } _ { 0 }$ is less than $n ^ { s _ { 0 } }$.

Let $A_{m,n}$ denote the set of strictly increasing sequences $1 \leq \alpha_1 < \alpha_2 < \cdots < \alpha_m \leq n$ of integers, $B_{m,n}$ denote the set of non-negative integer solutions of $\alpha_1 + \alpha_2 + \cdots + \alpha_m = n$, and $C_{m,n}$ denote the set of strictly increasing sequences chosen from $\{1,2,\ldots,n\}$.
a) Construct a bijection from $A_{m,n}$ to $B_{m+1,n-1}$.
b) Construct a bijection from $A_{m,n}$ to $C_{m,m+n-1}$.
c) Find the number of elements in $A_{m,n}$.

Using AM-GM inequality, find a lower bound for $\left({}^{10}C_0\right)\left({}^{10}C_1\right)\cdots\left({}^{10}C_{10}\right)$, and determine which of the following holds:
(A) $\left({}^{10}C_0\right)\left({}^{10}C_1\right)\cdots\left({}^{10}C_{10}\right) < \left(\dfrac{2^{10}}{11}\right)^{11}$
(B) $\left({}^{10}C_0\right)\left({}^{10}C_1\right)\cdots\left({}^{10}C_{10}\right) = \left(\dfrac{2^{10}}{11}\right)^{11}$
(C) $\left({}^{10}C_0\right)\left({}^{10}C_1\right)\cdots\left({}^{10}C_{10}\right) > \left(\dfrac{2^{10}}{11}\right)^{11}$
(D) None of the above

If $n = { } ^ { m } C _ { 2 }$, then the value of ${ } ^ { n } C _ { 2 }$ is given by
(1) $3 \left( { } ^ { m + 1 } C _ { 4 } \right)$
(2) ${ } ^ { m - 1 } C _ { 4 }$
(3) ${ } ^ { m + 1 } C _ { 4 }$
(4) $2 \left( { } ^ { m + 2 } C _ { 4 } \right)$

If $\sum _ { r = 0 } ^ { 25 } \left\{ \left( { } ^ { 50 } C _ { r } \right) \left( { } ^ { 50 - r } C _ { 25 - r } \right) \right\} = K \left( { } ^ { 50 } C _ { 25 } \right)$, then $K$ is equal to
(1) $2 ^ { 25 }$
(2) $2 ^ { 25 } - 1$
(3) $2 ^ { 24 }$
(4) $( 25 ) ^ { 2 }$

The value of $\sum _ { r = 0 } ^ { 20 } { } ^ { 50 - r } C _ { 6 }$ is equal to:
(1) ${ } ^ { 51 } C _ { 7 } - { } ^ { 30 } C _ { 7 }$
(2) ${ } ^ { 50 } C _ { 7 } - { } ^ { 30 } C _ { 7 }$
(3) ${ } ^ { 50 } C _ { 6 } - { } ^ { 30 } C _ { 6 }$
(4) ${ } ^ { 51 } C _ { 7 } + { } ^ { 30 } C _ { 7 }$

If $\sum _ { k = 1 } ^ { 10 } K ^ { 2 } \left( { } ^ { 10 } C _ { K } \right) ^ { 2 } = 22000 L$, then $L$ is equal to

If $\sum_{k=1}^{31} \left({}^{31}\mathrm{C}_k\right)\left({}^{31}\mathrm{C}_{k-1}\right) - \sum_{k=1}^{30}\left({}^{30}\mathrm{C}_k\right)\left({}^{30}\mathrm{C}_{k-1}\right) = \frac{\alpha(60!)}{(30!)(31!)}$, where $\alpha \in R$, then the value of $16\alpha$ is equal to
(1) 1411
(2) 1320
(3) 1615
(4) 1855

$\sum _ { k = 0 } ^ { 6 } { } ^ { 51 - k } C _ { 3 }$ is equal to
(1) ${ } ^ { 51 } C _ { 4 } - { } ^ { 45 } C _ { 4 }$
(2) ${ } ^ { 51 } C _ { 3 } - { } ^ { 45 } C _ { 3 }$
(3) ${ } ^ { 52 } C _ { 4 } - { } ^ { 45 } C _ { 4 }$
(4) ${ } ^ { 52 } C _ { 3 } - { } ^ { 45 } C _ { 3 }$

If the product $\left(\frac{1}{{}^{15}C_0} + \frac{1}{{}^{15}C_1}\right)\left(\frac{1}{{}^{15}C_1} + \frac{1}{{}^{15}C_2}\right) \cdots \left(\frac{1}{{}^{15}C_{12}} + \frac{1}{{}^{15}C_{13}}\right) = \frac{\alpha^{13}}{{}^{14}C_0 \cdot {}^{14}C_1 \cdot {}^{14}C_2 \cdots {}^{14}C_{12}}$, then $30\alpha$ is equal to
(A) 16
(B) 32
(C) 15
(D) 28

5. For ALL APPLICANTS.

This question is about counting the number of ways of partitioning a set of $n$ elements into subsets, each with at least two and at most $n$ elements. If $n$ and $k$ are integers with $1 \leqslant k \leqslant n$, let $f ( n , k )$ be the number of ways of partitioning a set of $n$ elements into $k$ such subsets. For example, $f ( 5,2 ) = 10$ because the allowable partitions of $\{ 1,2,3,4,5 \}$ are
$$\begin{array} { l l } \{ 1,5 \} , \{ 2,3,4 \} , & \{ 1,2,5 \} , \{ 3,4 \} , \\ \{ 2,5 \} , \{ 1,3,4 \} , & \{ 3,4,5 \} , \{ 1,2 \} , \\ \{ 3,5 \} , \{ 1,2,4 \} , & \{ 1,3,5 \} , \{ 2,4 \} , \\ \{ 4,5 \} , \{ 1,2,3 \} , & \{ 2,4,5 \} , \{ 1,3 \} , \\ & \{ 1,4,5 \} , \{ 2,3 \} , \\ & \{ 2,3,5 \} , \{ 1,4 \} . \end{array}$$
(i) Explain why $f ( n , k ) = 0$ if $k > n / 2$.
(ii) What is the value of $f ( n , 1 )$ and why?
(iii) In forming an allowable partition of $\{ 1,2 , \ldots , n + 1 \}$ into subsets of at least two elements, we can either

• pair $n + 1$ with one other element, leaving $n - 1$ elements to deal with, or
• take an allowable partition of $\{ 1,2 , \ldots , n \}$ and add $n + 1$ to one of the existing subsets, making a subset of size three or more.

Use this observation to find an equation for $f ( n + 1 , k )$ in terms of $f ( n - 1 , k - 1 )$ and $f ( n , k )$ that holds when $2 \leqslant k < n$.
(iv) Use this equation to compute the value of $f ( 7,3 )$.
(v) Give a formula for $f ( 2 n , n )$ in terms of $n$ when $n \geqslant 1$ and show that it is correct.
If you require additional space please use the pages at the end of the booklet