Mes premiers doubles comptages

1. Si on considère une partie de $[\![1,n]\!]$, il y en a $a_n$, c’est notre premier comptage, rapide.

Pour l’autre côté, chaque partie de $[\![1,n]\!]$ contient ou non $1$. Si elle contient $1$, alors elle est caractérisée comme $\{1\} \cup B$ où $B$ est une partie de $[\![2,n]\!]$, contenant $n-1$ éléments, donc il y en a $a_{n-1}$. De la même manière, si notre partie ne contient pas $1$, alors c’est une partie de $[\![2,n]\!]$, et il y en a aussi $a_{n-1}$. Finalement, cela nous donne la formule $a_n = a_{n-1} + a_{n-1} = 2a_{n-1}$.
En ajoutant le fait que les parties de $\{1\}$ (partie $n=1$) sont $\{1\}$ et le vide $\emptyset$, on a $a_1=2$. Donc finalement on retrouve bien $a_n= 2^{n-1} a_1=2^n$.

2. Il existe $b_n$ permutations de $[\![1,n]\!]$, c’est aussi notre premier comptage (super rapide).
   Si on prends une permutation de $[\![1,n]\!]$, on peut considérer l’image de $1$ par cette dernière, notons-là $i$. Il y a $n$ choix pour $i$, et ainsi il reste à construire une permutation de $[\![1,n]\!]\backslash\{1\}$ dans $[\![1,n]\!]\backslash \{i\}$, soit deux ensembles à $n-1$ éléments, et il y en a $b_{n-1}$. Ce qui donne la formule $b_n = n \times b_{n-1}$.
   En ajoutant le fait que la seule permutation de $\{1\}$ dans $\{1\}$ est l’identité, on a $b_1=1$ donc $b_n = n!$ et on retrouve notre résultat connu !