Chapitre 6  Dénombrement

6.1  Nombre d’applications d’un ensemble fini dans un ensemble fini

Soient deux ensembles E dans F de cardinaux respectifs p et n. Soit A(E,F) l’ensemble des applications de E dans F. Soit u(p,n) le nombre d’applications de E dans F. On a : u(p,1)=p car si E=a et F=b₁,b₂..b_p les applications de E dans F sont définies par :
f_j(a)=b_j) avec 1≤ j≤ p
On montre par récurrence que u(p,n)=p*u(p,n−1).
En effet :
si E=a₁,a₂...a_n et E₁=a₂...a_n, une application de E dans F est définie par une application de E₁ dans F et par f(a₁)=b_j pour 1≤ j≤ p.
Donc u(p,n)=pⁿ

6.2  Nombre d’injections d’un ensemble fini dans un ensemble fini : les arrangements

Soient deux ensembles E dans F de cardinaux respectifs p et n avec n≥ p.
Soit I(E,F) l’ensemble des injections de E dans F. Soit v(n,p) le nombre injections de E dans F. On a : v(n,1)=n car si E=a et F=b₁,b₂..b_n les injections de E dans F sont définies par :
f_j(a)=b_j) avec 1≤ j≤ n
On montre par récurrence que v(p,n)=(n−p+1)*v(p,n−1).
En effet :
si E=a₁,a₂...a_p et E₁=a₂...a_p, une injection de E dans F est définie par une injection de f de E₁ dans F et par f(a₁)∈ F∖ f(E₁).
Comme F∖ f(E₁) a pour cardinal n−(p−1)=n−p+1 on a :
v(n,p)=(n−p+1)*v(n,p−1) Donc v(n,1)=n,v(n,2)=n(n−1),...,v(n,p)=n(n−1)...(n−p+1)
En utilisant la notation factorielle on a donc :

Définition v(n,p) est le nombre d’arrangements sans répétition de p objets pris parmi n objets (p≤ n).
Avec Xcas v(n,p) se note perm(n,p).
On tape :
perm(n,p)
On obtient : (n!)/((n-p)!)
On tape :
perm(6,3)
On obtient : 120

6.3  Nombre de bijections d’un ensemble fini dans un ensemble fini : la factorielle

Soient deux ensembles E dans F de même cardinaux n.
Le nombre de bijections de E dans F est égal au nombre d’injections de E dans F car E et F ont le même nombre déléments.
Le nombre de bijections de E dans F est donc 1*2*..*n =n! Avec Xcas v(n,p) se note perm(n,p).
On tape :
6!
On obtient : 720
On tape :
3!
On obtient : 6

6.4  Nombre de parties à p éléments d’un ensemble à n éléments : les combinaisons

Soit un ensemble E de cardinal n (n≥ 1) et soit un entier p≤ n.
Soit w(n,p) le nombre de parties de E ayant p éléments.
Soit f une injection de I=[1,p] dans E dans f(I) est une partie de E qui a p éléments.
Soit F l’application qui a une injection f de I=[1,p] dans E fait correspondre f(M) i.e. F(f)=f(M).
F est surjective mais n’est pas injective car si:
F(f₁)=F(f₂) cela entraine f₁(M)=f₂(M).
Soit f₁ une injection de I=[1,p] dans E et F=f₁(M). Donc I et F sont de cardinal p.
D’après le paragraphe précédent, le nombre d’injections f de I=[1,m] dans E tel que f(M)=F est p! car ces injections sont des bijection de I dans F. Donc le nombre de parties de E ayant p éléments est égal au nombre d’injection de I dans E divisé par p!.
Donc :

On remarquera que la formule est encore valable pour n=p=0 puisque w(0,0)=1 Définition w(n,p) est le nombre de combinaisons sans répétition de p objets pris parmi n objets (p≤ n).
Avec Xcas w(n,p) se note comb(n,p).
On tape :
simplify(comb(n,p))
On obtient : (n!)/((n-p)!*p!)
On tape :
comb(6,3)
On obtient : 20

6.5  Les combinaisons avec répétition

6.5.1  La définition

Définition
Soit un ensemble E de cardinal n (n≥ 1) et soit un entier p.
Le nombre d’ensemble ayant p éléments de E, chaque élément pouvant être est appelé combinaison avec répétition de p éléments pris parmi n.

6.5.2  Une démonstration

