Objets Combinatoires

élementaires

0-0
 ' Combinatoire pour les informaticiens
$

• Permutations
– Arrangements
– Permutations pour un multi-ensemble
• mots
• sous-ensemble à k éléments (Problème du
choix)
• Compositions

& %
LE2I 04 1
 ' Combinatoire pour les informaticiens
$

Permutations
Supposons que nous avons n personnes qui
arrivent dans un cabinet dentaire au même
moment. Le dentiste ne peut que les prendre un
par un, alors il doit décider l’ordre dans lequel il
doit les faire passer. Combien y a t il d’ordres
possibles?

Soit A = {a1 , a2 . . . an } un ensemble contenant n

objets. Combien existe t il de mots différents de
la forme :

x1 , x2 . . . xn , xi 6= xj , xi ∈ A

& %
LE2I 04 2
 ' Combinatoire pour les informaticiens
$

Définition Les arrangements de différents objets

en ordre linéaire utilisant chaque objet
exactement une fois est appelé une permutation
de ces objets. Le nombre

n · (n − 1) · · · (n − 2) · . . . · 1

de toutes les permutations de n objects est appelé

n f actoriel, et est noté n!.

& %
LE2I 04 3
 ' Combinatoire pour les informaticiens
$

Théorème Le nombre de toutes les permutations

d’un ensemble à n éléments est n!

√  n n
n! ∼ 2πn
e

Exemple Combien de manières différentes peut

on construire des drapeaux avec les 3 couleurs
rouge, blanc et vert?

& %
LE2I 04 4
 ' Combinatoire pour les informaticiens
$

Arrangements
Définition Le choix de k objets différents parmis
n objets en utilisant chaque objet au plus une fois
est appelé arrangement de ces objets.
Théorème Le nombre d’arrangement de k
élements parmi n est

n!
n · (n − 1) · (n − 2) · · · (n − k + 1) = = (n)k
(n − k)!

Le nombre

n · (n − 1) · · · (n − 2) · . . . · 1

de toutes les permutations de n objets est appelé

n f actoriel, et est noté n!.

& %
LE2I 04 5
 ' Combinatoire pour les informaticiens
$

Exemple Un président doit choisir cinq

politiciens parmi 20 candidats pour occuper cinq
différents cabinets ministériels.
Combien de choix possibles a t il?

& %
LE2I 04 6
 ' Combinatoire pour les informaticiens
$

Permutations pour un
multi-ensemble
Un multi-ensemble est un ensemble sauf que la
répétition des éléments est permise.
Les arrangements de différent objets en ordre
linéaire utilisant exactement ni fois l’ objet i avec
(n1 + n2 + . . . + nk = n) est appelé permutation
d’un multi-ensemble.
Notons que si ni = 1 pour tout i alors on a une
permutation ordinaire sans élément répété.

& %
LE2I 04 7
 ' Combinatoire pour les informaticiens
$

Théorème Avec les notations ci-dessus, le

nombre de permutations d’un multi-ensemble (ou
le nombre de façons de ranger linéairement ces
objets) est

n!
n1 ! · n 2 ! · · · · n k !

Exemple Un jardinier a 5 fleurs rouges, 3 jaunes

et 2 blanches pour planter en une rangée.
Combien y a t il de motifs possibles?

& %
LE2I 04 8
 ' Combinatoire pour les informaticiens
$

Mots
Maintenant nous étudions les problèmes dans
lesquels nous n’arrangerons pas simplement les
objets, en connaissant combien de fois on peut
utiliser chaque symbole, mais mais plutot en
construisant des mots à partir d’un ensemble fini
de symboles, ce que nous appelons un alphabet
fini.
Nous n’avons pas besoin que les symboles
apparaissent un nombre de fois spécifique.

Théorème Le nombre de mots de longueur k sur

l’alphabet à n éléments est nk .

& %
LE2I 04 9
 ' Combinatoire pour les informaticiens
$

Exemple Le nombre de sous-ensembles d’un

ensemble à n éléments est 2n

Preuve On construit une bijection de l’ensemble

de tous les sous-ensembles d’un ensemble à n
éléments vers les mots de longueur n sur
l’alphabet binaire {0, 1}. Comme ce dernier
ensemble a 2n éléments, on obtient le résultat.

La bijection est construite de la façon suivante:

Soit B un sous-ensemble de {1, 2, . . . , n} et soit

f (B) le mot ayant un 1 en i-ième position si et
seulement si i ∈ B and 0 sinon.

& %
LE2I 04 10
 ' Combinatoire pour les informaticiens
$

Exemple Une ville a construit récemment 10

