Anagramme
Une anagramme d’un mot est une permutation de ses lettres. Par exemple, « ruine » est une anagramme de « nuire ». Les anagrammes sont strictement liées aux permutations, en effet les permutations de ne sont rien d’autre que la représentation abstraite des toutes les anagrammes possibles d’un mot de lettres.
Nombre d’anagrammes
Il est facile de voire qu’un mot de lettres distinctes a exactement anagrammes. En effet, pour former une anagramme à partir de lettres, on a choix pour la première lettre, choix pour la deuxième et ainsi de suite.
On peut voir cela de façon récursive. On note le nombre d’anagrammes. On commence par choisir la première lettre de notre anagramme, ce qui fait possibilités ; il reste lettres à déterminer, et tous les anagrammes du mot de lettres restantes sont acceptables. On déduit
et, puisque , on déduit .
Anagrammes avec répétitions
Le calcul est un peu plus compliqué lorsque le mot présente des lettres répétées. Par exemple, le mot « abba » a seulement six anagrammes possibles, à savoir « baab », « baba », « abab », « bbaa », « aabb » et « abba » lui-même. Ce nombre est bien moindre que .
Pour trouver le nombre exact d’anagrammes d’un mot avec répétitions, on numérote les lettres répétées afin de les distinguer. « abba » devient
Comme toutes les lettres sont différentes, ce nouveau mot a maintenant anagrammes, mais plusieurs anagrammes correspondent au même mot dès qu’on enlève les indices. En effet, les mots
correspondent tous au même mot « abba ». On voit que si un mot a une lettre répétée fois, à chaque anagramme du mot d’origine, correspondent anagrammes équivalents avec cette lettre numérotée.
En conclusion, un mot de longueur , contenant répétitions de la lettre , répétitions de la lettre et ainsi de suite a exactement
anagrammes.