Previous Up
Mathématiques pour l’Informatique 2013–14                  http://www.lri.fr/~paulin/MathInfo


7  Combinatoire

L’analyse combinatoire consiste à compter les éléments de certains ensembles finis.

7.1  Rappels sur les cardinaux

Dans les chapitres précédents nous avons établi plusieurs résultats importants concernant le dénombrement :

Soit E un ensemble de cardinal p et F un ensemble de cardinal q:

De manière générale, soient n ensembles (Ei)i=1… n tels que chaque Ei a un nombre pi d’éléments alors le produit cartésien E1× … × En a pour cardinal i=1n pi.

On peut généraliser ce résultat de la manière suivante. Si on doit faire n choix consécutifs et qu’à l’étape i, le nombre de choix différents possibles est pi alors le nombre de choix total est i=1n pi. Ce résultat se montre par récurrence sur n.

7.2  Arrangements

Le nombre d’arrangements Ank compte le nombre de manière de choisir en les classant k éléments dans un ensemble E à n éléments.

Le tiercé consite à choisir dans le bon ordre 3 chevaux gagnants parmi les n chevaux en course. Il y a n(n−1)(n−2) combinaisons possibles, soit pour une course de 20 chevaux 6840 combinaisons.

Le nombre d’arrangements de k éléments d’un ensemble E peut se formaliser comme le nombre d’applications injectives de [1,k] dans E.

Pour construire une injection de [1,k] dans E, il suffit de choisir f(1) puis f(2) en satisfaisant f(2)≠f(1) puis f(3) différent des précédents et finalement f(k).

Si k=0 alors l’ensemble [1,k] est vide et il y a une seule application injective.

Si 0<kn alors à l’étape i, il y a ni+1 choix possibles et donc le nombre d’arrangements est

si  k≤ n  alors  Ank=
k
i=1
 (ni+1)=n(n−1)… (nk+1) 

Dans le cas où n<k alors il n’y a pas d’application injective de [1,k] dans E (lemme des tiroirs) et donc le nombre d’arrangements est nul.

si  n < k  alors  Ank=0=
k
i=1
 (ni+1)=n(n−1)… (nk+1) 
Exemple 1   Quatre frères voyagent en train, chacun refuse d’être dans le même compartiment que l’un de ses frères. S’il y a n compartiments, combien y-a-t-il de configurations possibles ?

7.3  Permutations

Une permutation est une application bijective d’un ensemble fini dans lui-même. Le nombre de permutations sur un ensemble E à n éléments est égal au nombre d’arrangements de [1,n] dans E. En effet si on se donne une manière d’énumérer les éléments de E :e1,…,en. Il suffit de se donner pour chaque i la valeur f(i) de l’application pour ei et toute application injective d’un ensemble fini dans un ensemble de même cardinal est bijective. Le nombre de permutations est donc i=1n (ni+1)=n(n−1)… 1. Ce nombre est connu sous le nom de factorielle de n et est noté n!.
La définition récursive de cette fonction est donnée par les équations :

0!=1        (n+1)!=(n+1)n!

On remarque que si kn alors le nombre d’arrangements peut s’exprimer en utilisant la fonction factorielle.

Ank=
n!
(nk)!

7.4  Combinaisons

Dans un arrangement, les éléments choisis sont ordonnés. On cherche parfois à dénombrer des parties dans lesquelles l’ordre n’a pas d’importance. Par exemple si on joue au loto plutôt qu’au tiercé, le but est d’avoir k numéros corrects parmi 49 possibilités, mais l’ordre du tirage n’intervient pas comme critère de gain.

Le nombre de combinaisons de k éléments dans un ensemble à n éléments est noté Cnk.

7.4.1  Propriétés des combinaisons

On peut relier le nombre de combinaisons et le nombre d’arrangements. Si on veut arranger k éléments parmi n on peut d’abord identifier un sous ensemble de k éléments parmi n (on a Cnk possibilités) puis les ordonner (k! différentes possibilités). On obtient au final :

Ank = Cnk k!

On a en particulier Cn0=1, Cnn=1 , Cnk=0 si n<k.

Dans le cas où kn on obtient la formule:

Cnk=
n!
k!(nk)!

Lorsque l’on doit calculer à la main les combinaisons, la formule suivante est utile et valable si 0<k : Cnk=n(n−1)…(nk+1)/k(k−1)… 1. Dans cette formule, on a le même nombre de produits en numérateur et en dénominateur.

On retiendra en particulier les cas suivants : Cn1=n    Cn2=n(n−1)/2

Exemple 2   Une fourmi se déplace sur une grille de longueur n et de hauteur p. Elle part du coin en bas à gauche et doit rejoindre le coin en haut à droite. Elle ne peut que franchir un pas horizontalement vers la droite ou monter d’un cran. Combien y-a-t-il de chemins différents possibles ?
Combinaison et complément.

