Qu'est-ce que « Arrangements, permutations, combinaisons » ?

Exemple 2.14 (Ajouter une contrainte)

Poursuivons avec la table ronde : parmi les $(n-1)!$ tables de $n \geq 3$ convives, combien séparent deux convives donnés $A$ et $B$ (non voisins) ? Comptons le complémentaire. Les tables où $A$ et $B$ sont assis côte à côte : collons-les en un seul bloc — $n - 1$ objets autour de la table, soit $(n-2)!$ dispositions circulaires — puis ordonnons la paire à l’intérieur de son bloc ($2$ façons) : $2\,(n-2)!$ tables où ils sont voisins. Donc

tables les séparent. Vérifications : $n = 3$ donne $0$ (autour d’un triangle, tout le monde touche tout le monde) et $n = 4$ donne $2$, faciles à lister à la main. L’astuce du collage — traiter un bloc imposé comme un seul objet, puis compter ses dispositions internes — est le remède standard aux contraintes de voisinage, linéaires ou circulaires.

Exemple 2.18 (Une identité, deux démonstrations)

La spécialisation $a = 2$, $b = 1$ de la formule du binôme s’écrit

Voici la même identité sans le moindre calcul algébrique. Le membre de droite compte les mots de longueur $n$ sur l’alphabet $\{0, 1, 2\}$ (règle du produit). Classons chaque mot selon l’ensemble $K$ des positions portant une lettre non nulle : choisir $K$ avec $\abs K = k$ coûte $\binom nk$, puis chaque position de $K$ porte indépendamment $1$ ou $2$ : $2^k$ façons. La règle de somme sur $k$ donne le membre de gauche. Au-delà du plaisir de l’accord, les deux démonstrations ont des vertus différentes : l’algébrique se généralise à toute valeur de $a$, la combinatoire explique la formule et s’adapte à des contraintes (interdire la lettre $2$ en dernière position, par exemple) qu’aucune substitution ne capture. Garder les deux techniques actives est la compétence pratique que ce chapitre entraîne.

Exemple 2.6 (La finitude est essentielle)

Sur un ensemble fini, la Proposition 2.5 est un raccourci puissant : toute application injective de $E$ dans lui-même est automatiquement une permutation de $E$ — la moitié de la bijectivité est offerte. Les deux implications s’effondrent sur les ensembles infinis : $n \mapsto n + 1$ est injective de $\N$ dans $\N$ mais rate $0$, et l’application $\N \to \N$ qui envoie $0 \mapsto 0$ et $n \mapsto n - 1$ pour $n \geq 1$ est surjective sans être injective. Chaque fois que cette proposition est invoquée, l’hypothèse de finitude travaille réellement — un thème que le devoir maison du Chapitre 1 explore par l’autre bout, là où les ensembles infinis sont précisément ceux qui admettent de telles applications d’eux-mêmes dans eux-mêmes.