valeur 2 ; l’application c 3 définie par c 3 (1) = c 3 (2) = 1 et c 3 (3) = 2 ; et l’application
c 4 définie par c 4 (1) = 1 et c 4 (2) = c 4 (3) = 2. Leur nombre est bien
3+2−1
3
=
4
3
= 4.
Corollaire. Soient n et p des entiers au moins égaux à 1.
i) L’équation x 1 + · · · + x p = n, où x i ∈ N et x i 1, possède
n−1
p−1
solutions.
ii) L’équation x 1 + · · · + x p = n, où x i ∈ N, possède
p+n−1
p−1
solutions.
Démonstration. Si x 1 , . . . , x p sont des entiers, on a l’équivalence
x 1 + · · · + x p = n ⇐⇒
x 1 + · · · + x p n et x 1 + · · · + x p > n − 1
.
Le nombre de solutions de l’équation x 1 + · · · + x p = n, où x i ∈ N et x i 1, est donc
n
p
−
n−1
p
=
n−1
p−1
. De même, le nombre de solutions de l’équation x 1 + · · · + x p = n, où
x i ∈ N, est
p+n
p
−
p+n−1
p
=
p+n−1
p−1
.
Exemple. Pour organiser un jeu publicitaire dans un centre commercial, on prépare
p lots différents. En plus du lot, chaque gagnant se verra offrir au moins deux bons
d’achat. On dispose de n bons d’achat, tous du même montant. Combien y a-t-il de
façons de répartir tous les bons entre les lots ?
Numérotons les lots de 1 à p et notons x i le nombre de bons d’achat donnés avec le
lot numéro i. Les bons étant tous les mêmes, une répartition est déterminée par les
entiers x 1 , x 2 , . . . , x p . Puisque tous les bons sont utilisés, la somme des x i est égale
à n. Le nombre cherché est donc le nombre de solutions (x 1 , . . . , x p ) de l’équation
x 1 + · · · + x p = n telles que x i 2 pour tout i.
En posant y i =x i −2, l’équation x 1 +· · ·+x p =n est équivalente à y 1 +· · ·+y p =n−2p,
où les y i sont des entiers positifs ou nuls. Si n < 2p, il n’y a pas de solution. Si
n 2p, le nombre de solutions est
p+(n−2p)−1
p−1
=
n−p−1
p−1
.
Applications
Nombre de rangements de n objets dans p boîtes
Numérotons les boîtes de 1 à p et notons x i le nombre d’objets dans la i-ième
boîte. En ne tenant compte que du nombre d’objets dans chaque boîte, les solutions
sont les suites (x 1 , . . . , x p ) d’entiers positifs ou nuls tels que x 1 + · · · + x p = n. Le
nombre de possibilités est donc
p+n−1
p−1
.
Combinaisons avec répétitions
Étant donné un ensemble E à n éléments, une p-combinaison avec répétitions de ces
n éléments est un ensemble à p éléments formé de clones d’éléments de E .
Si par exemple E ={a,b,c,d,e,f }, alors a,a,c,d,d,d,f représente une 7-combinaison
avec répétitions des 6 éléments de E . De même, u, u, u, v, v est une 5-combinaison
avec répétitions des deux éléments u et v.
Une p combinaison avec répétitions des n éléments a 1 , . . . , a n est déterminée par
le nombre de fois qu’y figure chacun des élément a 1 , . . . , a n : si a 1 est répété x 1
fois, si a 2 est répété x 2 fois et a k , x k fois, alors x 1 + x 2 + · · · + x n = p. Il y a
donc autant de p combinaisons avec répétitions de n éléments que de solutions
64 – ENSEMBLES FINIS
c 4 définie par c 4 (1) = 1 et c 4 (2) = c 4 (3) = 2. Leur nombre est bien
3+2−1
3
=
4
3
= 4.
Corollaire. Soient n et p des entiers au moins égaux à 1.
i) L’équation x 1 + · · · + x p = n, où x i ∈ N et x i 1, possède
n−1
p−1
solutions.
ii) L’équation x 1 + · · · + x p = n, où x i ∈ N, possède
p+n−1
p−1
solutions.
Démonstration. Si x 1 , . . . , x p sont des entiers, on a l’équivalence
x 1 + · · · + x p = n ⇐⇒
x 1 + · · · + x p n et x 1 + · · · + x p > n − 1
.
Le nombre de solutions de l’équation x 1 + · · · + x p = n, où x i ∈ N et x i 1, est donc
n
p
−
n−1
p
=
n−1
p−1
. De même, le nombre de solutions de l’équation x 1 + · · · + x p = n, où
x i ∈ N, est
p+n
p
−
p+n−1
p
=
p+n−1
p−1
.
Exemple. Pour organiser un jeu publicitaire dans un centre commercial, on prépare
p lots différents. En plus du lot, chaque gagnant se verra offrir au moins deux bons
d’achat. On dispose de n bons d’achat, tous du même montant. Combien y a-t-il de
façons de répartir tous les bons entre les lots ?
Numérotons les lots de 1 à p et notons x i le nombre de bons d’achat donnés avec le
lot numéro i. Les bons étant tous les mêmes, une répartition est déterminée par les
entiers x 1 , x 2 , . . . , x p . Puisque tous les bons sont utilisés, la somme des x i est égale
à n. Le nombre cherché est donc le nombre de solutions (x 1 , . . . , x p ) de l’équation
x 1 + · · · + x p = n telles que x i 2 pour tout i.
En posant y i =x i −2, l’équation x 1 +· · ·+x p =n est équivalente à y 1 +· · ·+y p =n−2p,
où les y i sont des entiers positifs ou nuls. Si n < 2p, il n’y a pas de solution. Si
n 2p, le nombre de solutions est
p+(n−2p)−1
p−1
=
n−p−1
p−1
.
Applications
Nombre de rangements de n objets dans p boîtes
Numérotons les boîtes de 1 à p et notons x i le nombre d’objets dans la i-ième
boîte. En ne tenant compte que du nombre d’objets dans chaque boîte, les solutions
sont les suites (x 1 , . . . , x p ) d’entiers positifs ou nuls tels que x 1 + · · · + x p = n. Le
nombre de possibilités est donc
p+n−1
p−1
.
Combinaisons avec répétitions
Étant donné un ensemble E à n éléments, une p-combinaison avec répétitions de ces
n éléments est un ensemble à p éléments formé de clones d’éléments de E .
Si par exemple E ={a,b,c,d,e,f }, alors a,a,c,d,d,d,f représente une 7-combinaison
avec répétitions des 6 éléments de E . De même, u, u, u, v, v est une 5-combinaison
avec répétitions des deux éléments u et v.
Une p combinaison avec répétitions des n éléments a 1 , . . . , a n est déterminée par
le nombre de fois qu’y figure chacun des élément a 1 , . . . , a n : si a 1 est répété x 1
fois, si a 2 est répété x 2 fois et a k , x k fois, alors x 1 + x 2 + · · · + x n = p. Il y a
donc autant de p combinaisons avec répétitions de n éléments que de solutions
64 – ENSEMBLES FINIS