Si kn alors choisir k éléments parmi n est équivalent à choisir nk éléments parmi n (ceux qui restent). On en déduit la formule :

Cnk=Cnnk
Triangle de Pascal.

On peut également trouver une formule de récurrence pour les combinaisons. Supposons que l’on veuille choisir k éléments dans un ensemble à n+1 éléments et essayons de nous ramener au choix dans un ensemble à n éléments. Dans l’ensemble E qui à n+1 éléments on particularise un élément e. Soit une partie à k éléments dans E avec 1≤ k. Soit elle contient e soit elle ne contient pas e. On compte d’abord le nombre de parties à k éléments qui contiennent e, il y en a exactement autant que le nombre de parties à k−1 éléments dans E∖{e} soit Cnk−1. On compte ensuite le nombre de parties à k éléments qui ne contiennent pas e, il y en a exactement autant que le nombre de parties à k éléments dans E∖{e} soit Cnk. On obtient la formule de récurrence suivante:

Cn+1k=Cnk+Cnk−1

A partir de cette formule on peut construire le Triangle de Pascal qui nous donne les valeurs des nombres de combinaisons juste en faisant des additions. On choisit de mettre l’indice k en colonnes et n en lignes. On peut remplir la première colonne et la diagonale en utilisant Cn0=Cnn=1, pour les autres données, on utilise la formule du binôme en aditionnant la valeur de la case du dessus et de celle dans le coin en haut à gauche.

 0123
0
11
212
3133
41464
  
Exercice 1   Trouver une formule permettant de relier An+1k+1 et Ank.
Formule du binôme.

Les combinaisons apparaissent naturellement dans la formule du binôme :

(x+y)nk=0n Cnk xk ynk

La preuve se fait par récurrence sur n.

Exercice 2   Donner une formule pour développer (x+y+z)n. Généraliser à une somme (x1+⋯ +xk)n.

Preuve: On a (x+y+z)n = Σk=0n Σl=0nk Cnk Cnkl xkylznkl

On remarque que Cnk Cnkl=n!/k!l!(nkl)!.

On généralise en :

(x1+⋯ +xk)n = Σ{0≤ n1,…,nk|n1+⋯+nk =n}
n!
n1!… nk!
x1n1… xknk

.

Exercice 3   Pour n et m des entiers positifs, on note Sm,n le nombre de manières de répartir m objets parmi n personnes en s’assurant que chaque personne a au moins un objet.
  1. Quel est le lien entre Sm,n et les applications surjectives.
  2. Calculer S3,4, S3,1 et S3,3.
    Généraliser à
    Sm,n si n<m, Sm,1 et Sm,m.
  3. Que vaut Sm,2 si 2 ≤ m ?
  4. Exprimer en fonction de Sm,p et Cnp le nombre de manières de répartir m objets entre n personnes lorsque seules p personnes reçoivent un objet.
  5. En déduire que nm=Cn1Sm,1+⋯+CnnSm,n
  6. Que vaut Sm,p pour m≤ 4.
  7. Démontrer que Sm,n=n(Sm−1,n+Sm−1,n−1)
  8. Faire l’analogue du triangle de Pascal pour le calcul des premières valeurs de Sm,n.
Preuve:
  1. Le nombre Sm,n représente le nombre d’applications surjectives de [1,m] dans [1,n].
  2. Sm,n=0 si m<n, si 1≤m alors Sm,1=1 et Sm,m=m!
  3. Si 2 ≤ m on a Sm,2k=1m−1Cmk car il suffit de choisir les k objets que l’on donnera au premier. On a 2m=(1+1)mk=0mCmkk=1m−1Cmk+2 Donc Sm,2=2m−2.
  4. Si on donne les m objets à p personnes parmi n alors on peut d’abord choisir les p personnes parmi n (Cnp) puis ensuite répartir les m objets entre ses p personnes en servant au moins une fois chaque personne.

    On a donc en tout Cnp Sm,p solutions.

  5. Le nombre d’application d’un ensemble de m éléments dans un ensemble à n éléments est nm. On peut le décomposer suivant la taille de l’image. On a donc
    nmp=1n Cnp Sm,p
  6. S1,1=1, S2,1=1, S2,2=2, S3,1=1, S3,3=6, S4,1=1, S4,4=24 On a par ailleurs : 23=2S3,1+S3,2 donc S3,2=8−2=6
    24=2S4,1+S4,2 donc S4,2= 16−2=14
    34=3S4,1+3S4,2+S4,3 donc S4,3= 81−3−(3× 14)=14=36
  7. On regarde l’objet numéro m. Il y a n manières différentes de le distribuer. Pour le reste des objets soit on les donne aux autres (Sm−1,n−1) soit on en distribue au moins un à chacun (Sm−1,n).
  8. avec n en colonne et m en ligne :
     123
    1100
    2120
    3166
    41143624 
      


Previous Up