In the $4 \times 4$ grid table shown in the figure, select 4 squares such that each row and each column contains exactly one selected square. The total number of ways to do this is $\_\_\_\_$. Among all selections satisfying the above requirement, the maximum sum of the 4 numbers in the selected squares is $\_\_\_\_$.

11	21	31	40
12	22	33	42
13	22	33	43
15	24	34	44

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$.

For every pair $(p, k)$ of nonzero natural numbers, we denote by $S(p, k)$ the number of surjections from $\llbracket 1, p \rrbracket$ to $\llbracket 1, k \rrbracket$. Consistently, for every $p \in \mathbb{N}^*$, we set $S(p, 0) = 0$.
Determine $S(n+1, n)$.

For every pair $(p, k)$ of nonzero natural numbers, we denote by $S(p, k)$ the number of surjections from $\llbracket 1, p \rrbracket$ to $\llbracket 1, k \rrbracket$. Consistently, for every $p \in \mathbb{N}^*$, we set $S(p, 0) = 0$.
How many applications are there from $\llbracket 1, p \rrbracket$ to $\llbracket 1, n \rrbracket$?

For every pair $(p, k)$ of nonzero natural numbers, we denote by $S(p, k)$ the number of surjections from $\llbracket 1, p \rrbracket$ to $\llbracket 1, k \rrbracket$. Consistently, for every $p \in \mathbb{N}^*$, we set $S(p, 0) = 0$.
For $p \geqslant n$, establish the formula $$n^p = \sum_{k=0}^{n} \binom{n}{k} S(p, k)$$ where $S(p, 0) = 0$ by convention.

For every pair $(p, k)$ of nonzero natural numbers, we denote by $S(p, k)$ the number of surjections from $\llbracket 1, p \rrbracket$ to $\llbracket 1, k \rrbracket$. Consistently, for every $p \in \mathbb{N}^*$, we set $S(p, 0) = 0$.
Deduce an expression of $S(p, n)$ for $p \geqslant n$.

For every pair $(p, k)$ of nonzero natural numbers, we denote by $S(p, k)$ the number of surjections from $\llbracket 1, p \rrbracket$ to $\llbracket 1, k \rrbracket$. Consistently, for every $p \in \mathbb{N}^*$, we set $S(p, 0) = 0$.
By rereading question I.B.5, comment on the consistency of the expression of $S(p,n)$ for $p < n$.

For every pair $(p, k)$ of nonzero natural numbers, we denote by $S(p, k)$ the number of surjections from $\llbracket 1, p \rrbracket$ to $\llbracket 1, k \rrbracket$. Consistently, for every $p \in \mathbb{N}^*$, we set $S(p, 0) = 0$.
Simplify as much as possible the following expressions: $$\sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} k^n \quad \text{and} \quad \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} k^{n+1}$$

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 } }$.

How many natural numbers less than $10^{8}$ are there, whose sum of digits equals 7?

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}$.

Let $f(n)$ be the number of ways to write a positive integer as an ordered sum of three non-negative integers, where each integer is chosen from $\{0, 1, 2, \ldots, 2n-1\}$ (i.e., using $n$ colours with values $0$ to $2n-1$). Find $f(n)$.

Let $A$ be the set $\{ 1,2 , \ldots , 20 \}$. Fix two disjoint subsets $S _ { 1 }$ and $S _ { 2 }$ of $A$, each with exactly three elements. How many 3-element subsets of $A$ are there, which have exactly one element common with $S _ { 1 }$ and at least one element common with $S _ { 2 }$?
(a) 51
(b) 102
(c) 135
(d) 153

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

Let $S = \{ 1, 2, \ldots, n \}$. The number of possible pairs of the form $(A, B)$ with $A \subseteq B$ for subsets $A$ and $B$ of $S$ is
(A) $2^n$
(B) $3^n$
(C) $\sum _ { k = 0 } ^ { n } \binom { n } { k } \binom { n } { n - k }$
(D) $n!$

The number of maps $f$ from the set $\{ 1, 2, 3 \}$ into the set $\{ 1, 2, 3, 4, 5 \}$ such that $f(i) \leq f(j)$ whenever $i < j$ is
(A) 60
(B) 50
(C) 35
(D) 30

Consider three boxes, each containing 10 balls labelled $1, 2, \ldots, 10$. Suppose one ball is drawn from each of the boxes. Denote by $n_i$, the label of the ball drawn from the $i$-th box, $i = 1, 2, 3$. Then the number of ways in which the balls can be chosen such that $n_1 < n_2 < n_3$ is
(A) 120
(B) 130
(C) 150
(D) 160

A box contains 10 red cards numbered $1, \ldots, 10$ and 10 black cards numbered $1, \ldots, 10$. In how many ways can we choose 10 out of the 20 cards so that there are exactly 3 matches, where a match means a red card and a black card with the same number?
(A) $\binom { 10 } { 3 } \binom { 7 } { 4 } 2 ^ { 4 }$
(B) $\binom { 10 } { 3 } \binom { 7 } { 4 }$
(C) $\binom { 10 } { 3 } 2 ^ { 7 }$
(D) $\binom { 10 } { 3 } \binom { 14 } { 4 }$

The number of ways in which one can select six distinct integers from the set $\{1, 2, 3, \cdots, 49\}$, such that no two consecutive integers are selected, is
(A) $\binom{49}{6} - 5\binom{48}{5}$
(B) $\binom{43}{6}$
(C) $\binom{25}{6}$
(D) $\binom{44}{6}$

In how many ways can 20 identical chocolates be distributed among 8 students such that each student gets at least one chocolate and exactly 2 students get at least 2 chocolates?
(A) 308 (B) 280 (C) 300 (D) 320

Find the number of ordered triples $(a, b, c)$ of positive integers such that $abc = 1000$.
(A) 90 (B) 100 (C) 110 (D) 120

Let $S = \{ 1,2 , \ldots , n \}$. Find the number of unordered pairs $\{ A , B \}$ of subsets of $S$ such that $A$ and $B$ are disjoint, where $A$ or $B$ or both may be empty.

Let $S = \{ 1,2 , \ldots , n \}$. Find the number of unordered pairs $\{ A , B \}$ of subsets of $S$ such that $A$ and $B$ are disjoint, where $A$ or $B$ or both may be empty.