rond points. Certains d’entre eux auront un
éclairage, et d’autres auront un éclairage avec une
station essence. Combien y a t il de possibilités?
Proof Il est facile de construire une bijection de
l’ensemble de toutes distributions de lumière et de
station essences sur les mots de longueur 10 sur
l’alphabet {0, 1, 2}.
Pour chaque distribution de ces objets, on définit
le mot sur {0, 1, 2} comme suit:
• si l’intersection i a une station essence et un
éclairage, alors on met le chiffre 2 sur la ième
lettre du mot
• si seulement il y a un éclairage on met 1 sur
la ième lettre du mot,
• dans les autres cas on met 0

& %
LE2I 04 11
 ' Combinatoire pour les informaticiens
$

Sous-ensemble à (problème du choix)

Exemple A la lotterie nationale de Hongrie, cinq
nombres sont sélectionnés aléatoirement dans
l’ensemble {1, 2, . . . , 90}. Pour gagner le gros lot,
on doit deviner tous les 5 nombres correctement.
Combien de tickets a t on besoin de jouer pour
etre sur d’avoir le gros lot.

& %
LE2I 04 12
 ' Combinatoire pour les informaticiens
$

Cette question est un exemple du dernier et plus

important et interessant problème d’énumération
élémentaire, le problème du choix. Dans ce genre
de problème, nous avons à choisir des
sous-ensembles dans un ensemble donné. Nous
supposerons toujours que les sous-ensembles ont
une taille donnée. La différence importante avec
les problèmes précédents est que l’ordre des
éléments du sous-ensemble n’a aucune
importance; Par exemple {1, 43, 52, 8, 3} et
{3, 8, 52, 1, 43} sont deux sous-ensembles
identiques de {1, 2, . . . , 90}.

& %
LE2I 04 13
 ' Combinatoire pour les informaticiens
$

Le nombre de sous-ensembles à k éléments dans

{1, 2, . . . , n} a une importance cruciale en
combinatoire.
Définition Le nombre de sous-ensembles à k
n


éléments dans {1, 2, . . . , n} est noté k et appelé
coefficient binomial

Théorème Pour tout entier k positif ou nul

k ≤ n, on a

 
n n! (n)k
= =
k k!(n − k)! k!

& %
LE2I 04 14
 ' Combinatoire pour les informaticiens
$

Proposition Pour tout entier k positif ou nul

k ≤ n, on a

   
n n
=
k n−k
   
n n
= =1
0 n

& %
LE2I 04 15
 ' Combinatoire pour les informaticiens
$

Exemple Un étudiant en médecine doit travailler

dans un hopital pour 5 jours en janvier. Il ne doit
pas travailler 2 jours consécutifs dans un hopital.
De combien de manières peut il choisir les 5 jours?

Exemple Maintenant on suppose que nous

jouons a la lotterie ou 5 nombres sont tirés parmis
{1, 2, . . . , 90}, mais les nombres tirés sont remis
en jeu après etre sélectionnés. Pour gagner le
jackpot, on doit jouer le même multi-ensemble de
nombres que le tirage (l’ordre ici n’a pas
d’importance). Combien de ticket dois je acheter
pour etre sur d’avoir le jackpot?

& %
LE2I 04 16
 ' Combinatoire pour les informaticiens
$

Théorème le nombre de multi-ensembles à k

éléments parmis {1, 2, . . . , n} est

 
n+k−1
k

& %
LE2I 04 17
 ' Combinatoire pour les informaticiens
$

Permuts n objets distincts n!

n!
k objets distincts (n)k = (n−k)!

parmis n objets
n!
ai objets n1 !·n2 !····nk !

de type i
k
i=1 ai = n
mots mots de longueur k nk
(words) sur un alphabet
à n letters
n
Sous-ens. sous-ens. à k éléments

k 

de {1, . . . n}
n+k−1
Multi-ens. de k éléments

k 

avec des éléments dans

{1, . . . n}

& %
LE2I 04 18
 ' Combinatoire pour les informaticiens
$

Autres objets combinatoires

& %
LE2I 04 19
 ' Combinatoire pour les informaticiens
$

Compositions
Supposons que nous avons à distribuer 30 balles
identiques pour quatre enfants: Alice, Bob,
Charlie and Denise. Comme les balles sont
identiques, cela revient à savoir combien de balles
devrais je donner à chaque enfant. Alors si nous
voulons savoir le nombre de facons de distribuer
ces balles, nous avons simplement à savoir le
nombre de facons d’écrire 20 comme une somme
de 4 entiers positifs ou nuls. Clairement, l’ordre
des entiers importe, c’est à dire, 1 + 6 + 8 + 5 ne
correspond pas à la même distribution que
6 + 1 + 5 + 8.
Définition Un tableau a1 a2 . . . ak avec
• ai ≥ 0
• a 1 + a2 + . . . + a k = n
est appelé une composition de n. Si nous avons
aussi ai > 0 pour tout i, alors le tableau
a1 a2 . . . ak est appelé composition faible de n.

