Show that the dimension of $\mathcal{C}(f)$ is greater than or equal to $n$.

We assume that $f$ is an endomorphism such that the algebra $\mathcal{C}(f)$ is equal to $\mathbb{K}[f]$. Show that $f$ is cyclic.

Suppose that there exists $f : \mathbb{N} \rightarrow \mathcal{P}(\mathbb{N})$ bijective. By considering $A = \{x \in \mathbb{N} \mid x \notin f(x)\}$, establish a contradiction.

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.

In this part, we assume that $\mathbb{K} = \mathbb{R}$ and that $E$ is a Euclidean space. The inner product of two vectors $x, y$ of $E$ is denoted $(x \mid y)$ and we denote by $\mathrm{O}(E)$ the group of vector isometries of $E$. We say that an endomorphism $f$ of $E$ is orthocyclic if there exists an orthonormal basis of $E$ in which the matrix of $f$ is of the form $C_Q$ (companion matrix).
Let $f \in \mathrm{O}(E)$. Let $f' \in \mathrm{O}(E)$ having the same characteristic polynomial as $f$. Show that there exist orthonormal bases $\mathcal{B}$ and $\mathcal{B}'$ of $E$ for which the matrix of $f$ in $\mathcal{B}$ is equal to the matrix of $f'$ in $\mathcal{B}'$.

Show that the application $\Phi : \begin{aligned} \mathcal{P}(\mathbb{N}) &\rightarrow \{0,1\}^{\mathbb{N}} \\ A &\mapsto \mathbb{1}_A \end{aligned}$ is bijective.

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.

In this part, we assume that $\mathbb{K} = \mathbb{R}$ and that $E$ is a Euclidean space. The inner product of two vectors $x, y$ of $E$ is denoted $(x \mid y)$ and we denote by $\mathrm{O}(E)$ the group of vector isometries of $E$. We say that an endomorphism $f$ of $E$ is orthocyclic if there exists an orthonormal basis of $E$ in which the matrix of $f$ is of the form $C_Q$ (companion matrix).
Let $f \in \mathrm{O}(E)$. Deduce that $f$ is orthocyclic if and only if $\chi_f = X^n - 1$ or $\chi_f = X^n + 1$.

Show that the application $$\Psi : \begin{aligned} \{0,1\}^{\mathbb{N}} &\rightarrow [0,1] \\ (x_n) &\mapsto \sum_{n=0}^{+\infty} \frac{x_n}{2^{n+1}} \end{aligned}$$ is well-defined and surjective. Is it injective?

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 this part, we assume that $\mathbb{K} = \mathbb{R}$ and that $E$ is a Euclidean space. The inner product of two vectors $x, y$ of $E$ is denoted $(x \mid y)$. We say that an endomorphism $f$ of $E$ is orthocyclic if there exists an orthonormal basis of $E$ in which the matrix of $f$ is of the form $C_Q$ (companion matrix).
Let $f$ be a nilpotent endomorphism of $E$. Show that there exists an orthonormal basis of $E$ in which the matrix of $f$ is lower triangular.

