COMBINATOIRE I (Master AMD 1ere année)

January 7, 2021

Programme Combinatoire I (Master I AMD)

Chapitre I Introduction à la combinatoire, Rappels sur la théorie

des ensembles.
Chapitre ii Analyse combinatoire, principes de dénombrements
(principe d’addition, principe de multiplication). Exemples d’illustrations
(nombre d’applications entre deux ensembles …nis, nombre d’injections,
permutations, injections, combinaisons).
Chapitre iii. Principe d’inclusion-exclusion + exemples (nombre
de dérangements, nombre de surjections, etc).

Bibliographie:

1. Introduction to Combinatorial Mathematics, C. L. Liu, McGraw-

Hill Book Company.1968.
2. An Introduction to Combinatorics, Alan Slomson, CHAPMAN
AND HALL MATHEMATICS.
3. Discrete Mathematics for Computer Scientists and Mathemati-
cians, Joe l Mott et al.
Chapitre I Introduction à la combinatoire

La combinatoire est une branche des mathématiques qui s’intéresse

aux méthodes permettant de compter ou bien dénombrer dans les
ensembles …nis (combinatoire énumérative). On s’intéresse dans ce
cours à quelques techniques qui permettent de compter sur les en-
sembles …nis, et si possible leurs sous ensembles, sans énumérer tous
leurs éléments. On fait tout d’abord, un rappel sur le nombre de
permutations, arrangements et combinaisons sur un ensemble …ni
E = f1; 2; :::; ng contenant n éléments. Nous étudierons ensuite des
techniques de comptage d’ensembles …nis qui nous permettent de

1
compter le nombre d’éléments d’une union , d’une intersection , et
de diverses combinaisons d’ensemble …nis avec et sans répetition
d’éléments.
I.1 Rappels sur la théorie des ensembles

Un ensemble E est une collection d’objets dits éléments de l’ensemble

E. Si e est un élément de E on note e 2 E , sinon on note e 2= E . Pra-
tiquement, on peut dé…nir un ensemble de deux façons:
1) par extension: en décrivant tous ses éléments entre accolades
E = f0; 2; 4; 6; 8; 10g :
2) par compréhension: en donnant une propriété commune car-
actérisant tous ses éléments.
E = fx=x véri…e la propriété p g : Par exemple, l’ensemble des entiers
pairs peut etre dé…ni par :
P = fn 2 N= l’entier n est pairg.
Soit E un ensemble, on note par } (E) l’ensemble des parties de
E , on a:

A E () A 2 } (E)

Donc } (E) = fA=A Eg. Il su¢ t de prendre A = E ou bien A = ;,

pour voir qu’on a respectivement: E 2 } (E) et ; 2 } (E). En partic-
ulier, si a 2 E alors le singleton fag 2 } (E) ; on a:

a 2 E () fag E () fag 2 } (E)

Soient E; F deux ensembles. On a

E = F () E F et F E (double inclusion)

E F () (a 2 E =) a 2 F )
Exercice 1
1/ Soient A1 = x 2 N=x2 x 2=0 , B1 = f2g : Montrer que A1 =
B1 .

2
 2/ Soient A2 = fx 2 Z = x est divisible par 6g ; B2 = fx 2 Z = x est multiple de 2 et 3g.
Montrer qu’on a A2 = B2 .

I.2 Partition et recouvrement d’un ensemble

Soit E un ensemble et soit (Ai )i2I une famille de parties de E , i.e,
8i 2 I , Ai E (ou bien Ai 2 } (E)), avec I un ensemble d’indices …ni
ou in…ni. On dit que (Ai )i2I est une partition de E si d’une part,
l’union ces parties donnent E , et d’autres parts ces parties sont dis-
joints 2 à 2 i.e,
a) 8i 2 I : Ai 6= ;;
b) A
Si \ Aj = ;; pour tous i; j 2 I ,avec i 6= j .
c) Ai = E
i2I

Figure 1: partition de E

S
La famille (Ai )i2I est dite un recouvrement de E si on a Ai = E ,
i2I
dans ce cas des parties de (Ai )i2I peuvent avoir des éléments en
commun, c.à.d, il peut exister i; j 2 I , i 6= j avec Ai \ Aj 6= ;.

3
 recouvrement de E

Exercice 2 Montrer que si un ensemble E contient n éléments, alors

l’ensemble } (E) des parties de E , contient 2n parties.

Preuve: voir td