& %
LE2I 04 20
 ' Combinatoire pour les informaticiens
$

Théorème Le nombre de compositions de n en k

parties est
   
n+k−1 n+k−1
=
k−1 n

Théorème Le nombre de compositions faible de

n en k parties est
 
n−1
k−1

& %
LE2I 04 21
 ' Combinatoire pour les informaticiens
$

Corollary Le nombre de toutes les compositions

faibles de n est 2n−1
Preuve Une composition faible de n aura au
moins une et au plus n parties. Alors le nombre
total compositions faibles de n est

n  
X n−1
= 2n−1
k−1
k=1

& %
LE2I 04 22
 ' Combinatoire pour les informaticiens
$

Partitions d’un ensemble

Maintenant supposons que les balles sont
différentes, mais les boites ne le sont pas. Alors
on doit étiqueter les balles de 1 à n. En d’autres
termes, on doit simplement dire que nous voulons
partitionner l’ensemble {1, 2, . . . , n} en k
sous-ensembles non vide.

Définition Le nombre de partitions de

{1, 2, . . . , n} en k parties non vide est noté
S(n, k), et il est appelé le nombre de Stirling de
seconde espèce.

& %
LE2I 04 23
 ' Combinatoire pour les informaticiens
$

Exemple L’ensemble {1, 2, 3, 4} a 7 partitions en

deux parties non vide:
• {1, 2, 3}, {4}
• {1, 2, 4, }, {3}
• {1, 3, 4}, {2}
• {2, 3, 4, }, {1}
• {1, 2}, {3, 4}
• {1, 3}, {2, 4}
• {1, 4}, {2, 3}

& %
LE2I 04 24
 ' Combinatoire pour les informaticiens
$

Exemple
• Pour tout n ≥ 1, on a S(n, 1) = S(n, n) = 1.
n


• Pour tout n ≥ 2, on a S(n, n − 1) = 2
puisqu une partition de {1, 2, . . . , n} en n − 1
parties doit etre faite de 1 doublon et de
n − 2 singletons.

Théorème Pour rout entier positif k ≤ n, on a

S(n, k) = S(n − 1, k − 1) + k · S(n − 1, k)

& %
LE2I 04 25
 ' Combinatoire pour les informaticiens
$

Corollaire Le nombre de toutes les fonctions

surjectives

f : {1, 2, . . . , n} → {1, 2, . . . , k}

est k! · S(n, k)

Une autre facon de trouver notre énumeration de

partitions est en énumerant toutes les partitions,
sans restreindre le nombre de parties.

& %
LE2I 04 26
 ' Combinatoire pour les informaticiens
$

Définition Le nombre de toutes les partitions

d’ensemble de {1, 2, . . . , n} en parties non vide est
noté B(n), et est appelé le nème nombre de Bell.
Pn
Alors B(n) = i=1 S(n, i), le nombre de Bell
satisfait aussi une jolie relation de récurrence.
Théorème Pour tout entier positif n on a
n  
X n
B(n + 1) = B(i)
i=0
i

& %
LE2I 04 27
 ' Combinatoire pour les informaticiens
$

partition d’entier
Maintenant nous supposons que les balles et les
boites sont indistinguables, alors quand on
distribue les balles dans les boites, la seule chose
qui importe est leurs nombres. EN d’autres
termes, on est interessé de trouver le nombre de
facons d’écrire un entier positif n comme une
somme d’entiers positifs, ou l’ordre de sommation
n’a pas d’importance. C’est à dire, 4 = 3 + 1 ou
4 = 1 + 3 seront comptés pour une seule
sommation pour l’entier 4.
Comme l’ordre de sommation ne compte pas, on
ne perd pas de generalité si on suppose que la
sommation est en ordre décroissant (faible).

& %
LE2I 04 28
 ' Combinatoire pour les informaticiens
$

Définition Soit a1 ≥ a2 ≥ . . . ≥ ak ≥ 1 des

entiers tels que a1 + a2 + . . . + ak = n. Le tableau
a1 a2 . . . ak est appelé une partition de l’entier n.
Le nombre de toutes les partitions de n est noté
p(n).Le nombre de partitions de n en exactement
k parties est noté pk (n).
Exemple L’entier 5 a 7 partitions. En effet, il y a
• 5
• 4+1
• 3+2
• 3+1+1
• 2+2+1
• 2+1+1+1
• 1+1+1+1+1
Donc, p(5) = 7.

