Le dénombrement 165
1850
Kirkman pose le problème
des 15 pensionnaires.
1930
Franck Ramsey travaille
dans le domaine de l’analyse
combinatoire.
1971
Ray-Chaudhuri et Wilson
prouvent l’existence
des systèmes généraux
de Kirkman.
étaient tous présents. Combien venaient de Saint Ives ? Le tableau suivant nous
donne une réponse.
Homme
1
1
Femmes
7
7
Sacs
7 × 7
49
Chats
7 × 7 × 7
343
Chatons
7 × 7 × 7 × 7
2 401
Total
2 801
Lors d’un séjour à Luxor en 1858, Alexander Rhind, antiquaire écossais, découvrit
par hasard un papyrus de 5 mètres de long couvert de formules mathématiques
remontant à 1800 av. J.-C. Il l’acheta. Quelques années plus tard, le British Museum
l’acquit et les hiéroglyphes furent traduits. Le problème 79 du Papyrus Rhind est
un problème de maisons, de chats, de souris et de blé qui ressemble fortement à
celui des chatons, chats, sacs et femmes de Saint Ives. Ils impliquent tous deux des
puissances de 7 et le même type d’analyse. L’analyse combinatoire a, semble-t-il,
une bien longue histoire.
Les factorielles Avec le problème des files d’attente, nous sommes en présence
de la première arme de l’arsenal combinatoire : les factorielles. Supposons qu’Alban,
Brice, Charlotte, David et Émilie forment une file d’attente
E C A B D.
Émilie est en tête, suivie de Charlotte, d’Alban et de Brice qui est lui-même suivi de
David, le dernier de la file. Si l’on change les personnes de place, on obtient d’autres
files d’attente ; combien de files d’attente différentes sont-elles possibles ?
L’art du dénombrement dans ce problème dépend du choix. Il existe 5 choix possibles pour la personne qui occupera la première place de la file, et une fois que cette
personne a été choisie, il existe 4 choix pour la seconde, et ainsi de suite. Lorsque
l’on arrive à la dernière position, il ne reste aucun choix possible car elle ne peut
être occupée que par la dernière personne non placée. Il y a donc 5 × 4 × 3 × 2 × 1
= 120 files d’attente possibles. Si l’on avait commencé avec 6 personnes, le nombre
de files possibles serait 6 × 5 × 4 × 3 × 2 × 1 = 720 et pour 7 personnes, il y aurait
7 × 6 × 5 × 4 × 3 × 2 × 1 = 5 040 files possibles.
Le produit de nombres entiers consécutifs de 1 à n s’appelle une factorielle. On en
trouve si souvent en mathématiques que l’on préfère les écrire sous la forme 5! (qui
se lit « factorielle 5 ») plutôt que sous la forme 5 × 4 × 3 × 2 × 1. Examinons les
1850
Kirkman pose le problème
des 15 pensionnaires.
1930
Franck Ramsey travaille
dans le domaine de l’analyse
combinatoire.
1971
Ray-Chaudhuri et Wilson
prouvent l’existence
des systèmes généraux
de Kirkman.
étaient tous présents. Combien venaient de Saint Ives ? Le tableau suivant nous
donne une réponse.
Homme
1
1
Femmes
7
7
Sacs
7 × 7
49
Chats
7 × 7 × 7
343
Chatons
7 × 7 × 7 × 7
2 401
Total
2 801
Lors d’un séjour à Luxor en 1858, Alexander Rhind, antiquaire écossais, découvrit
par hasard un papyrus de 5 mètres de long couvert de formules mathématiques
remontant à 1800 av. J.-C. Il l’acheta. Quelques années plus tard, le British Museum
l’acquit et les hiéroglyphes furent traduits. Le problème 79 du Papyrus Rhind est
un problème de maisons, de chats, de souris et de blé qui ressemble fortement à
celui des chatons, chats, sacs et femmes de Saint Ives. Ils impliquent tous deux des
puissances de 7 et le même type d’analyse. L’analyse combinatoire a, semble-t-il,
une bien longue histoire.
Les factorielles Avec le problème des files d’attente, nous sommes en présence
de la première arme de l’arsenal combinatoire : les factorielles. Supposons qu’Alban,
Brice, Charlotte, David et Émilie forment une file d’attente
E C A B D.
Émilie est en tête, suivie de Charlotte, d’Alban et de Brice qui est lui-même suivi de
David, le dernier de la file. Si l’on change les personnes de place, on obtient d’autres
files d’attente ; combien de files d’attente différentes sont-elles possibles ?
L’art du dénombrement dans ce problème dépend du choix. Il existe 5 choix possibles pour la personne qui occupera la première place de la file, et une fois que cette
personne a été choisie, il existe 4 choix pour la seconde, et ainsi de suite. Lorsque
l’on arrive à la dernière position, il ne reste aucun choix possible car elle ne peut
être occupée que par la dernière personne non placée. Il y a donc 5 × 4 × 3 × 2 × 1
= 120 files d’attente possibles. Si l’on avait commencé avec 6 personnes, le nombre
de files possibles serait 6 × 5 × 4 × 3 × 2 × 1 = 720 et pour 7 personnes, il y aurait
7 × 6 × 5 × 4 × 3 × 2 × 1 = 5 040 files possibles.
Le produit de nombres entiers consécutifs de 1 à n s’appelle une factorielle. On en
trouve si souvent en mathématiques que l’on préfère les écrire sous la forme 5! (qui
se lit « factorielle 5 ») plutôt que sous la forme 5 × 4 × 3 × 2 × 1. Examinons les