Soit c(n,p) le nombre de combinaisons avec répétition de p éléments pris parmi n.
On va montrer que l’on a : c(n,p)=comb(n+p-1,n-1)=comb(n+p-1,p) à l’aide de l’exercice suivant.
Enoncé
Soient O et A 2 points tels que OA=p.
1/ On suppose p≥ n. De combien de manières peut-on placer entre O et A (O et A exclus) n−1 points d’abscisse entière ?
2/ Application Nombre de solutions de l’équation x₁+x₂+...x_n=p :
a/ lorsque les x_i sont des entiers >0 et p≥ n.
b/ lorsque les x_i sont des entiers ≥ 0
3/ En déduire la valeur de c(n,p)
Solution
1/ Entre O et A (O et A exclus) il y a p−1 points.
Donc on peut placer n−1 points d’abscisse entière de comb(p-1,n-1) manières différentes.
2/ a/ Pour résoudre x₁+x₂+...x_n=p lorsque les x_i sont des entiers >0, on place n−1 points M₁,M₂..M_n−1 d’abscisse entière m₁,m₂..m_n−1 entre O et A et on pose :
x₁=m₁,x₂=m₂−m₁,....x_n−1=m_n−1m_n−2,x_n=p−m_n−1
On a alors x₁+x₂+...x_n=p.
Réciproquement à chaque solution x₁,x₂,...,x_n de x₁+x₂+...x_n=p lorsque les x_i sont des entiers >0, il correspond n−1 points d’abscisse entière entre O et A ce sont :
M₁,M₂..M_n−1 d’abscisse respective x₁,x₁+x₂,...,∑_i=..n−1x_i.
Le nombre de solution est donc comb(p-1,n-1) b/ Pour résoudre x₁+x₂+...x_n=p lorsque les x_i sont des entiers ≥ 0, on se raméne au cas précédent en posant :
y_i=x_i+1 (si x_i est un entier ≥ 0, y_i est un entier >0).
À chaque solution de x₁+x₂+...x_n=p où les x_i sont des entiers ≥ 0 correspond une solution de y₁+y₂+...y_n=n+p où les y_i sont des entiers >0 et on a n+p≥ n.
Donc le nombre de solutions de l’équation x₁+x₂+...x_n=p lorsque les x_i sont des entiers ≥ 0 est comb(n+p-1,n-1)=comb(n+p-1,p).
3/ c(n,p) est le nombre de combinaisons avec répétition de p éléments pris parmi n. Soient a₁,a₂,...a_n les n élements de E. Chaque combinaison avec répétition de p éléments pris parmi ces n élements est À chaque solution de x₁,x₂,...x_n=p avec x_i ≥ 0 pour i=1..n il correspond une combinaison avec répétition de p éléments pris parmi ces n élements a_i à savoir on a la combinaison qui correspond aux p élements :
x₁ fois a₁,x₂ fois a₂,...x_n fois a_n (il y bien p élements puisque x₁,x₂,...x_n=p. Réciproquement à chaque combinaison avec répétition de p éléments pris parmi a₁,a₂,...a_n il correspond une solution de x₁,x₂,...x_n=p avec x_i ≥ 0 pour i=1..n. Donc c(n,p)=comb(n+p-1,n-1)=comb(n+p-1,p)

6.5.3  Autre démonstration

Soient a₁,a₂,...a_n les n élements de E.
1/ On cherche combien de fois l’élément a₁ figure dans les c(n,p) combinaisons avec répétition de p éléments pris parmi ces n élements a_i (i=1..n).
Dans chaque combinaison il y a p éléments donc en tout il y a :
p*c(n,p) éléments.
Les n éléments figurent le même nombre de fois donc :
l’élément a₁ figure p*c(n,p)/n fois dans les c(n,p) combinaisons
et de même pour tout i=1..n,
l’élément a_i figure p*c(n,p)/n fois dans les c(n,p) combinaisons.
2/ Cherchons une relation entre p*c(n,p)/n et c(n,p−1) Parmi les combinaisons à répétition, il y en a :
c(n−1,p)=comb(n+p-2,p) qui ne contiennent pas a₁.
Parmi les combinaisons à répétition, il y en a :
c(n,p−1)=comb(n+p-2,p-1) qui contiennent a₁ au moins une fois (car on a comb(n+p-2,p-1)+comb(n+p-2,p)=comb(n+p-1,p))
D’après 1/ l’élément a₁ figure (p−1)*c(n,p−1)/n fois dans les c(n,p−1) combinaisons
Donc dans les c(n,p) combinaisons il y a c(n,p−1) combinaisons qui contiennent a₁ au moins une fois. Cherchons le nombre de fois où apparait a₁ parmi les combinaisons qui contiennent a₁ au moins une fois. Ces combinaisons sont au nombre de c(n,p−1). Si on enlève a₁ de ces combinaisons il reste une combinaison avec répétition de p−1 éléments pris parmi ces n élements a_i (i=1..n). On sait d’apr‘es 1/ que a₁ figure (p−1)*c(n,p−1))/n fois dans les c(n,p−1) combinaisons. Donc l’élément a₁ figure c(n,p−1)+(p−1)*c(n,p−1)/n fois dans les c(n,p) combinaisons.
On a donc la relation :