Exercice 2 Soient E = R et I = Z. On dé…nit 8i 2 I : Ai = [i; i + 1[: Par

exemple, A0 = [0; 1[, A1 = [1; 2[, A 1 = [ 1; 0[, A 2 = [ 2; 1[. On a
1/ Pour
S j : Ai \ Aj = ;,
i 6=S
2/ Ai = [i; i + 1[= R. Véri…er les résultats 1 et 2.
i2I i2Z
I.3 Produit cartésien

Soient E; F deux ensembles. Leur produit cartésien, noté E F,

est l’ensemble E F = f(x; y) = x 2 E et y 2 F g.

produit cartésien

4
En général, si E1 ; E2 ; :::; En sont n ensembles, leur produit cartésien
est l’ensemble E1 E2 ::: En = f(x1 ; x2 ; :::; xn ) =8i 2 f1; 2; :::; ng xi 2 Ei g.
Un élément (x1 ; x2 ; :::; xn ) 2 E1 E2 ::: En est dit un n-uplet. L’élément
(x; y) 2 E1 E2 est dit un couple, l’élément (x; y; z) 2 E1 E2 E3 un
triplet, l’élément (x; y; z; t) 2 E1 E2 E3 E4 un quadruplet...etc. Si
E1 = E2 = ::: = En = E , on note par E n (n copies de E ), le produit
cartésien E [Link] E (n fois).

Exemples:
1/ R2 = f(x; y) =x 2 R et y 2 Rg ; R f0g = f(x; 0) =x 2 Rg on a R f0g R2 .
De meme, f0g R = f(0; x) =x 2 Rg R2 et (R f0g) \ (f0g R) = f(0; 0)g.
Exercice 3 Soit A, B et C trois ensembles quelconques. Démontrer l’égalité
A (B \ C) = (A B) \ (A C)
Si A B = A C avec A 6= ; alors B = C.
I.4 Relation
Soient E; F deux ensembles. Une relation binaire < de E vers
F est une partie de E F , i.e, < E F . Si (x; y) 2 < on note
par x<y le fait que l’élément x est en relation avec l’élément y selon
la relation <, sinon on a (x; y) 2= < (x et y ne sont pas en relation
selon <). Comme ; E F , alors ; est dite la relation vide qui ne
contient aucun couple (aucun élément de E n’est en relation avec
aucun élément de F ). De même comme on a E F E F , alors
E F est dite la relation pleine (tout élément de E est en relation
avec tout élément de F ).
Soit < : A ! B une relation, on note par
Dom (<) = fa 2 A=9b 2 B : (a; b) 2 <g A
le domaine de la relation < et par
Rang(<) = fb 2 B=9a 2 A : (a; b) 2 <g B:

5
 l’image de la relation <

L’image d’un élément a 2 A est l’ensemble < (a) = fb 2 B : (a; b) 2 <g

des éléments de B avec lequels l’élément a est en relation. Les antéce-
dents de b 2 B est l’ensemble < 1 (b) = fa 2 B : (a; b) 2 <g des éléments
de A en relation avec b.
Inverse relation(relation inverse):

If < A B then the inverse of < is a relation from the set B to set
A which is denoted by < 1 and is de…ned by < 1 = f(b; a) = (a; b) 2 <g
or equivalently, (a; b) 2 < () (b; a) 2 < 1 .
On fait remarquer ici qu’on peut calculer la relation inverse < 1 de
toute relation binaire <. Alors que la réciproque f 1 d’une applica-
tion f de E vers F ne peut être dé…nie que si f est une bijection (au
moins une injection).

Une relation binaire sur un ensemble E est une partie de E E .

On note par IE ou bien 4E le relation identité de E , c.à.d, IE =
f(a; a) =a 2 Eg qui représente aussi la diagonale dans la table du pro-
duit cartésien E E . Certaines propriétés remarquables d’une rela-
tion binaire < sur un ensemble E sont: La relation < est dite ré‡exive
si (a; a) 2 < pour tout a 2 E ; symétrique si (b; a) 2 < lorsque (a; b) 2 <;
antisymétrique si (a; b) 2 < et (b; a) 2 < alors a = b; et transitive si

6
(a; b) 2 < et (b; c) 2 < alors (a; c) 2 <.
Exemples a). Soient E = f1; 2; 3; 4; 5g, F = f5; 6; 7; 8; 9g et la partie < =
f(a; b) =a 2 E et b = 2a + 3 2 F g = f(1; 5) ; (2; 7) ; (3; 9)g est une relation sur
E F.
b). Toute fonction f : E ! F est une relation binaire de E vers F ,
i.e , f E F avec la condition: si (a; b) 2 f et (a; c) 2 f alors b = c
(pour une fonction un élément ne peut avoir plus d’une image).
Exercice 4
a/ Soit E un ensemble. Montrer que toute relation d’équivalence
< sur E détermine une partition P = (Ai )i2I de l’ensemble E . Inverse-
ment, à toute partition P = (Ai )i2I de E on peut dé…nir une relation
d’équivalence correspondante. Donc le nombre de partitions d’un
ensemble est égal au nombre de relations d’équivalences sur cette
ensemble.
b/ b/ Soient P et P 0 2 partitions d’un ensemble E . On dit que P
est plus …ne que P 0 si:
8p 2 P; 9p0 2 P 0 tel que p p0 :
Soient R et R0 deux relations d’équivalences sur E . Montrer que
< <0 () E=< est plus …ne que E=<0 .
c/ Soit E = Z et les relations < = ( mod [4]), <0 = ( mod [2]). Montrer
que Z= mod [4] est plus …ne que Z= mod [2].
Graphe d’une relation

Soit < A B une relation. On peut représenter < d’une manière

saggitale, cartésienne ou bien matricielle.
Représentation saggitale

Représentation saggitale d’une relation

7
 Représentation cartésienne de <

Représentation cartésienne de <

Représentation Matricielle d’une relation

On peut représenter une relation < par une matrice M< qu’on dé…nie par

M
0 < (i; j) =
1 1 si (i; j) 2 < sinon on pose M< (i; j) = 0, par exemple M< =
0 1 0
@0 1 1A.
0 1 0
Une relation binaire intéressante sur un ensemble E est la re-
lation d’équivalence qui permet de quotienter l’ensemble E en une
partition. Si la relation binaire < sur l’ensemble E est une rela-
tion d’équivalence, alors la classe de l’élément a 2 E est la partie de
E dé…nie par: a< = fb 2 E=a<bg. Evidemment, on a 8a; b 2 E , soit
a< \ b< = ; soit a< = b< . Comme exemple de congruence (une con-
gruence est une relation d’équivalence compatible avec les lois de la
structure), prenons E = Z (l’ensemble des entiers) et la congruence,
notée , dé…nie sur Z par: Soit (n 2) 2 N, pour x; y 2 Z on dit
que a b [mod n] si et seulement si l’entier n divise a b. Evidem-
ment, cette relation est ré‡èxive, symétrique et transitive. La classe
a d’un élément a 2 Z est a = a + nZ. Comme pour tout entier a 2 Z,
on a par division euclidienne de l’entier a par l’entier naturel n:
a = nq + r (q :le quotient de la division et r son reste), avec 0 r < n.
Par passage_ aux classes on obtient:
a = nq + r = nq+r = 0+r = r avec 0 r < n. Et par suite, l’ensemble
quotient Z=nZ est :
Z=nZ = 0; 1; :::; n 1 avec 0 = nZ, 1 = 1 + nZ; ..., n 1 = (n 1) + nZ.
Il est clair que le cardinal de toute classe est in…ni.
Exercice 5
Soit n un entier naturel donné. On suppose n 2. On dé…nit
dans Z une relation a b [mod n] qui signi…e que (9k 2 Z) tel que
a b = kn.

8
 1/ Montrer que cette relation est une relation d’équivalence. Cette
relation est appelé congruence modulo n. On désigne par a la classe
d’équivalence de l’entier relatif a. Déterminer tous les éléments de
Z=nZ:
2/
a/ On dé…nit dans Z=nZ une addition et une multiplication par:
a+b=a+b et a:b = ab.
Montrer que (Z=nZ; +; :) est un anneau commutatif. est il intègre?
b/ Montrer que si n est premier alors Z=nZ est un corps.
3/ Donner les tables d’addition et multiplication de Z=5Z et ré-
soudre le système d’équations suivant dans Z=5Z
1x + 2y = 3
f
2x + 3y = 4
où x; y sont des éléments cherchés dans Z=5Z.
4/ Résoudre l’équation x2 4x 2 = 0, x étant un élément cherché
dans Z=5Z.
5/ Soit a 2 Z, on désigne par aZ l’ensemble aZ = fay=y 2 Zg.
5a/ Montrer que aZ + bZ = p gcd (a; b) Z.
5b/ Montrer que aZ \ bZ = ppcm (a; b) Z.
Exercice 6
Soit E un ensemble à n éléments Trouver:
1/ Le nombre de relations binaires dans E ,
2/ Le nombre de relations ré‡exives dans E ,
3/ Le nombre de relations symétriques dans E .
Preuve: Voir td
I.5 Application
Soit E; F deux ensembles. Une application f de E vers F est une
relation binaire de E vers F qui véri…e en plus la condition suivante:
si on a (a; b) 2 f et (a; c) 2 f alors b = c (c.à.d, l’élément a 2 E , ne peut
avoir plus d’une image f (a) 2 F ).
Soit f une application de E vers F .
a/ L’application f est dite injective (one to one)
si pour x1 ; x2 2 E on a f (x1 ) = f (x2 ) alors x1 = x2 ,
ceci est équivalent à dire si x1 6= x2 alors on a aussi f (x1 ) 6= f (x2 )
(deux éléments di¤érents de l’ensemble de départ ont des images
di¤érents dans l’ensemble d’arrivé). Tout cela est équivalent à dire
qu’on a: 8y 2 F on f 1 (y) 1.
b) L’application f est dite surjective(onto),
si 8y 2 F =) 9x 2 E tel que y = f (x).
Ceci est équivalent à dire qu’on a : f (E) = F , ce qui revient à dire
qu’on a aussi : 8y 2 F on a f 1 (y) 1.
c/ L’application f est dite bijective si elle est injective et surjective
ce qui est équivalent à dire: 8y 2 F on f 1 (y) = 1.
Exercice 7
Soit E; F deux ensembles …nis avec jEj = jF j. Pour montrer qu’une
application f de E vers F est une bijection, il su¢ t de montrer que

9
c’est une injection (ou bien une surjection). En d’autres mots, on
doit montrer f est injective si et seulement si f est surjective.
Preuve: Voir td.

Notion de cardinal

Soit E un ensemble. Le cardinal de l’ensemble E mesure la taille

(size) de l’ensemble E . Pour mesurer la taille d’un ensemble, on
utilise les applications (Cantor). Si l’ensemble E est …ni, alors il ex-
iste un entier naturel n 2 N tel que E soit en bijection avec l’ensemble
f1; 2; :::; ng et note Card (E) = jEj = n. Par exemple, on a j;j = 0,
jf2gj = 1, jf1; 2; :::; ngj = n. Si l’ensemble E est in…ni, on compare sa
taille avec les ensembles in…nis usuels tels que N, R,:::etc. On dit
qu’un ensemble E est in…ni dénombrable, s’il est en bijection avec
l’ensemble des entiers naturels N dans ce cas, on dé…nit jEj = @0
(aleph zéro), qui est le plus petit cardinal in…ni, evidemment @0 2= N.
Sinon, l’ensemble E est dit in…ni non dénombrable, dans ce cas on
a jEj > @0 .

Exercice 8
1/ Montrer que les ensembles Z, Q sont dénombrables.
2/ Montrer que l’intervalle(ensemble) [0; 1] R est non dénombrable.
Preuve: voir td

10
 COMBINATOIRE I CHAPITRE II

January 13, 2021

Chapitre II Principes de dénombrements

II.1/ Basics of counting

If X is a set, then jXj denote the number of elements in the set X.

Two basic counting principles:

II.1.1/The sum rule (the principle of disjunctive counting) =(the whole is the
sum of its parts).
If a set X is the union of disjoint non empty subsets S1 ; S2 ; :::; Sn , then:

jXj = jS1 j + jS2 j + ::: + jSn j

(the sets S1 ; S2 ; :::; Sn ; must have no elements in common).

Si les ensembles S1 ; S2 ; :::; Sn constituent une partition d’un ensemble X, alors
jS1 j + jS2 j + ::: + jSn j = jXj.

Exemple 1:
Combien y’a-t-il de carrés dont les cotés sont matérialisés sur la …gure ci-
dessous?

1
Soit S l’ensemble de tous les carrés. Notons S1 , S2 , S3 et S4 l’ensemble de ces
carrés ayant pour cotés respectifs 1; 2; 3 et 4 carreaux. Les sous-ensembles S1 ;
S2 ; S3 et S4 constituent une partition de S (parce que ils n’ont aucun élément
en commun et que leur réunion est égale à S, un carré ne peut avoir en même
temps un coté de longueur 1 et un coté de longueur 2 par exemple).
D’après le principe de la somme, on a:

jSj = jS1 j + jS2 j + jS3 j + jS4 j = 16 + 9 + 4 + 1 = 30.

Frequently, instead of asking for the number of elements in a set, some problems
ask for how many ways a certain event can happen. The di¤erence is largely in
semantics. For if A is an event, let X be the set of ways that A can be happen,
and count the number of elements in X.

If E1 ; :::; En are mutually exclusive events,

and E1 can happen in e1 ways, and
E2 can happen in e2 ways, and,
...............................................,
En can happen in en ways,
Then E1 or E2 or ....or En can happen in e1 + e2 + :::: + en ways.
Again we emphasize that mutually exclusive events E1 and E2 mean that E1
or E2 can happen but both cannot happen simultanousely.

The sum rule can also be formulated in terms of choices. If an object can be
selected from a reservoir in e1 ways and another object can be selected from a
separate resevoir in e2 ways, then the selection of one object from either one
resevoir or the other can be made in e1 + e2 ways.

Example 2:

How many ways can we get a sum of 4 or 8 when two distinguishable dice (say one
die is red and the other is white) are rolled?. How many ways can we get an even
sum. The space of events E is E = f(r; w) =r 2 f1; :::; 6g and w 2 f1; :::; 6gg
with jEj = 36 possible results (the integer r is for the red dice and the integer
w is for the white dice).
Il est évident que seules les résultats (1; 3) ; (2; 2) ; (3; 1) satisfont à l’evenement
: E1 = f(r; w) =r; w 2 f1; :::; 6g : r + w = 4g, on a 3 couples qui satisfont à la
condition, donc jE1 j = 3.

De la même façon, les seuls couples qui satisfont l’évenement:

2
E2 = f(r; w) =r; w 2 f1; :::; 6g : r + w = 8g sont: (2; 6) ; (3; 5) ; (4; 4); (5; 3) et
(6; 2). Donc, jE2 j = 5. Et par suite, il ya jE1 j + jE2 j = 3 + 5 = 8 possibilités
d’avoir la somme S = 4 ou bien S = 8.

The number of ways to obtain an even sum is the same as the number of
ways to obtain either the sum 2; 4; 6; 8; 10; or 12:
We have one way (1; 1) to obtain the sum = 2,
We have 3 ways to obtain the sum = 4,
We have 5 ways to obtain the sum = 6,
We have 5 ways to obtain the sum = 8;
We have 3 ways to obtain the sum = 10;
and …naly 1 way to obtain the sum = 12. Consequently, the are 1 + 3 + 5 + 5 +
3 + 1 = 18 ways to obtain an even sum.

In the above example we have two distinct dice. The two dice were distin-
guishable by color so that their outcome (1; 5) could be di¤erentiated from the
outcome (5; 1). For example, how many ways can we get a sum of 8 when two
indistinguishable dice are rolled? an even sum?.
Had the dice been distinguishable, we would obtain a sum of 8 by the outcomes
(2; 6) ; (3; 5) ; (4; 4) ; (5; 3) and (6; 2). But, since the dice are similar the out-
comes (2; 6) and (6; 2) as well, (3; 5) and (5; 3) cannot be di¤erentiated. And
thus we obtain the sum of 8 with the roll of two similar dice in only 3 ways.
Likewise, we can get an even sum in 1 + 2 + 3 + 3 + 2 + 1 = 12 ways.

Remarque 1 Le calcul des probabilités consiste d’abord à modèliser une situa-

tion sous la forme d’un ensemble …ni : l’espace des épreuves, puis à calculer les
probabilités des événements. Calculer la probabilité d’un événement A revient,
à calculer le nombre d’éléments (épreuves) que contient l’ensemble A (surtout
lorsque les ensembles sont gros) et tous ceci nous oblige à connaitre les tech-
niques élémentaires de dénombrement.

Exercice 1
1/ Combien de mots binairs peut-on former sur 8 bits sachant que le premier
bit est consacré au signe (+; ) du nombre.
2/ Soit X = f1; 2; 3; :::; 2ng. Combien y’a t il d’applications de X vers X qui
appliquent les nombres pairs sur les nombres pairs et les nombres impairs sur
les nombres impairs.
Preuve voir td

3
II.1.2/ Principe multiplicatif (principe des choix successifs) (Product
rule).

Ce principe est appelé aussi en anglais : the principle of sequentiel counting:

If S1 ; S2 ; :::; Sn are nonempty sets then the number of elements in the carte-
Qn
sian product S1 S2 ::: Sn is the product jSi j.
i=1
En langage des choix successifs: quand on fait n choix successifs, s’il y a p1
possibilités pour le premier choix, p2 choix pour le second,..., pn choix pour le
dernier, alors il y’a en tout p1 p2 ::: pn façons d’enchainer tous ces choix.
Ce principe peut etre formulé en termes de tâches: si deux tâches indépen-
dantes T1 et T2 doivent etre exécutées l’une à la suite de l’autre, si la tâche T1
peut être éxecutée de n1 façons di¤érentes et si la tâche T2 peut etre executée
de n2 façons di¤érentes, alors la séquence T1 T2 peut etre executée de n1 n2
façons di¤érentes. Nous obtenons donc: n2 + n2 + ::: + n2 (n1 fois) c.à.d, n1 n2
manières d’éxécuter la suite de tâches T1 T2

Example 3
Dans un restaurant, il y’a 4 façons de choisir une entrée, 3 façons de choisir
un plat principal, 2 façons de choisir un légume, et 4 façons de choisir un dessert.
Alors le nombre total de menus que l’on peut choisir est donc: 4 3 2 4 = 96.

Exercice 2
a/ Un code comporte deux lettres distinctes suivies d’un chi¤re non nul.
Combien peut-on former de codes distincts.
b/ Le nombre d’itineraires distincts menant d’une ville A vers une ville B
est 4 et le nombre d’itineraires distincts menant de la ville B vers la ville C
est 3. Combien y’a t il d’aller simple entre A et C. Combien y’ a t il d’aller
retour A C A n’empruntant que des chemins distincts (l’allée est di¤érent
du retour).

Exemple 4

Si l’ensemble S1 = fa1 ; a2 ; :::; an g contient n éléments et l’ensemble S2 =

fb1 ; b2 ; :::; bm g contient m éléments, alors l’ensemble S1 S2 contient n m
Sn
couples. En e¤et, on a S1 S2 = (ai S2 ), et comme jai S2 j = jS2 j donc
i=1
S
n S
n
jS1 S2 j = j(ai S2 )j = jS2 j = n jS2 j = n m.
i=1 i=1

Exercice 3 Suppose that the license plates (plaques d’immatriculations) of

4
certain state require 3 english letters followed by 4 digits.
a/ How many di¤erent plates can be manufactured if repetition of letters
and digits are allowed?
b/ How many plates are possible if only the letters can be repeated?
c/ How many are possible if only the digits can be repeated?
d/ How many are possible if no repetitions are allowed at all?
Proof
Voir td.

Using the product rule, we can show that the number of subsets of set with
n elements is 2n .
Let V = fx1 ; x2 ; :::; xn g denote the entire set. Then if T is any subset of V ,
assign to it the n binary digit sequence (y1 ; y2 ; :::; yn ) where yi = 1 if xi 2 T
and yi = 0 if xi 2= T.
In this manner, we associate a unique binary sequence to each subset T of
the set V . For instance, if T = fx1 ; x3 ; x5 g then the associated n-digit binary
sequencies is (1; 0; 1; 0; 1; 0; 0; :::; 0)n indicating x1 2 T; x3 2 T; x5 2 T but the
other n 3 elements are not in T . We have established a one -to-one correspon-
dance between the collection of subsets of V and the collection of all n-digit
binary sequences. There are 2n n-digit binary sequence, so there are 2n subsets
of V . We have the biunivoque correspondance between the n-binary digits and
the subsets of the set V = fx1 ; x2 ; :::; xn g,

(0; 0; 0; :::; 0; :::; 0)n ! ;,

(1; 0; 0; :::; 0; :::; 0)n ! fx1 g,
(0; 1; 0; :::; 0; :::; 0)n ! fx2 g,
:::::::::::::::::::::::::::::::,
(0; 0; 0; :::; 0; :::; 1)n ! fxn g,
::::::::::::::::::::::::::::::::,
(1; 1; 1; :::; 1; :::; 1)n ! V = fx1 ; x2 ; :::; xn g.

In the language of choice, we have also for each xi ; for i 2 f1; 2; :::; ng, two
possibilities: the element xi is in the subset T or not. Using the principal of
successifs choices, we have 2 2 ::: 2 = 2n di¤erent choices which correspond
to the 2n di¤erent subsets.

5
 subsets of fa; b; cg

Exemple 5 A 2-valued boolean function of n variables is de…ned by the as-

signement of a value of either 0 or 1 to each of the 2n n-digit binary numbers.
How many Boolean functions of n variables are there?

Reponse:
Since there are 2 ways to assign a value to each of the 2n binary n-tuples,
n
by the rule of product there are 2 2 ::: 2 (2n times) = 22 ways to assign
2n
all the values, and therfore 2 di¤erent Boolean functions of n variables which
is the number of functions from the set E = B B ::: B (n times, with
jEj n
B = f0; 1g) to the set B = f0; 1g and this number is jBj = 22 .

Rappelons que le choix des éléments d’un ensemble peut se faire de plusieurs
manières: l’ordre de choix à une importance ou non; on autorise ou non de
choisir plusieurs fois le même objet. Prenons l’exemple suivant qui illustre cette
situation. On considère un ensemble E ayant 3 éléments E = fa; b; cg, choisir 2
éléments de cet ensemble peut se faire de plusieurs manières: selon que l’ordre

6
de choix à une importance ou non et que l’on autorise ou non de choisir le même
élément plusieurs fois.
Le tableau ci-dessous visualise tous les cas possibles.

répétition sans répétition

aa; ab; ac ab; ac
avec ordre ba; bb; bc ba; bc
ca; cb; cc ca; cb
aa; ab; ac
sans ordre ab; ac; bc
bb; bc; cc
Lists

A list is an ordered sequence of objects. The order in which elements appear in

a list is signi…cant, for example (1; 2; 3) 6= (3; 2; 1). The number of elements in
a list is called its length.
Then () is the empty list,
(1) is of length 1;
(1; 2) is a pair,....etc.
The numbers of pairs of the set f1; 2; :::; ng is n n = n2 which are:
(1; 1), (1; 2),..., (1; n)
(2; 1), (2; 2),...,(2; n)
.............................
.............................
.............................
(n; 1), (n; 2),...., (n; n).

If we have n choices for the …rst place and m choices for the second place, then
we have n m possible lists of length 2.

Two important list of length p in which each élément of the list is selected from
among n possibilities.

II.2/ Arrangement avec répétition

Dé…nition 1
Etant donné un ensemble …ni de n objets, on appelle arrangement avec
répétition de ces n objets p à p, tout groupement ordonné de p objets choisis
parmi les n objets avec répétition. Le nombre d’arrangements de n objets p à p
est égal à np

7
 - Pour construire un tel arrangement, on choisit un élément de l’ensemble
que l’on place en première position, il y’a n choix possibles. Puis on choisit
un élément de l’ensemble que l’on place en deuxième position, il y’a n choix
possibles, et ainsi de suite jusqu’au p ième élément et il y’a n choix possibles.
Ainsi il y’ a np choix possibles qui représente le nombre d’arrangements de n
objets p à p avec répétition.

Ce nombre représente aussi le nombre des applications d’un ensemble E

vers un ensemble F avec jEj = p et jF j = n. Rappelons qu’une application
f de l’ensemble E = fa1 ; a2 ; :::; ap g vers l’ensemble F = fb1 ; b2 ; :::; bn g peut
a1 a2 : : : ap
être représenté par f = avec la séquence
f (a1 ) f (a2 ) : : : f (ap )
p p
(f (a1 ) ; f (a2 ) ; :::; f (an )) 2 F c.à.d, un p-uplet de F .

Exemples 6
a/ Si E et F sont des ensembles …nis et si F E désigne l’ensemble des applications
de E dans F , si jEj = p et jF j = n alors F E = np .
b/ Le nombre de tirages di¤érents de p boules dans une urne contenant n boules
numérotées de 1 à n est égal à np lorsque les tirages sont avec remise (on dit
aussi que les tirages sont non exhaustifs).
c/ Le nombre de façons de placer p objets distincts dans n cases où chaque case
pouvant éventuellement contenir plusieurs objets est np .

Théorème 1
Soit E un ensemble …ni de cardinal n. Le cardinal de l’ensemble E p des
p-listes de E est np .
Exemple 7

I.4/ Arrangement sans répétition

Exercice Démontrer par récurrence sur l’ensemble X que le nombre de

jXj
fonctions de X vers l’ensemble Y est jY j .
Preuve: Voir td.

Exercice 4 Soit A et B deux ensembles et f une application de A vers B. On

suppose que B est …ni de cardinal n et que pour tout y dans B, le cardinal de
l’image réciproque de y par f , f 1 (fyg), est égal à un entier non nul p.
1/ Montrer que f est surjective.
2/ Soit R la relation d’équivalence associée à f . Montrer que A=R et B sont
équipotents.
3/ En déduire le cardinal de A.

8
 Figure 1: deux tirages possibles avec remise de 3 boules

Exercice 5 Soit A et B deux ensembles de cardinaux respectifs n et p et

désignons par z (A; B) l’ensemble des applications de A vers B:
1/ Déterminer le nombre d’applications de A vers B pour n = 1 et n = 2.
2/ Soit a 2 A et A1 = A fag. Montrer que z (A; B) et z (A1 ; B)
z (fag ; B) sont équipotents.
3/ En déduire, par un raisonnement par récurrence, le nombre d’applications
de A dans B.

II.3 Arrangement sans répétition

Dé…nition 2 Etant donné un ensemble …ni de n objets, on appelle arrangement

sans répétition de ces n objets p à p tout groupement ordonné de p objets choisis
parmi n objets sans répétition. Le nombre d’arrangements de n objets p à p est
égal à n (n 1) ::: (n p + 1) si n p et nul sinon et sera noté Apn .
En général on dit arrangement pour un arrangement sans répétition. Pour
construire un arrangement sans répétition, on choisit un élément de l’ensemble
que l’on place en première position, il y’a n choix possibles. Puis on choisit un
élément de l’ensemble di¤érent du premier choix que l’on place en deuxième po-
sition, il y’a n 1 choix possibles, ce nombre de choix se multiplient au nombre
de choix précédents, puis on choisit un élément de l’ensemble di¤érent des deux
premiers que l’on place en troisième position et ainsi de suite jusqu’au p élément,
qui lui reste n (p 1) = n p + 1 éléments à choisir (on a déja choisi les p 1
éléments donc, le p-ième élément lui reste n (p 1) éléments pour son choix,
et par suite, le nombre d’arrangements possible est n (n 1) ::: (n p + 1).

9
Exemples 8
a/ Si E et F sont des ensembles …nis et si I (E; F ) désigne l’ensemble des
applications injectives de E dans F avec jEj = p; jF j = n et p n alors
jI (E; F )j = n (n 1) ::: (n p + 1).
b/ Si jEj = jF j = n alors sym (E) = Sn désigne l’ensemble des permutations
des éléments de E.
c/ Le nombre de tirage di¤érents de p boules dans une urne contenant n boules
numérotées de 1 à n est égal à n (n 1) ::: (n p + 1), lorsque les tirages sont
sans remise après chaque tirage (on dit que les tirages sont exhaustifs)
d/ Le nombre de façons de placer p objet distincts dans n cases chaque case
pouvant contenir au plus 1 objet est n (n 1) ::: (n p + 1).
In this case, we have n choices for the …rst element, and for each of these n
choices, it remains n 1 choices for the second element, and n 2 choices for
the third element, ..., and then n (k 1) choices for the k-th element. Then,
the total of possible choices in this case is :
n (n 1) (n 2) ::: (n (k 1)), which represent (le nombre tirage
sans remise de k boules d’un réservoir contenant n di¤érentes boules (n dif-
férents couleurs).

Nous allons appliquer le principe des choix successifs pour calculer le nombre
d’applications d’un ensemble …ni E vers un ensemble …ni F . On note par F E
l’ensemble des applications de E vers F .

Théorème 1
Soient E et F deux ensembles …nis, alors F E est …ni et on a: F E =
jEj
jF j = mn .
Cet ensemble représente aussi les suites avec répetition de longueur n = jEj,
qu’on peut former à l’aide des éléments de l’ensemble …ni F de cardinal jF j = m.
Preuve:
Notons l’ensemble E par E = fa1 ; a2 ; :::; an g. Une application f : E ! F ,
a1 a2 : : : an
qu’on peut repésenter par f = est complète-
f (a1 ) f (a2 ) : : : f (an )
ment determinée par le choix des valeurs attribuées à f (a1 ) ; f (a2 ) ; :::; f (an ).
Comme il y’a jF j possibilités pour chacune des f (ai ) ; pour i 2 f1; :::; ng, alors
par le principe multiplicatif : le nombre de façons de dé…nir f est égal au produit
jEj
des n facteurs chacun égal jF j, donc il y’a jF j jF j ::: jF j (n fois)= jF j
façons de dé…nir une application de E vers F .
Exercice 6 Montrer que le nombre des fonctions booléennes de n variables est
n
22 .

Exemples 9

10
 1/ soit E = fag et F = f0; 1; 2g. Il y’a trois applications de E vers F :
f : a 7 ! 0; g : a 7 ! 1; h : a 7 ! 2.

2) Soit E = fa; bg et F = f0; 1; 2g. Pour dé…nir une application de E vers

F , nous pouvons partir des trois applications précedentes, choisir à chaque fois
une image di¤érente pour l’élément b. On obtient:

a b a b a b
f1 = f2 = ; f3 = ,
0 0 1 0 2 0
a b a b a b
f4 = f5 = ; f6 = ,
0 1 1 1 2 1
a b a b a b
f7 = f8 = ; f9 = :
0 2 1 2 2 2

jEj
Le nombre de ces applications est F E = jF j = 32 = 9. Comme il
y’a trois éléments dans F; il y’a trois choix possibles pour l’image de b, donc
3 3 = 32 applications de E vers F .
Si l’ensemble E avait un troisième élément c, chacune des neufs applications
précédentes permettrait de dé…nir trois applications de fa; b; cg dans F (puisqu’il
y’a trois possibilités de choix pour l’image de l’élément c. Il y aurait donc
9 3 = 33 applications de E vers F . On peut représenter l’arbre des applications
de E = fa; b; cg vers F = f1; 2g par:

2/ Injections d’un ensemble vers un autre (arrangements sans répéti-

tion)
Rappelons qu’une application f de E dans F est une injection, lorsque deux
éléments quelconques distincts dans E ont des images distinctes dans F . Soient
E, F 2ensembles avec jEj = p et jF j = n. On note par Apn le nombre d’injections

d’un ensemble E à p éléments vers un ensemble F à n éléments.

1/ Supposons que p > n.
Dans ce cas on a jEj = p > jF j = n, donc E a plus d’éléments que F , les images
de tous les éléments de E ne peuvent être des éléments distincts de F , et par
suite il n’y’a aucune application de E vers F qui soit injective=) Apn = 0.

Exemple 10 Il est impossible de former un mot de longueur 4 avec seulement

3 lettres sans qu’on répète au moins une lettre.
2/ On suppose p = 1.
Dans ce cas, E possède un seule élément, et par suite toute application de E
vers F est une injection

=) A1n = n1 = n.

11
Figure 2: applications de l’ensemble { a,b,c} vers l’ensemble {1,2}

Figure 3: applications de E={a} vers F={1,2,...,n}

12
 3/ Supposons que 1 < p n. Nous allons appliquer encore une fois le
principe des choix successifs pour compter le nombre des applications injectives
d’un ensemble E vers un ensemble F .
Pour dé…nir une application injective f de E dans F on choisit d’abord f (a1 )
arbitrairement, ce qui fait on a n possibilités, puis f (a2 ) mais cette fois il n’ya
plus que (n 1) possibilités car f (a2 ) doit être di¤érent de f (a1 ). On choisit
ensuite f (a3 ), il n’ya que (n 2) possibilités (pour éviter les valeurs prises
par f (a1 ) et f (a2 ) : On continue ainsi, et lorsqu’on arrive au moment de choisir
f (ap ) compte tenu des (p 1) interdictions dues aux choix de (f (a1 ) ; f (a2 ) ; :::; f (ap 1 ))
il ne reste plus que (n (p 1)) possibilités, et par suite le nombre total des
injections de E vers F , en utilisant le principe multiplicatif, est :
Apn = n (n 1) (n 2) ::: (n p + 1) = (nn!p)! avec par dé…nition n! =
n (n 1) (n 2) ::: 2 1 (lire n-factoriel) avec 0! = 1.

Un p-arrangement sans répétition = une p-liste sans répétition= un mot de

longueur p sans répétition de lettres.
Un arrangement de p éléments de F est parfois appelé une suite de p élé-
ments distincts de F (on dit aussi arrangement de n éléments p à p). Deux
arrangements di¤èrent si leurs images ne contiennent pas les mêmes éléments
ou si les éléments ne sont pas pris dans le même ordre.

Exemple 11
Dix chevaux participent au départ d’une course. Combien y’a t’il de tier-
cés di¤érents dans l’ordre (combien de choix de trois gagnants dont l’ordre
est signi…cant). Soit F = fa; b; c; d; e; f; g; h; i; jg l’ensemble des chevaux. Il
s’agit de calculer le nombre d’arrangements de trois éléments de F . Et on
A310 = 10 9 8 = 720: Remarquons que (a; b; c) et (b; a; c) sont des tiercés
di¤érents puisque l’on tient compte de l’ordre.

Exercice 7
On appelle arrangement d’ordre p de d’un ensemble A, toute suite ordonnée de
p éléments distincts choisis parmi les éléments de A.
1/Montrer que l’ensemble des arrangements d’ordre p de A est équipotent à

l’ensemble des applications injectives de f1; :::; pg dans A.

2/ En déduire le nombre d’arrangements d’ordre p de A, noté A (n; p).
3/ En déduire le nombre de permutations de A (arrangements d’ordre n de A)
noté p (n).
Preuve Voir td.

II.4/ Bijection d’un ensemble sur lui même (permutation d’un ensem-
ble E avec jEj = n).

13
 Lorsque jEj = jF j = n, toute injection de E vers F est une bijection de E
vers F .
Il y’a donc Ann = n! bijections E sur lui même.
Notation
Rappelons qu’on appelle factorielle de l’entier naturel n et le note n! l’entier
n! = n (n 1) (n 2) ::: 2 1 avec 0! = 1 (le nombre de bijection d’un
ensemble de 0 éléments vers lui même est l’application vide)

Permutation et le groupe Sn .
On appelle permutation de n éléments toute bijection de l’ensemble de ces n
éléments vers lui même. On note une permutation 2 Sn par:

1 2 : : n
= .
(1) (2) : : (n)

On note par Sn l’ensemble des permutations d’un ensemble de n éléments.

L’ensemble Sn muni par la composition des applications (Sn ; ) est un groupe
dit groupe de permutations de n lettres.
EXERCICE
Démontrer que (Sn ; ) est groupe.

Exercice 8 In how many ways can 7 women and 3 men be arranged in row if
the 3 men must always stand next to each other
Proof: see the td

Exercice
How many 6-digit numbers without repetition of digits are there such that
the digits are all non zero and 1 and 2 do not appear consecutively in either
order.

II.4.2/ Cyclic groups

cyclic notation
1 2 3
The permutation = has the e¤ect of moving the elements
3 1 2
around in a cycle. This is called a cycle of length 3 and we write this as (132) and
this signify (1 ! 3 ! 2 ! 1). Evidently, this permutation can be also written
(321) = (213) = (132).
In general, if a1 ; a2 ; :::; ar are distinct elements of f1; 2; 3; :::; ng the permu-
tation 2 Sn de…ned by (a1 ) = a2 ; (a2 ) = a3 ; :::; (ar 1 ) = ar ; (ar ) = a1
and (x) = x if x 2 = fa1 ; a2 ; :::; ar g, is called a cycle of length r or an r-cycle.
We denote it by (a1 a2 :::ar ) = (a1 ! a2 ! ::: ! ar ! a1 ).

14
 Figure 4: orbites de la permutation

Proposition 1
A r-cycle in Sn has order r.
Proof:
If = (a1 a2 :::ar ) is an r-cycle in Sn , then (a1 ) = a2 ; 2 (a1 ) = a3 ; 3 (a1 ) =
a4 ; :::; r 1 (a1 ) = ar and r (a1 ) = a1 .
Similarly, r (ai ) = ai for i = 1; 2; :::; r. Since r …xes all the other elements,
it is the identity permutation, but none of the permutations ; 2 ; :::; r 1 equal
the identity, because they move the element a1 : Hence, the order of is r:

Example 12
Write down = (1342) ; = (13) and = (12) (34) as permutation in S4 .
Calculate .
1 2 3 4 1 2 3 4
Solution: We have (1342) = ; (13) = ,
3 1 4 2 3 2 1 4
1 2 3 4
then = (12) (34) = :::etc.
2 1 4 3

Permutations that are not cycles can be split up into two or more cycles as
follows:
If 2 Sn and a 2 f1; 2; 3; :::; ng the orbit of a under consist of distinct
elements a; (a), 2 (a), 3 (a),..., We can split a permutation up into its
di¤erent orbits, and each orbit will give rise to a cycle. Consider the per-
1 2 3 4 5 6 7 8
mutation = 2 S8 . We have: (1) = 3,
3 2 8 1 5 7 6 4
2 3 4
(1) = ( (1)) = (3) = 8, (1) = 4, (1) = 1. Then the orbite of
1 is orb (1) = f1; 3; 8; 4g. Evidently, orb (1) = orb (3) = orb (8) = orb (4).
Since leaves 2 and 5 …xed then orb (2) = f2g, orb (5) = f5g : And …nally,
orb (6) = f6; 7g is a 2-cycle.

Disjoint cycle decomposition of is:

15
We have = (1384) (2) (5) (67) = (67) (2) (5) (1384) = (67) (1384).
Proposition
Every permutation can be written as a product of disjoint cycles

= 1 2 ::: k

where i are the cycles obtained as described in the precedent example.

Corollaire
The order of a permutation is the least common multiple of lengths of its
disjoint cycles.
Proof
If = 1 2 ::: k is the decomposition in disjoint cycles =) 8m, m =
m m
1 2 ::: k Because the cycles are disjoint, and this is the identity i¤ m
m
i
is the identity for each k i 1, the least such integer is the least common
multiple of the orders of the cycles.
Example 13

The cycle decomposition of is

1 2 3 4 5 6 7 8
= = (13825) (476).
3 5 8 7 1 4 6 2
2 3 4
Then the order of is the lcm (5; 3) = 15. we can calculate ; ; ; :::; until
we obtain the identity.

La formule suivante donne une éstimation de n! pour n assez large.

Théorème ( formule de Stirling)
lorsque n tend vers l’in…ni le rapport nn e n!
p
n 2 n
! 1,
ce qui donne
p
n! nn e n 2 n

II .5/ Combinaisons sans répétition (l’ordre est sans importance):

Dé…nition 3 Soit E un ensemble …ni de cardinal n et p un entier naturel tel
que 0 p n. Une p-combinaison (ou bien combinaison de p éléments) de E
est une partie de E ayant p éléments. On dit aussi combinaison de n objets p à
p.
Exemple 14
Soit E = fa; b; cg et p = 2 les combinaisons de deux éléments de E sont les
parties contenant deux éléments de E qui sont: fa; bg, fa; cg et fb; cg.
Il est important de noter que:
- Dans une partie tous les éléments sont distincts.
- Deux parties qui contiennent les mêmes éléments sont égales, (l’ordre dans
lequel on écrit les éléments n’a pas d’importance).
Théorème 2

16
 Soit E un ensemble …ni de cardinal n et p un entier naturel tel que 0 p
n.
Ap
Le nombre de combinaisons de p éléments de E est Cnp = p!n = p!(nn! p)! . Ce
n
nombre est aussi noté (notation englo-saxonne).
p
Preuve
A partir d’une combinaison sans répétition de n objets p à p, on obtient un
arrangement de n objets p à p en ordannant ces p objets. Comme il y’a p!
façons d’ordonner p objets, on peut dire qu’à une combinaison correspond p!
arrangements et ainsi on obtient la relation: Apn = p!Cnp .

Exemples 15
a/ Le nombre de façons de placer p objets indiscernables dans n cases chaque
case pouvant contenir au plus 1 objet est Cnp .
b/ Le nombre d’applications d’un ensemble ayant n éléments dans f0; 1g qui
envoient exactement p éléments dans 0 et les autres dans 1 est égal à Cnp .
c/ Le nombre d’applications strictements croissantes de 4p = f1; 2; :::; pg
dans 4n = f1; 2; :::; ng est égal à Cnp .

Relations entre les nombres ou les coe¢ cients Cnp

Il existe de nombreuses relations entre les coe¢ cients Cnp . On citera les plus
importantes:
Propriétés
1/ Cn0 = Cnn = 1,
2/ Cnp = Cnp 11 + Cnp 1 , relation de Pascal.
3/ Cnp = Cnn p ; relation de symétrie.
4/ Cnp = np Cnp 1 .
Preuve:
Toutes ces propriétés peuvent se démontrer par calcul algèbrique en utilisant
seulement le résultat Cnp = (nn!p)! , Ou bien d’une manière combinatoire:
Une preuve combinatoire est une démonstration qui tend à établir une identité
entre deux expressions a priori di¤érentes. La preuve s’appuie généralement sur
deux techniques :
Une preuve par double dénombrement, qui consiste à compter un même ensem-
ble d’objets de deux manières di¤érentes ;
Une preuve par bijection, qui consiste à établir une bijection entre deux ensem-
bles dont on souhaite prouver l’équipotence (bijection). On donne les preuves
combinatoire de ces quatres propriétés:

Pour la propriété 1
On a Cn0 = Cnn = 1. En e¤et, il y’a une seule partie de 0 éléments dans
tout ensemble de n éléments, c’est la partie ;. De même, dans un ensemble de

17
 Figure 5: parties avec et sans l’élément a1

n éléments il y’a 1 une seule partie contenant n éléments, c’est l’ensemble en

entier.
Pour la propriété 2: cette relation est connue sous le nom la relation de
Pascal.
Considérons un ensemble E de n éléments avec E = fa1 ; a2 ; :::; an g. Distin-
guons l’élément a1 , par exemple, de cet ensemble. Pour former une partie de
p éléments de E, cette partie peut contenir l’élément a1 ou bien ne pas con-
tenir l’élément a1 . Le nombre de parties de E ne contenant pas l’élément a1
est égal au nombres de parties de p éléments qu’on peut former de l’ensemble
E1 = E fa1 g, et ce nombre est bien Cnp 1 . De même, le nombre de parties de
p éléments qui contiennent chacune l’élément a1 sont au nombre de Cnp 11 , qui
sont toutes di¤érentes des parties précedentes par au moins l’élément a1 ; et par
suite ce nombre véri…e bien Cnp = Cnp 11 + Cnp 1 .

3/ La propriété 3 est connue sous le nom de la propriété de symétrie des com-

binaisons: dans un ensemble E de n éléments, à toute partie de p éléments de
E correspond une partie unique de n p éléments E et vice versa, et par suite
on a la propriété ( voir schema)
n n
conséquences: = =1
0 n
n n
= = n.
1 n 1

Formule du binôme de Newton

Soit (A; +; ) un anneau commutatif unitaire d’élément unité 1A , pour tout
n P
n
couple (a; b) de A2 et tout entier naturel n on a: (a + b) = Cnp ap bn p où
p=0
a0 = b0 = 1.
Preuve

18
Figure 6: Correspondance 1-1 entre partie de p éléments et de (n-p) éléments

1/ par récurrence sur n (voir td).

n
2/ preuve combinatoire: En developpant le produit (a + b) = (a + b) (a + b)
n
::: (a + b) nous obtenons 2 termes (on a n termes (a + b) et pour chaque terme
on le choix de choisir soit a soit b). On peut voir chaque terme comme une suite
de longueur n de l’ensemble fa; bg , par exemple le choix de a à chaque fois nous
donne an = a a ::: a; et c’est la seule façon d’obtenir an . Pour obtenir le
terme ap bn p , on doit choisir a (p fois) et b (n p fois). Mais ce choix peut se
faire en Cnp façons di¤érentes, d’où la formule pour p allant 0 à n.

Exercice 9 Soit A un ensemble à n éléments. On appelle combinaison d’ordre p

de A, toute suite non ordonnée de p éléments distincts choisis parmi les éléments
de A.
1/ Quelle est le nombre d’arrangements qu’on peut associer à une combinai-
son d’ordre p de A.
2/ En déduire le nombre de combinaisons d’ordre p de A, noté C (n; p).

Exercice 10 Soit a un élément d’un ensemble E. Déterminer le nombre de

sous ensembles de E de cardinal p :
- qui contiennent l’élément a.
- qui ne contiennent pas a:
En déduire: C (n; p) = C (n 1; p 1) + C (n 1; p).

Exercice 12 Soit un ensemble à n éléments, et A E un sous ensemble de p

éléments de E: Quel est le nombre de parties de E qui contiennent un et seul
élément de A.

Exercice 13

19
 Figure 7: Chemins du point (0,0) au point (p,q)

n P
n P
n
k P
n
En utilisant la fonction x 7 ! (1 + x) ; calculer Cnk ; ( 1) Cnk ; kCnk ;
k=0 k=0 k=0
P
n
1 k
1+k Cn .
k=0
En utilisant la formule du binôme démontrer que:
1/ 2n + 1 est divisible par 3 () n est impair.
Exercice 14
En part du point de coordonnées (0; 0) pour rejoindre le point de coordonnées
(p; q) (p et q entiers naturels donnés) en se déplaçant à chaque étape d’une unité
vers la droite ou vers le haut. Combien y’a t’il de chemins possibles? combien
de chemins passent par un point particulier c. Voir le schéma ci après. ,

Triangle de Pascal
La relation de Pascal permet de calculer les coe¢ cients binomiaux de la façon
suivante:
Binôme triangle de
pascal(Coe¢ cients)
0
n = 0, (a + b) = 1 1
1
n = 1, (a + b) = a + b 1 1
2 2 2
n = 2, (a + b) = 1a + 2ab + 1b 1 2 1
#
3
n = 3, (a + b) = 1a3 + 3a2 b + 3ab2 + b3 1 3 3 1
4
n = 4, (a + b) = 1a4 + 4a3 b + 6a2 b2 + 4ab3 + b4 1 4 6 4 1

n = [Link]
n = [Link] 1
n = [Link] 2 1
n = [Link] 3 3 1
n = [Link] 4 6 4 1
n = [Link] 5 10 10 5 1
: etc

La formule du binôme possède plusieurs applications

1/ En prenant a = b = 1 dans la formule du binôme de newton on obtient:

20
 2n = Cn0 + Cnp + :::: + Cnp + ::: + Cnn , qui représente le nombre de parties dans
un ensemble de n éléments.
Pn
k n
2/ En prenant a = 1; b = 1 on obtient ( 1) = 0.
k=0 k
P n P n
3/ On a = = 2n 1 .
k n;k pair k k n;k im pair k
Pn n n 1
4/ k = n2 .
k=0 k
Preuve:
n
1. On développe (1 + 1) avec le binôme de Newton.
n
2. On développe (1 1) avec le binôme de Newton.
P n
3. Par 1 et 2, on a le système, en notant P = et I =
k n;k pair k
P n
,
k n;k im pair k
P + I = 2n 2P = 2n
() =) P = 2n 1 m = I:
P I=0 P =I
4. Cette somme représente la somme des cardinaux de toutes les parties de
E. Pour XP 2 } (E) on X et X cP sont disjoints
P avec jX [ X
c
Pj = jXj + jX c j = n,
c c
d’où jXj + jX j = n or jXj = jX j et par suite
X2}(E) X2}(E) X2}(E) X2}(E)
P P Pn n n
P
n n
2 jXj = n 1 () k = 2 = n2n 1
.
X2}(E) X2}(E) k=0 k k=0 k

I.7/ Combinaisons avec répétition

Dé…nition 4 Soit E = fe1 ; e2 ; :::; en g un ensmble de n éléments. Soit p un entier
naturel. On appelle combinaison avec répétition d’ordre p de E toute collection
[ei1 ; ei2 ; :::; eip ] de p éléments (distincts ou non) de E. On peut représenter cette
combinaison par:[e1; :::; e1 ; e2 ; :::; e2 ; :::; en ; :::; en ] avec e1 est répété p1 fois, e2 est
répété p2 ; :::;et en est répété pn fois avec p1 + p2 + ::: + pn = p.
Proposition 2
p
Le nombre de combinaison avec répétition d’ordre p de E est Knp = Cn+p 1 =
n 1
Cn+p 1 :
PreuveUne combinaison avec répétition d’ordre p est caractérisée par le nombre

P
n
pk de fois où l’élément ek est répété, avec pk = p.
k=1
Tout ceci revient donc à resoudre l’équation suivante en nombres entiers
positifs ou nuls x1 + x2 + ::: + xn = p (*) où x1 représente le nombre de fois
de répétition de e1 , et x2 représente le nombre de répétition de e2 ,..., et xn
représente le nombre de fois de répétition de en . Tout ceci revient donc a
imaginé la distribution de p identical balls sur n distincts boxes où chaque boxe
peut contenir plusieurs balls. Pour simpli…er la solution au problème on imagine
que les (n 1) signes plus + dans l’équation "*" sont des cloisons et on veut
distribuer ces p identical balls entre ces (n 1) cloisons ou bien résevoirs. La

21
 p n 1
solution est tout simplement C(n 1)+p = Cn+p 1 , ( On imagine que les solutions
sont les di¤érentes façons d’ecrire un mot de longueur (n 1)+p avec seulement
deux symbols f ; Ig et ce mot doit contenir (n 1) symboles "I" et p symboles
" ". Le nombre de solutions est égal au nombre de mots di¤érents qu’on peut
p
écrire avec ces deux symboles, selon la condition préscrite, qui est bien C(n 1)+p
Exemple 16
Given 12 identical coins and wish to distribute them into four distinct boxes.
In how many ways can we do this?.
One of the distribution can be like this: I I I ! (2; 4; 3; 3),
or like this III ! (12; 0; 0; 0). There are 12 coins and three
"I" then 15 symbols, we choose three places from 15 places for the dividers.
3
This can be done in C15 = 455 ways.

Théorème 3
The number of nonnegative integer solutions to the equation x1 + x2 + ::: +
n+k 1 n+k 1
xk = n is = .
k 1 n
Proof
The solution (x1 ; x2 ; :::; xk ) corresponds to a partition of a set of n identical
objects into k distinct classes with xi is the number of elements in the i-th
classe: two partitions will di¤erent i¤ the string (x1 ; x2 ; :::; xk ) are di¤erent.
Sample problem
Find the number of non negative integer solutions to x1 + x2 + x3 + x4 = 11.
11 + 4 1 14
Solution We have k = 4 and n = 11 so there are = =
4 1 3
364 solutions.

Sample problem
Find the number of integer solutions to x1 + x2 + x3 + x4 = 20, where x1 2,
x1 2, x3 3, and x4 5.
Solution
De…ne y1 = x1 2, y2 = x2 + 2, y3 = x3 3, y4 = x4 5 we have then the
equivalent equation y1 + y2 + y3 + y4 = 20 2 + 2 3 5 = 12 with yi 0 for
12 + 4 1 15
i 2 f1; 2; 3; 4g. There are = = 455 solutions.
4 1 3

Essayons de démontrer le résultat suivant qui montre la correspondance entre

choisir une partie de p éléments d’un ensemble E de cardinal n et le choix d’une
suite strictement croissante de cette ensemble. De même le choix d’une partie
de p éléments avec répétition correspond au choix d’une suite croissante au sens
large de cette ensemble.
Exercice Soient n; p 2 N et E = f1; :::; ng.

22
 1/ Combien y’a -t-il de suite strictement croissantes (x1 < x2 < ::: < xp )
d’éléments de E.
2/ Combien y’a-t-il de suites croissantes au sens large (x1 x2 ::: xp )
d’éléments de E.
Solution 1/ Une suite (x1 < x2 < ::: < xp ) strictement croissante est en-
tièrement déterminée par le choix de p éléments distincts dans E, qu’il su¢ t
alors d’ordonner, il y’a donc autant de suites strictement croissantes que de
n
parties à p éléments dans un ensemble à n éléments, soit donc .
p
2/ Associons à une suite (x1 ; x2 ; :::; xp ) d’éléments de E; croissante au sens
large, la suite (y1 ; y2 ; :::; yp ) strictement croissante dé…nie par yk = xk +(k 1).
On a y1 = x1 ; y2 = x2 + 1; y3 = x3 + 2; :::; yp = xp + (p 1) :
La suite (y1 ; y2 ; :::; yp ) ainsi obtenue est un élément de l’ensemble E 0 =
f1; :::; n + p 1g. Et donc le nombre de suites (x1 ; x2 ; :::; xp ) croissantes au
n+p 1
sens large est égal à .
p

I.8/ Permutation avec répétition

Dé…nition 5
Soit un entier naturel n 1. Soit E = [e1; :::; e1 ; e2 ; :::; e2 ; :::; en ; :::; en ] une
collection de p éléments dont pk fois l’élément ek avec p = p1 + p2 + ::: + pn . On
appelle permutation avec répétition de E, toute suite ordonnée des p éléments
de E.
Proposition 3
Le nombre de permutations avec répétition de E est p1 !p2p!!:::pn ! .
Preuve
Pour construire une permutation de E, on choisit successivement
- p1 positions pour e1 parmi les positions possibles, on a Cpp1 choix possibles;
- p2 positions pour e2 parmi les p p1 positions restantes, soit Cpp2 p1 ;
- p3 positions pour e3 parmi les p p1 p2 positions restantes, soit Cpp3 p1 p2 ;
-...................................................................
- pn positions pour en parmi les p p1 p2 ::: pn 1 = pn positions
restantes, soit Cppnn .
Le principe de multiplication donne donc le nombre de permutations avec
(p p1 )!
répétition de E est Cpp1 Cpp2 p1 Cpp3 p1 p2 ::: Cppnn = p1 !(pp! p1 )! p2 !(p p1 p2 )!
(p p1 p2 )! pn ! p!
p3 !(p p1 p2 p3 )! ::: pn !0! , d’où le résultat p1 !p2 !:::pn ! .

Example 17
How many distinct words, including nonsense ones, can be produced using all
the lettres of the word MISSISSIPPI?
In …rst, imagine the lettres are distinguished, like MI1 S1 S2 I2 S3 S4 I3 P1 P2 I4 we
have 11 distinct letters, and these can be permuted in 11! distinct ways. But
the words MI1 S2 S1 I2 S4 S3 I3 P2 P1 I4 , MI1 S4 S3 I2 S1 S2 I3 P1 P2 I4 , for example, are
11!
the same as the word MISSISSIPPI, the answer to the problem, is 4!4!2!1! .

23
The same argument leads to the following general result: if we have objects
of m kinds, ki indistinguishable objects of i-th kind, where k1 + k2 + ::: +
km = n, then the number of distinct arrangements of these onjects in a row is
n
given by k1 !k2n!
!:::km ! this expression is usually written and is
k1 ; k2 ; :::; km
called a multinomial coe¢ cient. In particular, for m = 2; we have the binomial
n n
coe¢ cient: = .
k; n k k
Theorem 4 (Multinomial theorem). For arbitrarly real numbers x1 ; x2 ; :::; xm
and any natural number n 1; the following equality holds:
n P n
(x1 + x2 + ::: + xm ) = xk11 xk22 :::xkmm .
k1 +:::+km =n k 1 2 :::; km
; k ;
k1 ;:::;km 0
10 10
Example 18 The coe¢ cient of x2 y 3 z 5 in (x + y + z) is = 2520.
2; 3; 5
Exercice 15 Prove the multinomial theorem by induction on n.

The pigeonhole principale (le principe des cages à pigeons)

Suppose m pigeons ‡y into n pigeonholes to roost, where m > n then obviously
at least two pigeons must roost in the same pigeonhole. This property, is called
the pigeonhole principal (principe des cages à pigeons). This principale can
stated in terms of functions.
Theorem (the pigeonhole principale)
Let f : X ! Y where X and Y are …nite sets with jXj = m, jY j = n, and
m > n. Then there exist at least two distinct elements x1 and x2 such that
f (x1 ) = f (x2 ).
Proof
let X = fx1 ; x2 ; :::; xm g. Suppose f is injective, then ff (x1 ) ; f (x2 ) ; ::::; f (xm )g
are all distinct in the set Y .Then jY j = n m. But this contradict the fact
that m > n. Therefore f must non injective and there is at least two distinct
elements x1 and x2 such that f (x1 ) = f (x2 ).
The pigeonhole principale is also called the Dirichlet Box principale
Examples Si le nombre des étudiants 1ere année master discrète dépasse 12
alors certainement, il y’a au moins deux étudiants qui sont nés dans le même
mois.

Exemple 19 Supposant qu’on choisit 367 étudiants de l’université de M’sila,

alors il existe au moins deux étudiants qui ont le même jour de naissance. En
e¤et, comme il y’a 366 jours dans l’année et on a 367 étudiants, il su¢ t de
prendre 366 les cages et 367 les pigeons. Et donc, nécessairement il y’a au
moins deux étudiants qui ont le même jour de naissance. Montrons que ce
principe peut etre utilisé pour démontrer des choses assez profonde.

24
 It is well known that the decimal expansions of rational numbers are periodic,
we will show this using this principal. Rappelons qu’en e¤ectuant la division de
la fraction pq on obtient une partie entiere e et une partie fractionnaire f , i.e,
p
q = e + f avec 0 f < 1. La partie fractionnaire f est certainement …nie ou
bien périodique.
Exemples 20:
z}|{ z}|{ z}|{
355 4111
4 = 88 + 0; 75; 33300 = 0; 12 345 345 345 :::.
Proposition Prove that the decimal expansion of a rational number is periodic
Proof:
Consider, for convenience, a positive rational number ab ;where 0 < a < b.
Let ab = 0; d1 d2 d3 :::; we have
10a = bd1 + r1 ;
10r1 = bd2 + r2 ;
10r2 = bd3 + r3 ;
.
.
.
10rj = bdj+1 + rj+1
.
.
and 0 ri < b for every i. The digits d1 ; d2 ; :::, in the decimal expansion
are the quotients when 10a; 10r1 ; ::: are divided by b. Since a remainder has
only b choices, by the pigeonhole principle, two of the remainders r1 ; r2 ; :::; rb+1
must be equal; that is, rj = rk for some j and k, where 1 j < k b + 1.
Consequently, dk+1 = dj+1 ; dk+2 = dj+2 ; :::; d2k+j = dk ; d2k+j+1 = dj+1 and so
on. Thus dj+1 :::dk is the smallest block repeated and the period of the decimal
expansion is k j. See the book [ ] for more examples.
Example 21
Suppose a1 ; :::; an are integers. Then "some consecutive sum" ak + ak+1 +
ak+2 + ::: + ak+m is divisible by n.
Consider these n sums:
s1 = a1 ;
s2 = a1 + a2 ;
s3 = a1 + a2 + a3 ;
.
.
.
sn = a1 + a2 + ::: + an .
These are all consecutives sums, if one of them is divisible by n we are
done. If not, dividing each by n leaves a non-zero remainder r1 = s1 mod n;
r2 = s2 mod n; ..., these remainders have values in f1; 2; :::; n 1g. Since there
are n sums and only (n 1) remainders then certainely there is two sums with
the same remainder,

25
 Exercices pour révision
Exercice 16
Démontrer la formule
1 1! + 2 2! + 3 3! + ::: + n n! = (n + 1)! 1:
Exercice 17
Combien un polygone de n sommets a t-il de diagonales? Véri…er la formule
obtenue dans les cas particuliers: n = 3; n = 4; n = 5.
Exercice 18 a/ En évaluant parmi les combinaisons de n objets p à p celles
contenant un élément précisé a et celles ne le contenant pas, établir la formule
n n 1 n 1
= + .
p p p 1
b/ Etablir, par un procédé analogue à celui de la question a), la formule en
n n 2 n 2 n 2
distinguons 2 éléments: = +2 + .
p p p 1 p 2
c/ Même question en distinguons 3 éléments:
n n 3 n 3 n 3 n 3
= +3 +3 + .
p p p 1 p 2 p 3

26
1
 COMBINATOIRE I CHAPITRE III
(MASTER I AMD)

1 III.1 Introduction

Dans ce chapitre, on va étudier le principe général pour compter le nombre d’éléments

Sn
dans une réunion d’ensembles finis Ai , où les ensembles Ai peuvent avoir des
i=1
éléments en communs. Ce principe est connu sous le nom : principe d’inclusion-
exclusion. Après la présentation de ce principe, on donnera des exemples illustratifs
sur son utilisation, notamment sur le calcul des applications surjectives d’un ensemble
fini E vers un ensemble fini F , et le calcul du nombre de dérangements dans un ensem-
ble fini E. Pour le calcul du nombre de surjections d’un ensemble fini E de cardinal
n vers un ensemble F de cardinal m, on va considérer toutes les applications de E
vers F dont le nombre est mn , et on retranchera de ceux-ci le nombre des applications
de E vers F qui n’admettent pas au moins un antécedent, il nous reste donc que les
surjections . De même, pour calculer le nombre de dérangements dans un ensemble
E de cardinal n, on considère toutes les permutations de E dont le nombre est n!, et
on retranchera de ceux-ci les permutations qui laissent au moins un élément de E fixe.
Cette façons de procéder est appelée inclusion-exclusion c.à.d on inclu toutes les élé-
ments de l’ensemble en question et on execlu de ceux-ci les éléments qui ne possedent
pas certaine properiétés (surjectivité, être un dérangement,...etc).

Avant de présenter ce principe dans le cas général, on commence par considérer le

cas le plus simple de réunion non disjoints deux ou bien trois ensembles.

Proposition1 Si A; B sont deux ensembles finis, alors jA [ Bj = jAj + jBj jA \ Bj.

Preuve: Il suffit d’appliquer le principe additif pour la partition de la réunion A [ B

en fA B; A \ B; B Ag. On a jA [ Bj = jA Bj + jA \ Bj + jB Aj. Mais
on a jA Bj = jAj jA \ Bj et jB Aj = jBj jA \ Bj, donc jA [ Bj =
(jAj jA \ Bj) + jA \ Bj + (jBj jA \ Bj) = jAj + jBj jA \ Bj.

Exercice 1 Soit A; B deux ensembles finis. Calculer card(A4B).

Proposition 2 Si A; B; C sont trois ensembles finis, alors jA [ B [ Cj = jAj + jBj +

jCj jA \ Bj jA \ Cj jB \ Cj + jA \ B \ Cj.

2
Preuve: Il suffit d’appliquer la proposition 1 pour l’union (A [ B) [ C.

Pour le cas général, on fait tout d’abord un rappel sur la notion de fonction carac-
téristique d’une partie A d’un ensemble référentiel E. Cette fonction caractéristique
permet de distinguer les éléments de E qui sont dans A et ceux qui ne sont pas. Rap-
pelons qu’on appelle complémentaire de la partie A par rapport à l’ensemble réferentiel
E, la partie formée des éléments de E qui n’appartiennent pas à A, on la note A (voir
figure ci-dessous) on A = E A. Si l’ensemble E est fini alors A = jEj jAj. On
a les propriétés suivantes sur la complémentation
1/ A [ A = E;
2/ A \ A = ;;
3/ A = A;
4/ ; = E;
5/ E = ;.

Les lois de De Morgan nous seront utiles par la suite:

Pour A; B E on a:
6/ A [ B = A \ B,
7/ A \ B = A [ B.

D’une manière générale, si (Ai )i2f1;2;:::;ng est une famille de parties d’un ensemble

3
reférentiel E, on a les lois de De Morgane généralisées:
Sn T
n
8/ Ai = Ai ,
i=1 i=1
T
n S
n
9/ Ai = Ai .
i=1 i=1

2 III.2 Principe d’inclusion-exclusion

On a déja utilisé la fonction caractéristiques dans le chapitre II, où à toute partie A
fx1 ; x2 ; :::; xn g on lui associe une suite binaire unique de B n où B = f0; 1g. On fait
un bref rappel sur cette notion.
Soit A une partie d’un ensemble E. A la partie A on associe une application de E
vers B = f0; 1g qu’on appelle la fonction caractéristique de A qu’on note A . Cette
A (x) = 1 si x 2 A
application est définie par : .
A (x) = 0 si x 2 =A
Exemple1: Soient E = fa; b; cg et la partie A = fa; bg. La fonction caractéristique
de la partie A est définie par : A (a) = 1, A (b) = 1, A (c) = 0 ou bien la séquence
(110).
La fonction caractéristique de la partie ; est ; (a) = A (b) = A (c) = 0, ou bien la
séquence (000).
La fonction de caractéristique de la partie E est E (a) = E (b) = E (c) = 1; ou
bien la séquence (111).

En associant à chaque partie A d’un ensemble E sa fonction caractéristique, on ob-

tient une bijection entre les parties de E et les fonctions caractéristique associées à ces
parties. En d’autres mots on obtient la bijection suivante :
Théorème 1
L’application : } (E) ! B E
A 7 ! (A) = A est une bijection.
Exercice 2 Démontrer que l’application : } (E) ! B E
A 7 ! (A) = A
est une bijection.
Les fonctions caractéristiques des parties suivantes peuvent etre obtenus en utilisant
l’algèbre de Boole sur les parties d’un ensemble référentiel E.
1/ A\B = A B,
2/ A[B = A + B A\B ,
3/ A = 1 A ,
4/ A[B[C = A + B + C A\B A\C C\B + A\B\C .

Démontrons par exemple la 4-ième propriété.

Dans l’ensemble E,On a A [ B [ C = A \ B \ C et

4
donc A [ B [ C = A \ B \ C . D’après la propriété 3, on a
A[B[C = 1 A\B\C = 1 A B C
= 1 (1 A ) (1 B ) (1 C)
= A+ B+ C A B A C B C + A B C,
et par suite on : A[B[C = A + B + C A\B A\C B\C + A\B\C .
P
Comme on a A (e) = jAj pour une partie quelconque A E, on a :
e2E
jA [ B [ Cj = (jAj + jBj + jCj) jA \ Bj jA \ Cj jB \ Cj + jA \ B \ Cj.

Le schéma ci-dessous, montre une illustration de la formule sur 3 ensembles A; B et C

non nécéssairement disjoints. En sommant en premier lieu (jAj + jBj + jCj), chaque
élément appartenant seulement à A (respectivement B, C) est compté une seule fois,
alors que les éléments appartenant aux intersections A \ B, A \ C, et B \ C sont
comptés chacun 2 fois et les éléments appartenant à l’intersection A \ B \ C sont
chacun comptés 3 fois. A cet effet, on va retrancher par la formule jA \ Bj
jA \ Cj jB \ Cj, les éléments appartenant aux trois intersections, mais il faut ajout-
ter cette fois ci jA \ B \ Cj, car on vient de le retrancher 3 fois dans l’expression
jA \ Bj jA \ Cj jB \ Cj. Le schéma ci-dessous illustre cette situation.

Exercice Montrer en utilisant la fonction caractéristique d’une partie A d’un ensmble

fini E qu’on a A = jEj jAj.

5
 Basic examples
Suppose a group of students are studying logic or mathematics. If 12 are studying
logic, 26 are studying mathematics and 5 are studying both subjects. How many stu-
dents are in the group.
Solution
let A be the group of students studying logic,
and let B be the group of students studying mathematics. Find jA [ Bj.
Solution
We have jA [ Bj = jAj+jBj jA \ Bj then the total students is 26+12 5 = 33. And

we have 12 5 = 7 which study logic only and 26 5 = 21 which study mathematics

only.
Exemple 2 Déterminer le nombre des entiers naturels 1000 non divisibles ni par 3;ni
par 5 ni par 7.
Let A be the subset of integers which are divisible by 3, B the subset of integers
which are divisible by 5, and C the subset of integers which are divisible by 7. Then
S = A \ B \ C since each element of S is not divisible by 3; 5 or 7.
By integer division we have jAj = 1000=3 = 333;i.e, the number from 3 to 999,
jBj = 1000=5 = 200,
jCj = 1000=7 = 142,
jA \ Bj = 1000=15 = 66 (the numbers divisible by 3 and 5 = the numbers divisible
by 15),
jA \ Cj = 1000=21 = 47;
jB \ Cj = 1000=35 = 28;
jA \ B \ Cj = 1000=105 = 9.
Thus, by the inclusion exclusion principle, we have:
jSj = 1000 (333 + 200 + 142)+(66 + 47 + 28) 9 = 1000 675+141 9 = 457
numbers are not divisible by 3; 5 or 7.

2.1 III.2.1 Le principe d’inclusion-exclusion en utilisant des

ensembles finis
It is now not difficult to see how to extend this formula to deal with the general case of the
number of elements in a union of n sets.

Theorem 2 (the inclusion-exclusion theorem)

For all sets A1 ; A2 ; :::; An
jA1 [ A2 [ ::: [ An j

6
= (jA1 j + jA2 j + ::: + jAn j)
(jA1 \ A2 j + jA1 \ A3 j + ::: + jAn 1 \ An j)
+ (jA1 \ A2 \ A3 j + jA1 \ A2 \ A4 j + ::: + jAn 2 \ An 1 \ An j)
+:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
n+1
+ ( 1) jA1 \ A2 \ ::: \ An j
!
S
n P
n
k+1 P
= Ai = ( 1) jAi1 \ ::: \ Aik j .
i=1 k=1 1 i1 <:::<ik n
here the expression 1 i1 < ::: < ik n under the summation is taken for all the
strict increasing sequences of natural numbers of length k with 1 k n. In others
k
words, the expression 1 i1 < ::: < ik n is a sum over all the distinct
j
integers j-tuples (i1 ; :::; ij ) satisfying 1 i1 < ::: < ij k and k varies between 1
and
Par exemple, pour n = 1 on a seulement k = 1, et donc la seule sequence croissante
d’entiers natureles de longueur 1 entre 1 i!
1 1 est bien i1 = 1, et donc jA1 j =
P
n=1
k+1 P 1+1
( 1) jAi1 \ ::: \ Aik j = ( 1) (jA1 j) = jA1 j.
k=1 1 i1 <:::<ik 1
Pour n = 2, l’entier natural k varie entre 1 et 2 et par suite, il faut voir avec les
séquences de longueurs 1 et les séquences de longueurs 2. On a deux séquences de
longueur 1 qui sont: 1 i1 = 1 2 et 1 i2 = 2 2 et une seule séquence de
longueur 2 qui est 1 i1 = 1 i2 = 2 2 et par suite on a:
!
S
2 P2
k+1 P
Ai = ( 1) jAi1 \ ::: \ Aik j
i=1 k=1 1 i1 <:::<ik 2
1+1 2+1
= ( 1) (jA1 j + jA2 j) + ( 1) (jA1 \ A2 j)
= (jA1 j + jA2 j) (jA1 \ A2 j).

Pour n = 3, les suites strictements croissantes entre 1 et 3 sont:

- 3 suites de longueur 1 qui sont:1 i1 = 1 3, 1 i2 = 2 3, 1 i3 = 3 3.
- 3 suites de longueur 2 qui sont:(i1 < i2 ) = (1 < 2); (i1 < i3 ) = (1 < 3); et (i2 ; i3 ) =
(2 < 3).
- et une seule suite de longueur 3, qui est (i1 < i2 < i3 ) = (1 < 2 < 3). Et par suite,
la formule s’écrit: !
S3 P3
k+1 P
Ai = ( 1) jAi1 \ ::: \ Aik j
i=1 k=1 1 i1 <:::<ik 3
1+1 2+1
= ( 1) (jA1 j + jA2 j + jA3 j) + ( 1) (jA1 \ A2 j + jA1 \ A3 j + jA2 \ A3 j) +
3+1
( 1) (jA1 \ A2 \ A3 j)
= (jA1 j + jA2 j + jA3 j) (jA1 \ A2 j + jA1 \ A3 j + jA2 \ A3 j) + (jA1 \ A2 \ A3 j).

Exercice 3Démontrer par récurrence sur n le théorème d’inclusion-exclusion.

7
2.2 III.2.2 Principle of Inclusion and exclusion using the
conditions

Suppose we have a set of N objects that have various properties or conditions , , ,...,
. Each of the object may have any or none of these properties. Let N the number
of objects that have property . Some of these objects may have other properties in
addition to property . Similarly, let N be the number of objects that have property B,
and so on. Let N be the number of objects that have both property and property ,
also N be the number of objects that have both property and , etc. Finally denote
by N ::: the number of objects with all the properties. Given all this information,
we wish to find N0 the number of objects that have none of the properties. The general
formula for computing this is called the principal of inclusion and exclusion

N0 = N N N N ::: N
+N + N + ::: + N + ::: + N
N N :::::
:::::::::::::::::::::::::::::::::
+N ::: .
Using the notion of characteristic function attached to a subset A of universe U we can
derive the above formula.
Let U the set of universe (the totality of things) in which we are interested. And
A; B; C; :::etc represent subsets of U and x; y; z etc will be individual objects of U .
1 if x 2 A
For any set A, we define the characteristic function attached to A by A (x) = .
0 if x 2
=A
Example 3 Let U = f1; 2; 3; 4; 5; 6g, and let A be the subset of U consisting of the
divisors of 6. Then A (1) = 1, A (2) = 1, A (3) = 1, A (4) = 0, A (5) = 0, A (6) = 1.
Note that also we have U (x) = 1 for all x 2 U and ; (x) = 0 for all x 2 U .
The complement of A; denoted A consists of exactly those objects of U that are not in
A. Then the characteristic function attached to A is:
A (x) = 1 A (x).
If C = A \ B then C (x) = A (x) B (x),
If D = A [ B then D (x) = 1 (1 A (x)) (1 B (x)) = A (x) + B (x)
A (x) B (x). Finally, the number of elements in a set A U is the
P summation of
the characteristic function over all elements in the finite set U , i.e, A (x). So we
x2U
can now transform operations on sets into arithmetic operations. Let A be the set of
^
objects with property , and B the set of objects with property . We let N be the set
of objects having none of the properties ; ; :::; . What is the characteristic function
^ ^
of N . Every element of N is contained in the complement of each of the sets A; B;
^
:::; L. That is N is the intersection of the complements of all of the individuals sets.
^
So the characteristic function is N = (1 A) (1 B) (1 C) ::: (1 L). We want

8
 ^
to know how many elements are in the set N ; i.e, the number of elements having none
of the properties. And this number is:
P
(1 A) (1 B) (1 C) ::: (1 L)
x2U
P
= ((1 A B C ::: L) + AB + AC + ::: + KL
x2U
ABC
+ABCD
:
:
+[Link]L)
P P P P
= 1 A B ::: L
x2U x2U x2U x2U
P
+ [Link]
x2U
P
ABC
x2U
:
:
P
+ [Link]L.
x2U
=) N0 = N N N N ::: N
+N + N + ::: + N + ::: + N
N N :::::
:::::::::::::::::::::::::::::::::
+N ::: .
Problem1
How many integers are there in the range from 1 to 1000:000 which are divisible by 2
or by 3 or both?
Solution
We let D2 and D3 be the sets of those integers in the range from 1 to 1000:000 which
are divisible by 2 and by 3 respectively. By the above theorem 1, we have:
jD2 j = 500:000; jD3 j = 333:333.
Any integer is divisible by both 2 and 3 iff it is divisible by 6. Hence jD2 \ D3 j =
166:666. Thus jD2 [ D3 j = 500:000 + 333:333 166:666 = 666667.
Example 4

The Euler ' function is defined by ' (n) = jfk 2 N+ : k < n and gcd (k; n) = 1gj
and this function is multiplicative i.e, if the natural numbers m and n are coprime
(gcd (m; n) = 1) then ' (nm) = ' (n) ' (m). Calculate, using inclusion-exclusion
theorem, a formula for ' (n) when the distinct prime factors of n are p1 ; p2 ; :::; pk .
show that ' (n) = n 1 p11 1 p12 ::: 1 pk 1
.
e
If n = pe11 pe22 :::pekk then gcd pei i ; pj j = 1 for all 1 i; j k with i 6= j. We obtain
then ' (n) = ' (pe11 ) ' (pe22 ) ::: ' (pekk ). (Rappelons que si p est un nombre

9
premier alors les seuls diviseurs de p sont les nombres 1 et p, et donc les seuls diviseurs
de pt sont les nombres: p1 ; p2 , p3 ; :::; pt . Et par conséquent, le seul diviseur commun
e e
des nombres pei i et pj j est le nombre 1; c.à.d gcd pei i ; pj j = 1).

' (pet t ) représente le nombre des entiers naturels entre 1 et pet t qui sont premiers avec
pet t . les nombres entre 1 et pet t qui ne sont pas premiers avec pet t sont les multiples du
nombre premier pt et ces nombres sont: 1p; 2p; 3p; :::; p2 ; 2 p2 ; :::::; p3 ; :::pet 1 p
dont le cardinal est pet 1 . Comme il y’a pet t nombre natural entre 1 et pet t donc, par
inclusion exclusion on a ' (pet t ) = pet t pet 1 = pet 1 (pt 1).

Appliquons ce resultat au calcul de ' (n). On a donc:

' (n) = ' (pe11 ) ' (pe22 ) ::: ' (pekk ) =
= pe1 1 (p1 1) pe2 1 (p2 1) :::pek 1 (pk 1)
= pe1 1 pe2 1 :::pek 1 (p1 1) (p2 1) ::: (pk 1)
1 1 1
= p e1 1 e2 1
p :::pek 1
p1 1 p1 p2 1 p2 :::pk 1 pk

= pe1 pe2 :::pe1k 1 1

p1 1 1
p2 ::: 1 1
pk
1 1 1
=n 1 p1 1 p2 ::: 1 pk :
Pour n = 30 on a: 30 = 2 3 5.0
Donc
' (30) = 30 1 12 1 1
3 1 1
5
= 30 2 2 1 3 3 1 5 5 1 = 30 30 (1) (2) (4) = 8. Il y’a donc 8 nombres entre 1et 30 qui
sont premiers avec le nombre 30. Ces nombres sont:f1; 7; 11; 13; 17; 19; 23; 29g.

Exercice 4 On note par Zn l’ensemble des éléments de Zn inversibles par rapport la

multiplication des classes c.à.d,
8x 2 Zn , 9y Zn tel que: x y = 1 avec 1 = 1 + nZ.
Montrer que (Zn ; ) est un groupe d’ordre ' (n) d’élément neutre la classe 1: Ce
groupe est appelé le groupe des unités de Zn ou bien le groupe des éléments inversibles,
par rapport à la multiplication des classes, modulo n.

Dérangements
Among the permutations of f1; 2; :::; ng there are some called dérangements in which
1 2 : : : n
none of the integers appears in its natural place. Thus the permutation
i1 i2 : : : in
noted by (i1 ; i2 ; :::; in ) is a derangement if i1 6= 1; i2 6= 2; :::;and in 6= n (is it noted
here that the notation (i1 ; i2 ; :::; in ) is not cyclic notation). Let Dn the number of de-
rangements of f1; 2; :::; ng. As illustrations, we note that D1 = 0; D2 = 1 because
there is one derangement namely, (2; 1); and D3 = 2 because (2; 3; 1) and (3; 1; 2)

10
are the only derangements in the set of the 3! = 6 permutations of f1; 2; 3g. We want
to derive a formula for Dn that is valid for each positive integer n using inclusion-
exclusion principle. Let U be the set of n! permutations of f1; 2; :::; ng. For each i, let
Ai be the permutations (b1 ; b2 ; :::; bn ) of f1; 2; :::; ng such that bi = i. Then the set of
derangements is precisely the set A1 A2 \ ::: \ An , therefore Dn = A1 A2 \ ::: \ An .
The permutations in A1 are all of the form (1; b2 ; :::; bn ) where (b2 ; :::; bn ) is a permu-
tation of the set f2; 3; :::; ng. Thus jA1 j = (n 1)!. Similarly, jAi j = (n 1)!.
Likewise, A1 \ A2 is the set of permutations of the form (1; 2; b3 ; :::; bn ) so that
jA1 \ A2 j = (n 2)!. For any integer k where 1 k n, the permutations in
A1 \ A2 \ ::: \ Ak are of the form (1; 2; :::; k; bk+1 ; :::; bn ) where (bk+1 ; :::; bn ) is
a permutation of the set fk + 1; :::; ng. Thus jA1 \ A2 \ ::: \ Ak j = (n k)! and
more generally, jAi1 \ Ai2 \ ::: \ Aik j = (n k)! for (i1 ; i2 ; :::; ik ) a k-combination
of f1; 2; :::; ng.
Thus jU j jA1 [ A2 [ ::: [ An j =
n
n! C (n; 1) (n 1)! + C (n; 2) (n 2)! + ::: + ( 1) C (n; n)
n
= n! n! 1! + 2!
n! n!
+ ::: + ( 1) n! n! :
h 3! n
i
Then Dn = n! 1 1! 1
+ 2!1
+ ::: + ( n!1) .
1 1 1 1 1
For example, D5 = 5! 1 1! + 2! 3! + 4! 5! = 44.

Pour calculer encors une fois Dn , nous pourrons suivre une autre démonstration,
mais cette fois ci, en utilisant une formule par récurrence.

Fixed-point theorems

A permutation is arrangement of the sequence f1; 2; :::; ng. Notons que dans cette sec-
1 : : : n
tion on note une permutation = par = ( (1) ; :::; (n)),
(1) : : : (n)
1 2 3 4
par exemple (2; 3; 1; 4) = (il ne faut pas confondre avec la notation
2 3 1 4
cyclique). We say that a permutation fixes k if k is in the k-th place. For instance (1; 2)
is a permutation of f1; 2g which fixes both 1 and 2. The permutation (2; 3; 1; 4) fixes
only 4. Let 1 k n be a whole number. We say that a permutation (x1 ; :::; xn ) of
f1; :::; ng fixes k if xk = k. We say that the permutation has at least 1 fixed point if the
permutation fixes k for some 1 k n. The permutation is a derangement if it has
no fixed points.
The problem is to count the number of permutations with at least 1 fixed point, and the
number of permutations without fixed points.
Let Fn = the number of permutations of f1; :::; ng with at least 1 fixed point.
We must find F2 ; F3 and in general Fn for any number n > 1.
Example 5
Let n > 1 be a whole number. We count the number of derangements of f1; :::; ng.
Solution:

11
Let U be the set of all permutations of f1; :::; ng and let F Pn be the set of permutations
of f1; :::; ng that have at least 1 fixed point. Then we have n (U ) = n! and n (F Pn ) =
Fn .
The complement of F Pn is the set F Pn0 of all permutations of f1; :::; ng that have no
fixed points. Then by the complement formula
n (F Pn0 ) = n (U ) n (F Pn ) = n! Fn .
Then n! Fn = The number of derangements of f1; :::; ng.
Problem
3
a/ Show that F2 = 1 and F3 = (2! F2 ) + 1 = 4.
1
b/ Prove that
n
Fn = ((n 1)! Fn 1 )
1
n
+ ((n 2)! Fn 2)
2
n
+::: + ((2)! F2 ) + 1.
n 2
c/ Conclude that the number of derangements of f1; :::; ng is
n
n! Fn = n! + (Fn 1 (n 1)!)
1
n n
+ (Fn 2 (n 2)!) + ::: + (F2 2!) 1.
2 n 2
d/ Find F4 and the derangements of f1; 2; 3; 4g. Find F5 and the derangements of
f1; 2; 3; 4; 5g.

Le principe d’inclusion-exclusion peut être formaliser en termes de conditions ou bien

de properiétésfc1 ; c2 ; :::; ct g que peuvent possèder ou bien vérifier certains éléments
d’un ensemble fini E = fx1 ; x2 ; :::; xn g.

Exemple 6
Soit U M l’ensemble des étudiants de l’université de M’sila avec n = jU M j.
On considère, par exemple, les conditions suivantes :
c1 : "l’etudiant x pratique le football ou bien le footboll", et on note par n (c1 ) le
nombre des étudiants de U M qui pratiquent le football et par n (c01 ) = n n (c1 ), le
nombre des étudiants ne pratiquent pas le football.
c2 :"l’etudiant x pratique le footing ", et par n (c2 ) le nombre des étudiants de U M
qui pratiquent le footing et par n (c02 ) = n n (c2 ) le nombre des étudiants de U M ne
pratiquant pas le footing.
c3 :"l’etudiant x pratique la natation ", et par n (c3 ) le nombre des étudiants de U M
pratiquant la natation, et par n (c03 ) = n n (c3 ) le nombre des étudiants de U M ne
pratiquant pas la natation.

12
 On note aussi par n (c1 c2 ) le nombre des étudiants pratiquant en meme temps le foot-
ball et le footing. De même, on notera par n (c01 c02 c03 ) le nombre des étudiants de U M
qui ne pratiquent ni le football ni le footing ni la natation. On peut schématiser ces
conditions par la figure ci-dessous.

Donnons une autre démonstration du principe d’inclusion-exclusion en utilisant les

conditions (voir la référence 2).
Le cas général

Consider a set of n objects. Let c1 ; c2 ; :::; cr be a set of properties that these objects

13
may have. In general, these properties are not mutually exclusive, that is an object can
have one or more of these properties.
Let n (c1 ) denote the number of objects that have the property c1 and let n (c2 )
denote the number of objects that have the property c2 ,...., and let n (cr ) denote the
number of objects that have the property cr . Notice that, an object having the property
ci is included in the count n (ci ). If an object has both the properties ci and cj it will
contribute a count in n (ci ) as well as a count in n (cj ). Let n (c0i ) denote the number
of objects that do not have the property ci . Let n (ci cj ) denote the number of objects
that have both the properties ci and cj . Let n c0i c0j denote the number of objects that
have neither the property ci nor the property cj .

Considérons un ensemble de n objets. Soit c1 , c2 , ..., cr un ensemble de propriétés

ou bien conditions que ces objets peuvent avoir ou bien satisfaire . En général, un
élément de cet ensemble peut avoir une ou plusieurs de ces propriétés et peut aussi ne
posséder aucune de ces propriétés. Voir l’exemple sur l’université de M’sila, où un
étudiant peut pratiquer 1 ou bien 2 ou bien 3 sports et peut aussi ne pas pratiquer aucun
de ces activités.
Soit n(c1 ) le nombre d’objets qui ont la propriété n (c1 ) et soit n (c2 ) le nombre
d’objets qui possédent la propriété c2 , ...., et n (cr ) le nombre de objets qui ont la pro-
priété cr . Notons que si un objet possède à la fois les propriétés ci et cj , il contribuera
au nombre n (ci ) et contribuera aussi au nombre n (cj ). Soit n (c0i ) = n n (ci ) le nom-
bre d’éléments qui ne possèdent pas la propriété ci . Soit n (ci cj ) le nombre d’éléments
qui ont à la fois les propriétés ci et cj . Soit n c0i c0j le nombre d’éléments qui n’ont ni
la propriété ci ni la propriété cj . Soit n (c0i cj ) le nombre d’éléments ayant la propriété
cj mais ne possédant pas la propriété cj . On a donc n (c0i cj ) = n (cj ) n (ci cj ) (les
éléments qui possédent la propriété cj mais ne possédant pas la propriété ci ). De la
même façon, on peut écrire:
n c0i c0j = n n ci c0j n (c0i cj ) n (ci cj )
=n n ci c0j + n (ci cj ) (n (c0i cj ) + n (ci cj )) + n (ci cj )
= n n (ci ) n (cj ) + n (ci cj ).
En général, on a:
n (c01 c02 :::c0r ) = n n (c1 ) n (c2 ) ::: n (cr )
+n (c1 c2 ) + n (c1 c3 ) + ::: + n (cr 1 cr )
:::::::::::::::::::::::::::::::::::
r
+ ( 1) n (c1 c2 :::cr )
Pr
=n n (ci )
Pi=1
+ n (ci cj )
1 i<j r
P
n (ci cj ck )
1 i<j<k r
r
+::: + ( 1) n (c1 c2 :::cr ).

14
Exercice 6 Faire la démonstration de ce résultat par récurrence sur le nombre r de
conditions que peuvent posséder les éléments d’un ensemble E contenant un nombre
n d’éléments.
Le schéma ci-dessous montre une illustration de cette formule.

Appliquons la formule d’inclusion-exclusion pour calculer le nombre de surjections

d’un ensemble A de cardinal m vers un ensemble B de cardinal n avec m n. Il

faut noter ici, si m < n, alors on ne peut avoir un surjection entre l’ensemble A vers
l’ensemble B, car il y’a n m > 0 éléments de l’ensemble B qui n’admettent pas
d’antécédents. Soit donc, A = fa1 ; a2 ; :::; am g, B = fb1 ; b2 ; :::; bn g avec m n.
Notons aussi par S l’ensemble de toutes les applications f : A ! B. Soit S0 = jSj =
nm . Pour 1 i n, on note par ci la condition :"l’élément bi n’a pas d’antécédent"
ce qui revient au même de dire que l’élément bi n’est pas l’image de toute application
de A vers B. Dans ce cas, n (c0i ) est le nombre des fonctions dans S qui admettent
bi comme image, et note aussi par n (c01 c02 :::c0n ) le nombre de fonctions surjectives de
l’ensemble A vers l’ensemble B, c.à.d, le nombre d’applications où chaque élément de
l’ensemble d’arrivée B, admet au moins un antécédent.

15
 m
On a pour tout 1 i n, n (ci ) = (n 1) . On a ce résultat parce que , car
chaque element de B, à l’excéption de bi , peut être utilisé comme image d’une fonction
f : A ! B; et par suite on a: imf = f (A) = jBj 1 = n 1.
m
De même, pour toutes 1 i < j n il y’a (n 2) applications f : A ! B qui
admettent ni bi ni bj comme images. Soit donc, S1 = n (c1 ) + n (c2 ) + ::: + n (cn ) =
m
n (n 1) .
n m
S2 = n (c1 c2 ) + n (c1 c3 ) + ::: + n (cn 1 cn ) = (n 2) .
2
P
D’une manière générale, on a: pour tout 1 k n, Sk = n (ci1 ci2 :::cik ) =
1 i1 <i2 <:::<ik n
n m
(n k) .
k
Par conséquent, le nombre d’applications surjectives de l’ensemble A vers l’ensemble
n
B est n (c01 c02 :::c0n ) = S0 S1 + S2 S3 + ::: + ( 1) Sn
n m n m n m m
= nm (n 1) + (n 2) (n 3) + :::: + (n n)
1 2 3
Pn
i n m Pn
i n m
= ( 1) (n i) = ( 1) (n i) .
i=0 i i=0 n i
Voir la référence 3 pour plus d’exemples.
Exercice 7 In how many ways can the 26 letters of the alphabet be permuted so that
none of the patterns car, dog, pun,or byte occurs.

Réferences
1/ Jacques Vélu Méthodes mathématiques pour l’informatique, Dunod.
2/ C.L. LIU,Introduction to combinatorial Mathematics Mc Graw-Hill Book Company.

3/ Raplh P. Grimaldi, Discrete and combinatorial mathematics, Pearson Addison Wes-

ley0 (5ed).

16