Mes premiers doubles comptages

On note $a_n$ le cardinal de l’ensemble des parties de $[\![1,n]\!]$ (que l’on ne suppose pas connu ici !). Compter le nombre de parties de $[\![1,n]\!]$ qui contiennent $1$ et celles qui ne contiennent pas $1$ en fonction de $a_{n-1}$ . En déduire, par récurrence, la valeur de $a_n$ pour tout $n$ .
On note $b_n$ le cardinal de l’ensemble des permutations de $[\![1,n]\!]$ (que l’on ne suppose pas connu ici non plus). On se donne un entier $k$ entre $1$ et $n$ .
Compter le nombre de permutations de $[\![1,n]\!]$ qui envoient $1$ sur $k$ en fonction de $b_{n-1}$ . En déduire par récurrence la valeur de $b_n$ en fonction de $n$ .

I solved itMark it done Add to my listKeep it in your list

I like this problem1 like

Liked by

Ancient Tree@ancient-tree

Solutions

Reveal solutionsAre you sure? Give it a try first.

Solution by Sequoia

Discussions0 useful votes

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

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 !

Report