For $\sigma \in \mathfrak{S}_{n}$, specify the condition on $\nu(\sigma)$ for which $\sigma \in \mathfrak{D}_{n}$. Deduce that $$\operatorname{Card}\left\{\sigma \in \mathfrak{D}_{n} : \varepsilon(\sigma) = 1\right\} = \operatorname{Card}\left\{\sigma \in \mathfrak{D}_{n} : \varepsilon(\sigma) = -1\right\} + (-1)^{n-1}(n-1).$$

For $\sigma \in \mathfrak{S}_n$, specify the condition on $\nu(\sigma)$ for which $\sigma \in \mathfrak{D}_n$. Deduce that $$\operatorname{Card}\left\{\sigma \in \mathfrak{D}_n : \varepsilon(\sigma) = 1\right\} = \operatorname{Card}\left\{\sigma \in \mathfrak{D}_n : \varepsilon(\sigma) = -1\right\} + (-1)^{n-1}(n-1).$$

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_{n}$, we recall that there exists, up to order, a unique decomposition $\sigma = c_{1} c_{2} \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^{*}$ where $c_{1}, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_{1} \leqslant \ell_{2} \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_{1} + \ell_{2} + \cdots + \ell_{\omega(\sigma)} = n$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_{n}$ such that $\omega(\sigma) = k$.
Specify $s(n,n)$ and $s(n,1)$ then show that, for $2 \leqslant k \leqslant n-1$, we have $$s(n,k) = s(n-1, k-1) + (n-1) s(n-1, k)$$ For $\sigma \in \mathfrak{S}_{n}$, one may distinguish the cases $\sigma(1) = 1$ and $\sigma(1) \neq 1$.

Let $n$ be a non-zero natural integer. For any permutation $\sigma \in \mathfrak{S}_n$, we recall that there exists, up to order, a unique decomposition $\sigma = c_1 c_2 \cdots c_{\omega(\sigma)}$, where $\omega(\sigma) \in \mathbb{N}^*$ and $c_1, \ldots, c_{\omega(\sigma)}$ are cycles with disjoint supports of respective lengths $\ell_1 \leqslant \ell_2 \leqslant \cdots \leqslant \ell_{\omega(\sigma)}$ and $\ell_1 + \ell_2 + \cdots + \ell_{\omega(\sigma)} = n$. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_n$ such that $\omega(\sigma) = k$.
Specify $s(n,n)$ and $s(n,1)$ then show that, for $2 \leqslant k \leqslant n-1$, we have $$s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k).$$ For $\sigma \in \mathfrak{S}_n$, one may distinguish the cases $\sigma(1) = 1$ and $\sigma(1) \neq 1$.

Let $n$ be a non-zero natural integer. For an integer $k$ at most $n$, we denote by $s(n,k)$ the number of permutations of $\mathfrak{S}_n$ such that $\omega(\sigma) = k$.
Establish that, for any real $x$, $$\prod_{i=0}^{n-1}(x+i) = \sum_{k=1}^{n} s(n,k) x^k.$$

In how many ways can the numbers $1, 2, \ldots, 9$ be arranged in a $3 \times 3$ grid \[ \begin{array}{|c|c|c|} \hline A & B & C \\ \hline D & E & F \\ \hline G & H & I \\ \hline \end{array} \] such that each row and each column is in increasing order (i.e., $A < B < C$, $D < E < F$, $G < H < I$, $A < D < G$, $B < E < H$, $C < F < I$)?

There are 8 balls numbered $1,2 , \ldots , 8$ and 8 boxes numbered $1,2 , \ldots , 8$. The number of ways one can put these balls in the boxes so that each box gets one ball and exactly 4 balls go in their corresponding numbered boxes is
(a) $3 \times {}^{8}\mathrm{C}_{4}$
(b) $6 \times {}^{8}\mathrm{C}_{4}$
(c) $9 \times {}^{8}\mathrm{C}_{4}$
(d) $12 \times {}^{8}C_{4}$

A person $X$ standing at a point $P$ on a flat plane starts walking. At each step, he walks exactly 1 foot in one of the directions North, South, East or West. Suppose that after 6 steps $X$ comes to the original position $P$. Then the number of distinct paths that $X$ can take is
(a) 196
(b) 256
(c) 344
(d) 400

