Exercices de Dénombrement, Sup (prépa)

$(a)$ Pour $A\subset [[1,n]]$, notons $S_A=\{\sigma \in {\mathfrak{S}}_n\mid \forall x\in A,\sigma (x)=x\text{ et }\forall x\notin A,\sigma (x)\ne x\}$. ${\mathfrak{S}}_n$ est la réunion disjointe des $S_A$ pour $A$ parcourant $\mathcal{P}([[1,n]])$. Après indexation des éléments de $A$, une application de $S_A$ peut être identifiée à un dérangement de $[[1,n-k]]$ avec $k=\mathrm{Card}A$. On en déduit $\mathrm{Card}{S}_A=d_{n-k}$ puis$$\mathrm{Card}{\mathfrak{S}}_n=\sum _{A\subset \mathcal{P}(E)}{d}_{n-\mathrm{Card}A}=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_{n-k}.$$Donc $n!=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_{n-k}$.

$(b)$ Raisonnons par récurrence forte sur $n$. La propriété énoncée est vraie aux rangs $0$ et $1$. Supposons la propriété vraie jusqu'au rang $n-1$. Pour $k\in [[0,n]]$, posons $d_k^{\prime }=\sum _{\ell =0}^k(-1{)}^{k-\ell }(\genfrac{}{}{0ex}{}{k}{\ell })\ell !$. Par hypothèse de récurrence $d_k=d_k^{\prime }$ pour $k\in [[0,n-1]]$ et on veut établir l'identité pour $k=n$. Or$$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_{n-k}^{\prime }=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_k^{\prime }=\sum _{k=0}^n\sum _{\ell =0}^k(-1{)}^{\ell -k}(\genfrac{}{}{0ex}{}{n}{k}\left)\right(\genfrac{}{}{0ex}{}{k}{\ell })\ell !$$Par échange des deux sommes puis glissement d'indice dans la deuxième somme et expression factorielle des coefficients binomiaux :$$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_{n-k}^{\prime }=\sum _{\ell =0}^n\frac{n!}{(n-\ell )!}\sum _{k=0}^{n-\ell }(-1{)}^k(\genfrac{}{}{0ex}{}{n-\ell }{k}).$$Or $\sum _{k=0}^{n-\ell }(-1{)}^k(\genfrac{}{}{0ex}{}{n-\ell }{k})=(1+(-1){)}^{n-\ell }=\{\begin{array}{ll}0& \text{si }n-\ell >0\\ 1& \text{si }n=\ell \end{array}$
donc $\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_{n-k}^{\prime }=n!=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)d_{n-k}$.
On en déduit $d_n^{\prime }=d_n$ puisque l'hypothèse de récurrence a fourni les identifications $d_k=d_k^{\prime }$ pour $k\in [[0,n-1]]$. Récurrence établie.

1. Par définition de la fonction indicatrice, $1_A(x)=1$ si $x\in A$ et $1_A(x)=0$ si $x\notin A$. Donc :$$\sum _{x\in E}{1}_A(x)=|\{x\in E:x\in A\}|=\mathrm{card}(A)$$2. On a $A=\bigcap _{i=1}^n{A}_i$. On veut montrer que $\prod _{i=1}^n(1_A-1_{A_i})=0$, c'est-à-dire que pour tout $x\in E$, $\prod _{i=1}^n(1_A(x)-1_{A_i}(x))=0$.

Soit $x\in E$. Deux cas se présentent :
- Si $x\in A=\bigcap _{i=1}^n{A}_i$ : alors $x\in A_i$ pour tout $i$, donc $1_A(x)=1$ et $1_{A_i}(x)=1$ pour tout $i$. Chaque facteur vaut $1-1=0$, donc le produit est nul.
- Si $x\notin A$ : alors $1_A(x)=0$ et il existe $i_0$ tel que $x\notin A_{i_0}$, donc $1_{A_{i_0}}(x)=0$. Le facteur correspondant vaut $0-0=0$, donc le produit est nul.

Dans tous les cas, le produit est nul.

3. On développe le produit $\prod _{i=1}^n(1_A-1_{A_i})=0$ en utilisant la multilinéarité.

On note que $1_A=\prod _{i=1}^n{1}_{A_i}$ (car $A=\bigcap _{i=1}^n{A}_i$). De plus, pour des fonctions indicatrices, $1_{A_i}\cdot 1_{A_j}=1_{A_i\cap A_j}$.

En développant $\prod _{i=1}^n(1_A-1_{A_i})$ :$$0=\sum _{J\subseteq [[1,n]]}(-1{)}^{|J|}{1}_A^{n-|J|}\cdot \prod _{j\in J}{1}_{A_j}$$Comme $1_A\le 1_{A_i}$ pour tout $i$, on a $1_A^{n-|J|}\cdot \prod _{j\in J}{1}_{A_j}=\prod _{j\in J}{1}_{A_j}\cdot 1_A^{n-|J|}$. Pour $J\ne [[1,n]]$, puisque les facteurs $1_A$ absorbent dans l'intersection, on obtient $1_{{\bigcap }_{j\in J}{A}_j}$ si $J\ne \varnothing$ et $1_A$ si $J=\varnothing$.

Procédons plus directement. En sommant sur $x\in E$ l'identité $\prod _{i=1}^n(1_A(x)-1_{A_i}(x))=0$ et en développant :$$\sum _{x\in E}\sum _{J\subseteq [[1,n]]}(-1{)}^{|J|}\prod _{j\in J}{1}_{A_j}(x)\cdot 1_A(x{)}^{n-|J|}=0$$Puisque $1_A=\prod _{i=1}^n{1}_{A_i}$, on simplifie. En développant plutôt $\prod _{i=1}^n(1_{A_i}-1_A)=0$ et en isolant le terme $J=\varnothing$ :$$1_A^n=\sum _{k=1}^n(-1{)}^{k-1}\sum _{1\le i_1<\cdots <i_k\le n}\prod _{j=1}^k{1}_{A_{i_j}}\cdot 1_A^{n-k}$$Or $1_A^n=1_A$ et $\prod _{j=1}^k{1}_{A_{i_j}}\cdot 1_A^{n-k}=1_{{\bigcap }_{j=1}^k{A}_{i_j}}$ (car $A\subseteq A_{i_j}$).

En sommant sur $x\in E$ et en utilisant la question 1 :$$\mathrm{card}(A)=\sum _{k=1}^n(-1{)}^{k-1}\sum _{1\le i_1<\cdots <i_k\le n}\mathrm{card}\left(\bigcap _{j=1}^k{A}_{i_j}\right)$$