Donc puisque c(n,1)=n :

donc on en déduit que :
c(n,p)=comb(n+p-1,p)= comb(n+p-1,n-1)
Remarque
On a c(n,0)+c(n,1)+...+c(n,p)=c(n+1,p)
On tape :
sum(comb(n+k-1,n-1),k=0..p)-comb(n+p,n)
On obtient :
0
Par récurrence sur p on a :
c(n,0)+c(n,1)=1+n=c(n+1,1)
si c(n,0)+c(n,1)+...+c(n,p)=c(n+1,p) alors
c(n,0)+c(n,1)+...+c(n,p)+c(n,p+1)=c(n+1,p)+c(n,p+1)=
comb(n+p,p)+comb(n+p,p+1)=comb(n+p+1,p+1)=c(n+1,p+1)
En effet proriété de comb :
comb(n,p)=comb(n-1,p)+comb(n-1,p-1) pour tout n et p≤ n donc
comb(n+p,p)=comb(n+p-1,p)+comb(n+p-1,p-1)

6.5.4  Exercice

Dans une patisserie il y 10 sortes de gateaux.
De combien de manières peut-on en choisir 6 :
a/ de sortes différentes,
b/ de même sorte ou de sortes différentes, c/ de même sorte ou de sortes différentes dans le cas ou il ne reste que 3 gateaux d’une certaine sorte. Solution
a/ Il y a comb(10,6)=210 de choisir 6 gateaux de sortes différentes parmi 10 sortes.
b/ Il y a comb(15,6)=5005 de choisir 6 gateaux de même sorte ou sortes différentes parmi 10 sortes car ici n=10 et p=6.
c/ si il ne este que 3 gateaux de la sorte a₁, il y a comb(14,6)=3003 manières de prendre 6 gateaux sans la sorte a₁ (n=9, p=6 et n+p−1=14 i.e 9 sortes et 6 gateaux)
comb(13,5)=1287 manières de prendre 6 gateaux dont 1 gateau de la sorte a₁,(n=9, p=5 et n+p−1=13)
comb(12,4)=495 manières de prendre 6 gateaux dont 2 gateaux de la sorte a₁,(n=9, p=4 et n+p−1=12)
comb(11,3)=165 manières de prendre 6 gateaux dont 3 gateaux de la sorte a₁,(n=9, p=3 et n+p−1=11)
Donc il y a 3003+1287+495+165=4950 manières de prendre 6 gateaux de même sorte ou de sortes différentes dans le cas ou il ne reste que 3 gateaux d’une certaine sorte.
Vérifions :
On a comb(10,2)=45 manières de prendre 6 gateaux dont 4 gateaux de la sorte a₁,(n=9, p=2)
On a comb(9,1)=9 manières de prendre 6 gateaux dont 5 gateaux de la sorte a₁,(n=9, p=1)
On a comb(9,0)=1 manières de prendre 6 gateaux dont 6 gateaux de la sorte a₁,(n=9, p=0)
et on a bien : 4950 +55=5005.

6.6  Nombre de surjections d’un ensemble fini dans un ensemble fini

Exercice 1 Soient E un ensemble ayant p éléments et F un ensemble ayant q éléments. On cherche le nombre de surjections de E dans F.

1. Calculer ∑_{A⊂ E}(−1)^Card(A)
2. Soient f une application de E dans F et B une partie de F∖ f(E).
   On pose : S(f)=∑_{B⊂ F∖ f(E)}(−1)^Card(B)
   Montrer que :
   S(f)=1 si f est surjective et S(f)=0 si f n’est pas surjective.
3. En déduire le nombre de surjections de E dans F

La solution

1. Si p=0 alors E=∅ donc ∑_{A⊂ E}(−1)^Card(A)=(−1)⁰=1
   Si p≠ 0 alors il y a comb(p,k) sous-ensemble A de E qui ont k éléments A, donc
   ∑_{A⊂ E}(−1)^Card(A)=∑_k=0^pcomb(p,k)(−1)^k=(1−1)^p=0 d’après la formule du binôme.
2. Si f est surjective F∖ f(E)=∅ donc S(f)=1 d’après ce qui précéde.
   Si f n’est pas surjective F∖ f(E)≠ ∅ donc S(f)=0 d’après ce qui précéde.
   