We denote $D^{\star} = D \backslash \{0\}$. We set for all $(x_n) \in \{0,1\}^{\mathbb{N}}$ $$\Lambda\left((x_n)\right) = \begin{cases} \Psi\left((x_n)\right) & \text{if } \Psi\left((x_n)\right) \in [0,1[ \backslash D^{\star} \\ \frac{\Psi\left((x_n)\right)}{2} & \text{if } \Psi\left((x_n)\right) \in D \cup \{1\} \text{ and } (x_n) \text{ is eventually constant at } 1 \\ \frac{1 + \Psi\left((x_n)\right)}{2} & \text{if } \Psi\left((x_n)\right) \in D^{\star} \text{ and } (x_n) \text{ is eventually constant at } 0 \end{cases}$$
Show that $\Lambda$ realizes a bijection from $\{0,1\}^{\mathbb{N}}$ to $[0,1[$.

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 this part, we assume that $\mathbb{K} = \mathbb{R}$ and that $E$ is a Euclidean space. The inner product of two vectors $x, y$ of $E$ is denoted $(x \mid y)$. We say that an endomorphism $f$ of $E$ is orthocyclic if there exists an orthonormal basis of $E$ in which the matrix of $f$ is of the form $C_Q$ (companion matrix).
Let $f$ be a nilpotent endomorphism of $E$. Deduce that $f$ is orthocyclic if and only if
$$f \text{ has rank } n-1 \quad \text{and} \quad \forall x, y \in (\ker f)^{\perp}, \quad (f(x) \mid f(y)) = (x \mid y).$$

Using the results of Q33--Q36, conclude that $[0,1[$ is not countable.

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$), an algorithm constructs a permutation of $S_{n}$ from an outcome of $n$ draws. Using question 33, compare, for any outcome, the number of white balls in the final composition of the urn with the number of ascents of the permutation associated with it by the algorithm above.

Using the result of question 31, prove that if $M \in \mathcal{M}_n(\mathbb{C})$ is nilpotent, then $M$, $2M$ and $M^\top$ are similar.

Using the result of question 15, prove that if $M$ and $2M$ are similar, then $M$ is nilpotent.

Let $n \in \mathbb{N}^*$. For $k \in \mathbb{N}$, we denote $\mathcal{B}(n, k)$ the set of maps $\sigma \in \operatorname{MD}(n+1)$ such that $\sigma(2) - \sigma(1) = k+1$. For $k \in \mathbb{N}$ and $s \in \mathbb{N}$, we denote $\mathcal{C}(n, s, k)$ the set of elements $\sigma$ of $\operatorname{MD}(n+2)$ such that $\sigma(2) - \sigma(1) = s+1, \quad n+2-\sigma(2) = k$.
1. For $m \geq 2$ verify that the map $\operatorname{Opp} : \Sigma_m \rightarrow \Sigma_m$, which to $\sigma \in \Sigma_m$ associates $\eta \in \Sigma_m$ defined by $$\eta(i) = m + 1 - \sigma(i)$$ is a bijection satisfying $\operatorname{Opp}(\operatorname{MD}(m)) = \operatorname{DM}(m)$ and $\operatorname{Opp}(\operatorname{DM}(m)) = \operatorname{MD}(m)$. Verify that if $\sigma \in \Sigma_m$ and if $i, j$ are elements of $\{1, \ldots, m\}$ satisfying $\sigma(j) > \sigma(i)$, $$\sigma(j) - \sigma(i) = 1 + \operatorname{Card}\{k \in \Delta_m \mid \sigma(i) < \sigma(k) < \sigma(j)\}$$

Let $n \in \mathbb{N}^*$. For $k \in \mathbb{N}$, we denote $\mathcal{B}(n, k)$ the set of maps $\sigma \in \operatorname{MD}(n+1)$ such that $\sigma(2) - \sigma(1) = k+1$. For $k \in \mathbb{N}$ and $s \in \mathbb{N}$, we denote $\mathcal{C}(n, s, k)$ the set of elements $\sigma$ of $\operatorname{MD}(n+2)$ such that $\sigma(2) - \sigma(1) = s+1, \quad n+2-\sigma(2) = k$.
2. Under what condition (necessary and sufficient) on $n$ and $k$ is the set $\mathcal{B}(n, k)$ non-empty? Under what condition (necessary and sufficient) on $n$, $s$ and $k$ is the set $\mathcal{C}(n, s, k)$ non-empty?

Let $n \in \mathbb{N}^*$. For $k \in \mathbb{N}$, we denote $\mathcal{B}(n, k)$ the set of maps $\sigma \in \operatorname{MD}(n+1)$ such that $\sigma(2) - \sigma(1) = k+1$. For $k \in \mathbb{N}$ and $s \in \mathbb{N}$, we denote $\mathcal{C}(n, s, k)$ the set of elements $\sigma$ of $\operatorname{MD}(n+2)$ such that $\sigma(2) - \sigma(1) = s+1, \quad n+2-\sigma(2) = k$.
3. In this question and the next, we fix $n \geq 2$, $1 \leq k \leq n-1$ and $1 \leq s \leq n-k$. We propose to construct a bijection from $\mathcal{C}(n, s, k)$ to $\mathcal{B}(n, k)$. Let $\sigma \in \mathcal{C}(n, s, k)$. a. Verify that the number $m$ of integers $j \geq 4$ such that $\sigma(j) > \sigma(3)$ satisfies $m \geq k$. We denote $j_1, \ldots, j_m$ these integers, which we order in such a way that $\sigma(j_1) < \sigma(j_2) < \cdots < \sigma(j_m)$. b. Show that $\xi$ defined by $\xi(1) = \sigma(j_k) + \frac{1}{2}$, $\xi(2) = \sigma(3)$, $\xi(n+1) = \ldots$ satisfies $$\xi(p) > \xi(p+1) \text{ for } p \text{ odd}, \quad \xi(p) < \xi(p+1) \text{ for } p \text{ even}$$ and that the interval $]\xi(2), \xi(1)[$ contains exactly $k$ elements of $\{\xi(3), \ldots, \xi(n+1)\}$. c. We denote $A = \xi(\Delta_{n+1})$ and we set $\bar{\xi} = \beta_A \circ \xi$ (we recall that $\beta_A$ denotes the unique increasing bijection from $A$ to $\Delta_{n+1}$). Show that $\bar{\xi} \in \operatorname{DM}(n+1)$. d. Let $\eta = \operatorname{Opp}(\bar{\xi})$. Verify that $\eta \in \mathcal{B}(n, k)$.

Let $n \in \mathbb{N}^*$. For $k \in \mathbb{N}$, we denote $\mathcal{B}(n, k)$ the set of maps $\sigma \in \operatorname{MD}(n+1)$ such that $\sigma(2) - \sigma(1) = k+1$. For $k \in \mathbb{N}$ and $s \in \mathbb{N}$, we denote $\mathcal{C}(n, s, k)$ the set of elements $\sigma$ of $\operatorname{MD}(n+2)$ such that $\sigma(2) - \sigma(1) = s+1, \quad n+2-\sigma(2) = k$.
We denote by $\Psi_{n,s,k}$ the map from $\mathcal{C}(n,s,k)$ to $\mathcal{B}(n,k)$ defined by $\Psi_{n,s,k}(\sigma) = \eta$.
4. Let $\eta \in \mathcal{B}(n, k)$ and let $\xi = \operatorname{Opp}(\eta)$. a. Verify that the number $m$ of integers $j \geq 3$ such that $\xi(j) > \xi(2)$ satisfies $m \geq k$. We denote these integers by $j_1, \ldots, j_m$, with $\xi(j_1) > \xi(j_2) \cdots > \xi(j_m)$. b. We set $u_2 = \xi(j_k) - \frac{1}{2} > \xi(2)$. Show that the number $m'$ of integers $i \geq 2$ such that $\xi(i) < u_2$ satisfies $m' \geq s$. We denote them by $i_1, \ldots, i_{m'}$, with $\xi(i_1) > \cdots > \xi(i_{m'})$ and we set $u_1 = \xi(i_k) - \frac{1}{2}$. c. By considering the map $\theta$ defined by $$\theta(1) = u_1, \theta(2) = u_2, \theta(3) = \xi(2), \ldots, \theta(n+2) = \xi(n+1)$$ show the existence of $\sigma \in \mathcal{C}(n, s, k)$ satisfying $\Psi_{n,s,k}(\sigma) = \eta$. d. Show that $\Psi_{n,s,k}$ is bijective.

5. Give a procedure for computing $\operatorname{Card} \operatorname{MD}(n)$ by recursion.

3. For a function $f : \mathbb{R} \rightarrow \mathbb{R}$ of class $C^\infty$ and $n \in \mathbb{N}$, we denote by $f^{(n)}$ the derivative of order $n$ of $f$, with the convention $f^{(0)} = f$. We denote by $D : \mathbb{R}[X] \rightarrow \mathbb{R}[X]$ the unique linear map such that $$D(X^0) = 0, \quad D(X^k) = k(X^{k-1} + X^{k+1}), \quad \forall k \in \mathbb{N}^*$$ For $n \in \mathbb{N}^*$, we denote by $D^n$ the composition of order $n$ of $D$, with the convention $D^0 = \mathrm{Id}$. a. Let $P_n = D^n(X)$. Prove that for $n \in \mathbb{N}$, $\tan^{(n)}(x) = P_n(\tan x)$ for $x \in ]-\frac{\pi}{2}, \frac{\pi}{2}[$. b. For $m \in \mathbb{N}^*$, let $V_m$ be the subspace of $\mathbb{R}[X]$ generated by $\{X, \ldots, X^m\}$. Let $\iota_m$ be the canonical injection of $V_m$ into $\mathbb{R}[X]$ and let $\tau_m : \mathbb{R}[X] \rightarrow V_m$ be the linear projection defined by $\tau_m(X^k) = X^k$ if $k \in \{1, \ldots, m\}$ and $\tau_m(X^k) = 0$ otherwise. Finally, we set $\delta_m = \tau_m \circ D \circ \iota_m$. Verify that $\delta_m$ is a linear map from $V_m$ to $V_m$ and write its matrix $M_m$ in the basis $(X, \ldots, X^m)$.