An alien script has $n$ letters $b_{1}, \ldots, b_{n}$. For some $k < n/2$ assume that all words formed by any of the $k$ letters (written left to right) are meaningful. These words are called $k$-words. Such a $k$-word is considered sacred if:
i) no letter appears twice and,
ii) if a letter $b_{i}$ appears in the word then the letters $b_{i-1}$ and $b_{i+1}$ do not appear. (Here $b_{n+1} = b_{1}$ and $b_{0} = b_{n}$.)
For example, if $n = 7$ and $k = 3$ then $b_{1}b_{3}b_{6}, b_{3}b_{1}b_{6}, b_{2}b_{4}b_{6}$ are sacred 3-words. On the other hand $b_{1}b_{7}b_{4}, b_{2}b_{2}b_{6}$ are not sacred. What is the total number of sacred $k$-words? Use your formula to find the answer for $n = 10$ and $k = 4$.

Let $\pi = \pi_{1}\pi_{2}\ldots\ldots\pi_{n}$ be a permutation of the numbers $1,2,3,\ldots,n$. We say $\pi$ has its first ascent at position $k < n$ if $\pi_{1} > \pi_{2} \ldots > \pi_{k}$ and $\pi_{k} < \pi_{k+1}$. If $\pi_{1} > \pi_{2} > \ldots > \pi_{n-1} > \pi_{n}$ we say $\pi$ has its first ascent in position $n$. For example when $n = 4$ the permutation 2134 has its first ascent at position 2.
The number of permutations which have their first ascent at position $k$ is ......

Suppose that cards numbered $1, 2, \ldots, n$ are placed on a line in some sequence (with each integer $i \in [1,n]$ appearing exactly once). A move consists of interchanging the card labeled 1 with any other card. If it is possible to rearrange the cards in increasing order by doing a series of moves, we say that the given sequence can be rectified.
Statements
(37) The sequence 912345678 can be rectified in 8 moves and no fewer moves. (38) The sequence 134567892 can be rectified in 8 moves and no fewer moves. (39) The sequence 134295678 cannot be rectified. (40) There exists a sequence of 99 cards that cannot be rectified.

A permutation $\sigma$ of $\llbracket 1, n \rrbracket$ is called alternating up if the list $(\sigma(1), \ldots, \sigma(n))$ satisfies $x_1 < x_2 > x_3 < x_4 > \cdots$. Determine the alternating up permutations of $\llbracket 1, n \rrbracket$ for $n = 2$, $n = 3$, $n = 4$.

A permutation $\sigma$ of $\llbracket 1, n \rrbracket$ is called alternating up if $(\sigma(1), \ldots, \sigma(n))$ satisfies $x_1 < x_2 > x_3 < x_4 > \cdots$, and alternating down if it satisfies the reverse inequalities. Show, for every $n \geqslant 2$, that the number of alternating up permutations equals the number of alternating down permutations.

Let $\beta_n$ denote the number of alternating up permutations of $\llbracket 1, n \rrbracket$ (with $\beta_0 = \beta_1 = 1$). Let $k$ and $n$ be two integers such that $2 \leqslant k \leqslant n$ and $A$ a subset with $k$ elements of $\llbracket 1, n \rrbracket$. We consider the lists $(x_1, \ldots, x_k)$ consisting of $k$ pairwise distinct elements of $A$. Show that the number of these lists that are alternating up equals $\beta_k$.

Let $k$ be an integer greater than or equal to $1$, $(u_{0}, \ldots, u_{k})$ a finite sequence of integers, and $a$ an integer such that $a > u_{p}$ for all $p \in \llbracket 0, k \rrbracket$. We insert the value $a$ into this sequence immediately after $u_{i}$, with $i \in \llbracket 0, k-1 \rrbracket$, to obtain the sequence $(u_{0}, \ldots, u_{i}, a, u_{i+1}, \ldots, u_{k})$. Compare the number of ascents and descents of the new sequence with respect to the old one. Two cases will be distinguished.

We denote by $S_{n}$ the set of permutations of $\llbracket 1, n \rrbracket$. We represent an element $\sigma$ of $S_{n}$ by the finite sequence $(\sigma(1), \sigma(2), \ldots, \sigma(n))$ and we call an ascent (respectively descent) of $\sigma$ an ascent of this sequence. For any integer $m$, we denote by $A_{n,m}$ the number of elements of $S_{n}$ with $m$ ascents.
In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), $P_{3}(u,v) = uv^{3} + 4u^{2}v^{2} + u^{3}v$.
Determine the elements of $S_{3}$ and calculate among them the number of permutations with $m$ ascents for any integer $m$. Compare the values obtained with the coefficients of $P_{3}(X, 1)$ where $P_{3}$ was expressed in question 13.

