Let $n$ be a strictly positive integer. Denote by $\mathfrak{S}_{n}$ the set of bijections from the set $\{1,2, \ldots, n\}$ to itself. Let $\sigma \in \mathfrak{S}_{n}$; we say that $(i, j)$ (for $1 \leq i, j \leq n$) is an inversion of $\sigma$ if $i\sigma(j)$. We also say that $i$ (for $1 \leq i \leq n$) is a record of $\sigma$ if for all $j$ with $1 \leq j \leq i-1$ we have $\sigma(j)<\sigma(i)$ (thus, 1 is always a record). Finally, denote $\operatorname{inv}(\sigma)$ the number of inversions of $\sigma$ and $\operatorname{rec}(\sigma)$ its number of records.

Calculate the following sum:

$$
\sum_{\sigma \in \mathfrak{S}_{n}} 2^{\operatorname{inv}(\sigma)+\operatorname{rec}(\sigma)}
$$
We will calculate this sum by recurrence. Let's start by building a correspondence between $\mathfrak{S}_{n+1}$ and $\mathfrak{S}_{n} \times\{1, \ldots, n+1\}$. Let $\sigma \in \mathfrak{S}_{n+1}$, we denote $k=\sigma(1)$ the image of 1 and we look at $\sigma^{\prime}$ the permutation of $\{1, \ldots, n\}$ obtained by removing 1 and its image. More rigorously:

$$
\sigma^{\prime}(i)= \begin{cases}\sigma(i+1) & \text { if } \sigma(i+1)k\end{cases}
$$

I leave it to you to show that we indeed obtain a permutation and that the correspondence is bijective. Then we need to express the number of inversions and records of $\sigma$ in terms of $k$ and $\sigma^{\prime}$. Verify that:

- if $k=1$, then $\sigma$ has 1 more record than $\sigma^{\prime}$ (the one at 1) and the same number of inversions.
- if $k>1$, then $\sigma$ has $k-1$ more inversions than $\sigma^{\prime}$, all those taking 1 and $j$ with $\sigma(j)<k$, and the same number of records. Hence:

$$
\begin{aligned}
\sum_{\sigma \in \mathfrak{S}_{n+1}} 2^{i n v(\sigma)+r e c(\sigma)} & =\sum_{k=1}^{n+1} \sum_{\sigma^{\prime} \in \mathfrak{S}_{n}} 2^{i n v(\sigma)+r e c(\sigma)} \\
& =\sum_{\sigma^{\prime} \in \mathfrak{S}_{n}}\left(2^{i n v\left(\sigma^{\prime}\right)+\left(r e c\left(\sigma^{\prime}\right)+1\right)} \sum_{k=2}^{n+1} 2^{\left(i n v\left(\sigma^{\prime}\right)+k-1\right)+r e c\left(\sigma^{\prime}\right)}\right) \\
& =\left(2+2+2^{2}+2^{3}+\cdots+2^{n}\right) \cdot\left(\sum_{\sigma^{\prime} \in \mathfrak{S}_{n}} 2^{i n v\left(\sigma^{\prime}\right)+r e c\left(\sigma^{\prime}\right)}\right) \\
& =2^{n+1}\left(\sum_{\sigma^{\prime} \in \mathfrak{G}_{n}}\right) 2^{i n v\left(\sigma^{\prime}\right)+r e c\left(\sigma^{\prime}\right)}
\end{aligned}
$$

We have finally managed to obtain our recurrence formula. Then we calculate the sum for $n=1$ and we find 2. It is easy to show that the final sum is $2^{1+2+\cdots+(n+1)}$.

$$
\sum_{\sigma \in \mathfrak{S}_{n}} 2^{i n v(\sigma)+r e c(\sigma)}=2^{\frac{n(n+1)}{2}}
$$

## 2 Arithmetic and Inequality Test (3h)

## Statements