In how many ways can 3 couples sit around a round table such that men and women alternate and none of the couples sit together?
(a) 1
(b) 2
(c) $5! / 3$
(d) None of these.

Let $A$ be the set $\{ 1,2 , \ldots , 6 \}$. How many functions from $A$ to $A$ are there such that the range of $f$ has exactly 5 elements?
(a) 240
(b) 720
(c) 1800
(d) 10800

Let $f:\{1,2,3,4\} \to \{1,2,3,4\}$ be a function such that $f(i) \neq i$ for all $i$ (i.e., a derangement). Find the number of such functions.

In how many ways can $10$ A's and $6$ B's be arranged in a row such that no two B's are adjacent and no two A's are adjacent? (More precisely: find the number of arrangements of $10$ A's and $6$ B's such that between any two consecutive B's there is at least one A, and between any two consecutive A's there is at least one B.)

The sum of all distinct four digit numbers that can be formed using the digits $1,2,3,4$, and 5, each digit appearing at most once, is
(A) 399900
(B) 399960
(C) 390000
(D) 360000

In a win-or-lose game, the winner gets 2 points whereas the loser gets 0. Six players A, B, C, D, E and F play each other in a preliminary round from which the top three players move to the final round. After each player has played four games, A has 6 points, B has 8 points and C has 4 points. It is also known that E won against F. In the next set of games D, E and F win their games against A, B and C respectively. If A, B and D move to the final round, the final scores of E and F are, respectively,
(A) 4 and 2
(B) 2 and 4
(C) 2 and 2
(D) 4 and 4.

Find the number of six-digit numbers using digits from $\{2, 3, 9\}$ (repetition allowed) that are divisible by 6.
(A) 80 (B) 82 (C) 81 (D) 83

Find the sum of all distinct four digit numbers that can be formed using the digits $1,2,3,4,5$, each digit appearing at most once.

Find the sum of all distinct four digit numbers that can be formed using the digits $1,2,3,4,5$, each digit appearing at most once.

The sum of all distinct four digit numbers that can be formed using the digits $1,2,3,4$, and 5, each digit appearing at most once, is
(A) 399900
(B) 399960
(C) 390000
(D) 360000

The sum of all distinct four digit numbers that can be formed using the digits $1,2,3,4$, and 5, each digit appearing at most once, is
(A) 399900
(B) 399960
(C) 390000
(D) 360000

A solid cube of side five centimeters has all its faces painted. The cube is sliced into smaller cubes, each of side one centimeter. How many of these smaller cubes will have paint on exactly one of its faces?
(A) 25
(B) 54
(C) 126
(D) 150.

Let $A = \{ 1,2 , \ldots , n \}$. For a permutation $P = ( P ( 1 ) , P ( 2 ) , \cdots , P ( n ) )$ of the elements of $A$, let $P ( 1 )$ denote the first element of $P$. Find the number of all such permutations $P$ so that for all $i , j \in A$:

• if $i < j < P ( 1 )$, then $j$ appears before $i$ in $P$; and
• if $P ( 1 ) < i < j$, then $i$ appears before $j$ in $P$.

Consider all the permutations of the twenty six English letters that start with $z$. In how many of these permutations the number of letters between $z$ and $y$ is less than those between $y$ and $x$?
(A) $6 \times 23!$
(B) $6 \times 24!$
(C) $156 \times 23!$
(D) $156 \times 24!$.

Suppose Roger has 4 identical green tennis balls and 5 identical red tennis balls. In how many ways can Roger arrange these 9 balls in a line so that no two green balls are next to each other and no three red balls are together?
(A) 8
(B) 9
(C) 11
(D) 12

The number of permutations $\sigma$ of $1,2,3,4$ such that $| \sigma ( i ) - i | < 2$ for every $1 \leq i \leq 4$ is
(A) 2
(B) 3
(C) 4
(D) 5.

Assume that $n$ copies of unit cubes are glued together side by side to form a rectangular solid block. If the number of unit cubes that are completely invisible is 30, then the minimum possible value of $n$ is:
(A) 204
(B) 180
(C) 140
(D) 84.