We denote by $S_{n}$ the set of permutations of $\llbracket 1, n \rrbracket$. We represent an element $\sigma$ of $S_{n}$ by the finite sequence $(\sigma(1), \sigma(2), \ldots, \sigma(n))$ and we call an ascent (respectively descent) of $\sigma$ an ascent of this sequence. For any integer $m$, we denote by $A_{n,m}$ the number of elements of $S_{n}$ with $m$ ascents.
Let $n \geqslant 2$. Determine $A_{n,0}$, $A_{n,n-1}$ and $A_{n,m}$ for $m \geqslant n$.

In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), an algorithm constructs a permutation of $S_{n}$ from an outcome of $n$ draws as follows:

• We start with the sequence $(0,1,0)$ after the first draw.
• For any $k \in \llbracket 2, n \rrbracket$, if on the $k$-th draw we draw a white ball (respectively black ball) numbered $p$, we insert the value $k$ in the sequence in the middle of the $(p+1)$-th ascent (respectively descent).
• At the end, we remove the two 0's from the list.

Using the algorithm above, construct the permutation of $S_{5}$ associated with the outcome $(B_{0}, B_{0}, N_{1}, N_{0}, B_{2})$.

In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), an algorithm constructs a permutation of $S_{n}$ from an outcome of $n$ draws as follows:

• We start with the sequence $(0,1,0)$ after the first draw.
• For any $k \in \llbracket 2, n \rrbracket$, if on the $k$-th draw we draw a white ball (respectively black ball) numbered $p$, we insert the value $k$ in the sequence in the middle of the $(p+1)$-th ascent (respectively descent).
• At the end, we remove the two 0's from the list.

Conversely, let $\sigma$ be the element of $S_{7}$ represented by the sequence $(7,1,3,6,5,4,2)$. Determine an outcome $\omega$ consisting of 7 draws such that $\sigma_{\omega} = \sigma$.

In Friedman's urn model ($a_{0} = 1, b_{0} = 0, a = d = 0, b = c = 1$), the map $\omega \mapsto \sigma(\omega)$ is bijective from $\Omega_{n}$ to $S_{n}$ and induces a bijection between the event $(X_{n} = m)$ and the set of permutations of $S_{n}$ having $m-1$ ascents. We denote by $A_{n,m}$ the number of elements of $S_{n}$ with $m$ ascents.
Let $m \in \llbracket 1, n \rrbracket$. Determine, for any integer $n \geqslant 2$ and any $m \in \llbracket 0, n-1 \rrbracket$, the number $A_{n,m}$ of permutations of $S_{n}$ having $m$ ascents.

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$)?

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.

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

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.

A finite sequence of numbers $(a_{1}, \ldots, a_{n})$ is said to be alternating if
$$a_{1} > a_{2}, \quad a_{2} < a_{3}, \quad a_{3} > a_{4}, \quad a_{4} < a_{5}, \ldots$$ $$\text{or} \quad a_{1} < a_{2}, \quad a_{2} > a_{3}, \quad a_{3} < a_{4}, \quad a_{4} > a_{5}, \ldots$$
How many alternating sequences of length 5, with distinct numbers $a_{1}, \ldots, a_{5}$ can be formed such that $a_{i} \in \{1, 2, \ldots, 20\}$ for $i = 1, \ldots, 5$?

Six cards and six envelopes are numbered $1,2,3,4,5,6$ and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same number and moreover the card numbered 1 is always placed in envelope numbered 2. Then the number of ways it can be done is
(A) 264
(B) 265
(C) 53
(D) 67

Consider all sequences composed of only the three digits 0, 1, 2. The length $n$ of a sequence refers to the sequence consisting of $n$ digits (which may repeat). Let $a(n)$ be the total count of consecutive pairs of zeros (i.e., 00) appearing in all sequences of length $n$. For example, among sequences of length 3 containing consecutive zeros, there are 000, 001, 002, 100, 200. Among these, 000 contributes 2 occurrences of 00, and each of the others contributes 1 occurrence of 00, so $a(3) = 6$. The value of $a(5)$ is $\square$.