Let $k$ and $n$ be two strictly positive integers. Show that there exists only a finite number of partitions of the set $\llbracket 1 , n \rrbracket$ into $k$ parts.

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$.
Express $S ( n , k )$ as a function of $n$ or of $k$ in the following cases:
I.B.1) $k > n$;
I.B.2) $k = 1$.

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$.
Show that for all strictly positive integers $k$ and $n$, we have $$S ( n , k ) = S ( n - 1 , k - 1 ) + k S ( n - 1 , k )$$ One may distinguish the partitions of $\llbracket 1 , n \rrbracket$ according to whether or not they contain the singleton $\{ n \}$.

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

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

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

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.

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

Three left brackets and three right brackets have to be arranged in such a way that if the brackets are serially counted from the left, then the number of right brackets counted is always less than or equal to the number of left brackets counted. In how many ways can this be done?
(A) 3
(B) 4
(C) 5
(D) 6