Throughout the problem, for every pair $( n , k )$ of strictly positive integers, we denote by $S ( n , k )$ the number of partitions of the set $\llbracket 1 , n \rrbracket$ into $k$ parts. We further set $S ( 0,0 ) = 1$ and, for all $( n , k ) \in \mathbb { N } ^ { * 2 } , S ( n , 0 ) = S ( 0 , k ) = 0$. The recurrence relation $S ( n , k ) = S ( n - 1 , k - 1 ) + k S ( n - 1 , k )$ holds for all strictly positive integers $k$ and $n$.
I.D.1) Write a recursive Python function to compute the number $S ( n , k )$, by direct application of the formula established in question I.C.
I.D.2) Show that, for $n \geqslant 1$, the computation of $S ( n , k )$ by this recursive function requires at least $\binom { n } { k }$ operations (sums or products).

We set for every integer $n \geqslant 0$, $$B _ { n } = \sum _ { k = 0 } ^ { n } S ( n , k )$$ where $S(n,k)$ denotes the number of partitions of $\llbracket 1, n \rrbracket$ into $k$ parts.
Show that for $n \geqslant 1$, $B _ { n }$ equals the total number of partitions of the set $\llbracket 1 , n \rrbracket$.

What is the cardinality of $\mathcal{M}_{n}(\{-1,1\})$? Is this set a vector subspace of $\mathcal{M}_{n}(\mathbb{R})$?

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

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

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.

Let $\beta_n$ denote the number of alternating up permutations of $\llbracket 1, n \rrbracket$ (with $\beta_0 = \beta_1 = 1$). For $k \in \llbracket 0, n \rrbracket$, enumerate the permutations $\sigma$ alternating (up or down) of $\llbracket 1, n+1 \rrbracket$ such that $\sigma(k+1) = n+1$. Show, for every integer $n \geqslant 1$, $$2\beta_{n+1} = \sum_{k=0}^{n} \binom{n}{k} \beta_k \beta_{n-k}.$$

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

For every integer $n \geqslant 2$, let $p_n$ be the probability that a uniformly random permutation of $\llbracket 1, n \rrbracket$ is alternating up (with $p_0 = p_1 = 1$). Show that the sequence $(p_n)$ tends to 0. Give an equivalent of $p_{2n+1}$ as $n$ tends to infinity.

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.

We assume that $d = 2$ and that the distribution of $X$ is given by $$P ( X = ( 0,1 ) ) = P ( X = ( 0 , - 1 ) ) = P ( X = ( 1,0 ) ) = P ( X = ( - 1,0 ) ) = \frac { 1 } { 4 }$$ Let $n \in \mathbb{N}$. Establish the equality $$P \left( S _ { 2 n } = 0 _ { 2 } \right) = \left( \frac { \binom { 2 n } { n } } { 4 ^ { n } } \right) ^ { 2 }$$

For every integer $n \geqslant 1$, we denote $C_{n}$ the number of well-parenthesized words of length $2n$. We set by convention $C_{0} = 1$.
By enumerating the different well-parenthesized words of length 2, 4 and 6, show that $C_{1} = 1$, $C_{2} = 2$ and determine $C_{3}$.

For every integer $n \geqslant 1$, we denote $C_{n}$ the number of well-parenthesized words of length $2n$. We set by convenience $C_{0} = 1$.
By enumerating the different well-parenthesized words of length 2, 4 and 6, show that $C_{1} = 1$, $C_{2} = 2$ and determine $C_{3}$.

For every integer $n \geqslant 1$, we denote $C_{n}$ the number of well-parenthesized words of length $2n$. We set by convention $C_{0} = 1$.
Show by a combinatorial argument that, for every integer $k \geqslant 1$, $$C_{k} = \sum_{i=0}^{k-1} C_{i} C_{k-i-1}$$ We can note that a well-parenthesized word is necessarily of the form $(m)m^{\prime}$ with $m$ and $m^{\prime}$ two well-parenthesized words, possibly empty.

For every integer $n \geqslant 1$, we denote $C_{n}$ the number of well-parenthesized words of length $2n$. We set by convenience $C_{0} = 1$.
Show by a combinatorial argument that, for every integer $k \geqslant 1$, $$C_{k} = \sum_{i=0}^{k-1} C_{i} C_{k-i-1}$$ We can note that a well-parenthesized word is necessarily of the form $(m)m^{\prime}$ with $m$ and $m^{\prime}$ two well-parenthesized words, possibly empty.

Assume that $k$ is even and that $\vec{\imath} \in \mathcal{B}_{k}$ is a cycle passing through $\frac{k}{2} + 1$ distinct vertices (i.e. $|\vec{\imath}| = \frac{k}{2} + 1$). We traverse the edges of $\vec{\imath}$ in order. To each edge of $\vec{\imath}$ we associate an opening parenthesis if this edge appears for the first time and a closing parenthesis if it appears for the second time.
Count the cycles $\vec{\imath}$ that correspond to a fixed well-parenthesized word.

Assume $k$ is even and $\vec{\imath} \in \mathcal{B}_{k}$ is a cycle passing through $\frac{k}{2}+1$ distinct vertices (i.e. $|\vec{\imath}| = \frac{k}{2}+1$). We traverse the edges of $\vec{\imath}$ in order. To each edge of $\vec{\imath}$ we associate an opening parenthesis if this edge appears for the first time and a closing parenthesis if it appears for the second time.
Count the cycles $\vec{\imath}$ that correspond to a fixed well-parenthesized word.

Calculate $$\sum_{\sigma \in \mathfrak{S}_{n}} \varepsilon(\sigma), \quad \sum_{\sigma \in \mathfrak{S}_{n}} \varepsilon(\sigma) \nu(\sigma) \quad \text{and} \quad \sum_{\sigma \in \mathfrak{S}_{n}} \frac{\varepsilon(\sigma)}{\nu(\sigma)+1}.$$

Calculate $$\sum_{\sigma \in \mathfrak{S}_n} \varepsilon(\sigma), \quad \sum_{\sigma \in \mathfrak{S}_n} \varepsilon(\sigma) \nu(\sigma) \quad \text{and} \quad \sum_{\sigma \in \mathfrak{S}_n} \frac{\varepsilon(\sigma)}{\nu(\sigma)+1}.$$

Establish that $$\operatorname{Card}\left\{\sigma \in \mathfrak{S}_{n} : \varepsilon(\sigma) = 1\right\} = \operatorname{Card}\left\{\sigma \in \mathfrak{S}_{n} : \varepsilon(\sigma) = -1\right\}$$ and deduce the probability that a permutation of $\mathfrak{S}_{n}$ drawn uniformly at random has a prescribed signature.

Establish that $$\operatorname{Card}\left\{\sigma \in \mathfrak{S}_n : \varepsilon(\sigma) = 1\right\} = \operatorname{Card}\left\{\sigma \in \mathfrak{S}_n : \varepsilon(\sigma) = -1\right\}$$ and deduce the probability that a permutation of $\mathfrak{S}_n$ drawn uniformly at random has a prescribed signature.