& %
LE2I 04 29
 ' Combinatoire pour les informaticiens
$

objets distincts objets identiques

boites distinctes boites distinctes
objets distincts objects identiques
boites identiques boites identiques

• – nombre fixé de boites

– nombre quelconque de boites
• – pas de boite vide
– boite vide autorisé

& %
LE2I 04 30
 ' Combinatoire pour les informaticiens
$

Enumeration formulae if no boxes

are empty
Surjection n objets distincts S(n, k) · k!
k boites distincts
n
n objets distincts 

i=1 S(n, i) · i!
nombre quelconque
de boites distinctes
n−1
Compositions n objets identiques 

k−1 

faibles k boites distinctes

n objets identiques 2n−1
nombre quelconque de
boites distinctes
partitions n objets distincts S(n, k)
d’ens. k boites identiques
n identiques objets B(n)
number quelconque
de boites identiques
partition n identiques objets pk (n)
d’entier k identiques boites
n identiques objets p(n)
nombre quelconque
de boites identiques

& %
LE2I 04 31
 ' Combinatoire pour les informaticiens
$

formule d’énumération pour les

boites vides autorisées
Fonction n distincts objets kn
k distinctes boites
n+k−1
Compositions n identiques objets 

k−1 

k distinctes boites
k
partitions d’ensemble n distincts objets 

i=1 S(n, i)
k identiques boites
k
partitions d’entier n identiques objets 

i=1 pi (n)
k identiques boites

& %
LE2I 04 32
 ' Combinatoire pour les informaticiens
$

objets combinatoires plus élaborés

• mots de Dyck
• mots de Schröder
• mots de Motzkin
• Colliers
• mots de Lyndon

& %
LE2I 04 33
 ' Combinatoire pour les informaticiens
$

Mots de Dyck
Définition L’ensemble D(`) des mots de Dyck de
longueur 2` est l’ensemble des mots w écrits avec
les lettres {a, b} satisfaisant
• la propriété du préfix chaque prefix a au mois
plus d’occurrences de a que de b
• |w|a = |w|b

& %
LE2I 04 34
 ' Combinatoire pour les informaticiens
$

Mots de Motzkin
Définition L’ensemble M (n) des mots de
Motzkin de longueur n est l’ensemble des mots w
écrits avec des lettres de X = {a, b, 0} satisfaisant
• La propriété du préfix chaque prefix a au
mois plus d’occurrences de a que de b
• |w|a = |w|b

& %
LE2I 04 35
 ' Combinatoire pour les informaticiens
$

Necklaces - Colliers
Définition A k-aire necklace (ou collier) est une
classe d’équivalence de mots of k-aire modulo
rotation.
Exemple Il y a exactement 6 classes
d’équivalences pour les mots binaires de longueur
4.
0000 0001 0011 0101 0111 1111
0010 0110 1010 1011
0100 1100 1101
1000 1001 1110

On prend le plus petit lexicographiquement pour

le représentant de chaque classe

& %
LE2I 04 36
 ' Combinatoire pour les informaticiens
$

Mots de Lyndon
Définition Un mot de Lyndon est une
aprériodique necklace
0001
0011
0111

& %
LE2I 04 37
 ' Combinatoire pour les informaticiens
$

Quel est la cardinalité des necklaces

et des mots de Lyndon?

& %
LE2I 04 38
 ' Combinatoire pour les informaticiens
$

La fonction φ(m), la fonction d’Euler, est le

nombre de k dans l’intervalle 1 ≤ k ≤ m qui sont
prmiers avec m.
Exemple
φ(1) = |{1}| = 1
φ(6) = |{1, 5}| = 2

& %
LE2I 04 39
 ' Combinatoire pour les informaticiens
$

Théorème
X
φ(d) = n
d|n

Théorème Le nombre de k-aire necklaces de

longueur n est

1 X n d
Nk (n) = φ ·k
n d
d|n

& %
LE2I 04 40
 ' Combinatoire pour les informaticiens
$

La fonction µ(m) est la fonction de Möbius:

• 0 Si m est le produit de premiers non
distincts,
• +1 si c est le produit d’un nombre pair de
premiers distincts,
• -1 dans les autres cas
avec µ(1) = 1
Exemple
µ(18) = 0
µ(6) = 1
µ(7) = −1

& %
LE2I 04 41
 ' Combinatoire pour les informaticiens
$

Théorèm’

X  1 si n = 1
µ(d) =
 0 sinon
d|n

Théorème Le nombre de mots de Lyndon k-aires

de longueur n

1 X n d
Lk (n) = µ ·k
n d
d|n

& %
LE2I 04 42