3. Soit A(E,F) l’ensemble des applications de E dans F.
   D’après ce qui précède le nombre de surjections de E dans F est :
   ∑_{f∈ A(E,F)}S(f)=∑_{f∈ A(E,F)}∑_{B⊂ F∖ f(E)}(−1)^Card(B)
   Puisque B⊂ F∖ f(E) est équivalent à B∩ f(E)=∅ donc est équivalent à f(E)⊂ F∖ B donc le nombre de surjections de E dans F est :
   ∑_{B⊂ F}∑_{f∈A(E,F∖ B)} (−1)^Card(B)=
   ∑_{B⊂ F && Card(B)=k}(q−k)^p(−1)^k=∑_k=0^q comb(q,k)(q−k)^p(−1)^k
   En effet si Card(B)=k. Il y a (q−k)^p applications des E dans F∖ B et il y a comb(q,k) sous-ensemble de F qui contient k éléments.
   Donc :

   S(f)=

   q ∑ k=0

   (−1)kcomb(q,k)(q−k)p

Exercice 2 1a/ Montrer que pour tout j=1..k on a :
comb(p,j)*comb(p-j,k-j)=comb(p,k)*comb(k,j)
1b/ En déduire que :

2/ Soit S(n,p) le nombre de surjections d’un ensemble à n éléments sur un ensemble à p éléments.
En raisonnant, pour une application f de E dans F, sur le cardinal de f(E), établir :

3/ En déduire que :

4/ En utilisant φ(f) = {f⁻¹({y}) , y ∈ F } de l’ensemble des surjections de E dans F dans l’ensemble des partitions de E ayant p parties, déterminer le nombre de partitions d’un ensemble à n éléments en p parties (1 ≤ p ≤ n), noté Pi(n,p).

La solution 1a/ On développe les combinaisons ou on tape :
normal(comb(p,j)*comb(p-j,k-j)-comb(p,k)*comb(k,j))
On obtient :
0
1b/ On remplace les combinaisons à l’aide de 1a/ et on écrit le développement de (1−1)^k avec la formule du binôme et on obtient :
0=(1−1)^k=∑_j=0^k(−1)^jcomb(k,j) donc
comb(p,k)∑_j=0^k(−1)^jcomb(k,j)=∑_j=0^k(−1)^jcomb(p,k)comb(k,j)=∑_j=0^k(−1)^jcomb(p,j)*comb(p−j,k−j)
2/ Il y a pⁿ applications de E dans F et si f est une application de E dans F on note k le cardinal de f(E). Pour k fixé f est alors une surjection de E dans f(E) et il a S(n,k) surjections
il y a comb(p,1)*S(n,1) applications de E dans F qui sont telles que k=1
il y a comb(p,2)*S(n,2) applications qui sont telles que k=2
.... il y a comb(p,k)*S(n,k) applications qui sont telles que k=k
... il y a comb(p,p)*S(n,p) applications qui sont telles que k=p
d’où la formule pⁿ=sum( comb(p,k)*S(n,k),k=1..p)=S(n,p)+sum(comb(p,k)*S(n,k),k=1..p-1)
3/ On va faire une combinaison de lignes qui fera disparaitre les
S(n,k) pour k!=p en se servant de 1b/ :
sum((-1)ⁱcomb(p,i)comb(p-i,k-i),i=0..k)=0
Les coefficients de S(n,p-k) sont si la 1iere ligne est la ligne 0:
ligne 0 : comb(p,k),
ligne 1 : comb(p-1,k-1)
ligne 2 : comb(p-2,k-2)
...
ligne i : comb(p-i,k-i),
....
ligne k : 1
on multiplie donc
la ligne 0 par 1=(−1)⁰*comb(p,0)
la ligne 1 par -1*comb(p,1)
la ligne 2 par (−1)²*comb(p,2)
....
la ligne k par (−1)^kcomb(p,k)
...
la ligne p-1 par (−1)^p−1comb(p,p-1)
Puis on somme toutes les lignes et on obtient :
sum((-1)^kcomb(p,k)(p-k)ⁿ,k=0..p-1)=S(n,p) 4/ Chaque surjection de E dans F donne une partition de E ayant p parties. Mais une partition de E ayant p parties définit p! surjections donc le nombre de partitions de E ayant p éléments est S(n,p)/p!
Vérifions
S(n,2)=2ⁿ−2 et il y a 2ⁿ⁻¹−1 partitions de E ayant p parties.

6.7  Les nombres d’applications de E dans F