Image
Introduction au dénombrement et quelques applications

Combinatoire et dénombrements

On consultera avec grand profit le chapitre 1 de [GIO], très agréable et fournissant une bonne quantité de résultats originaux, complétant utilement les résultats très classiques suivants. On pourra aussi aller consulter le paragraphe [taillegrosmachins] pour les cardinaux d’ensembles infinis.

On se limitera ici à plus intuitif : cardinaux d’ensembles finis ([benfai1]), dénombrement de fonctions ([benfai2]), dénombrement d’arrangements ([benfai3]), et enfin les célèbres combinaisons ([benfai4] - on parle aussi de binôme de Newton).

Cardinaux d’ensembles finis

Avec \(A\) un ensemble fini, on a la Formule d’inclusion-exclusion; avec \(F_i \in {\cal A}=P(A)\), on a \[|\cup_{i \leq n} F_i|=\sum_{i \leq n} |F_i| - \sum_{1 \leq i<j\leq n} |F_i \cap F_j| + \sum_{1\leq i<j<k\leq n} |F_i \cap F_j \cap F_k| ... + (-1)^{n-1}|\cap_{1\leq i\leq n} F_i|.\]

Le nombre de parties à \(p\) éléments d’un ensemble à \(n\) éléments est \(C_n^p\) ; les coefficients du binomiaux sont définis en [comb].

Dénombrement de fonctions

On considère \(E\) et \(F\) deux ensembles finis, de cardinaux \(e\) et \(f\).

Ensemble des applications de \(E\) dans \(F\)

L’ensemble des applications de \(E\) dans \(F\), noté \(F^E\), a pour cardinal \(f^e\).

Ensemble des injections de \(E\) dans \(F\)

L’ensemble des injections de \(E\) dans \(F\) a pour cardinal \(A_f^e=\frac{f!}{(f-e)!}\) si \(f\geq e\); \(0\) sinon.

La preuve se fait facilement par récurrence. Voir [arr] pour les premières valeurs.

Ensemble des surjections (et bijections) de \(E\) dans \(F\)

En notant \(S_e^f\) le cardinal de l’ensemble des surjections de \(E\) dans \(F\) (dans le cas \(e\geq f\)) divisé par \(f!\) (c’est-à-dire, dans le cas de \(E\) et \(F\) totalement ordonnés, le nombre de surjections croissantes), on a les formules: \[S_e^1=S_e^e=1\] \[\forall (e,f)\ S_{e+1}^f=S_e^{f-1}+f.S_e^f\] On obtient ainsi les valeurs suivantes de \(S_e^f\): \[\begin{array}{c|ccccc} & f=1 & f=2 & f=3 & f=4 & f=5 \\ \hline e=1 & 1 & 0 & 0 & 0 & 0 \\ e=2 & 1 & 1 & 0 & 0 & 0 \\ e=3 & 1 & 3 & 1 & 0 & 0 \\ e=4 & 1 & 7 & 6 & 1 & 0 \\ e=5 & 1 & 15 & 25 & 10 & 1 \end{array}\] Le nombre de bijections de \(E\) vers \(F\) vaut \(e!\) si \(e=f\), \(0\) sinon.

Ensemble des applications croissantes de \(E\) vers \(F\)

\(E\) et \(F\) sont maintenant munis d’un ordre total. L’ensemble des applications croissantes de \(E\) dans \(F\) a le même cardinal que l’ensemble des applications strictement croissantes de \(E\) dans \([1,f+e-1]\); En effet, on a :

  • si \(u\) de \(\{1,2,3,...,e\}\) dans \(\{1,2,3,...,f\}\) est croissante alors \(x\mapsto v_u(x)=u(x)+x\) de \(\{1,2,3,...,e\}\) dans \(\{1,2,3,...,e+f\}\) est strictement croissante

  • \(u\mapsto v_u\) est bijective de l’ensemble des applications croissantes de \(E\) dans \(F\) vers l’ensemble des applications strictement croissantes de \(E\) dans \([1,f+e-1]\))

Il est alors facile de montrer que cet ensemble a pour cardinal \(C_{f+e-1}^e\).

Arrangements

(\(p\)-arrangement de \(E\)).
On appelle \(p\)-arrangement de \(E\) une application injective de \(\mathbb{N}_p\) dans \(E\). On note \(A_n^p\) le cardinal de l’ensemble des \(p\)-arrangements d’un ensemble à \(n\) éléments.

Au vu des résultats précédents, on peut dire que \(A_n^p=\frac{n!}{(n-p)!}\).

Les premières valeurs sont: \[\begin{array}{c|ccccc} & p=1 & p=2 & p=3 & p=4 & p=5 \\ \hline n=1 & 1 & 0 & 0 & 0 & 0 \\ n=2 & 2 & 2 & 0 & 0 & 0 \\ n=3 & 3 & 6 & 6 & 0 & 0 \\ n=4 & 4 & 12 & 24 & 24 & 0 \\ n=5 & 5 & 20 & 60 & 120 & 120 \newline \end{array}\]

Combinaisons

(\(p\)-combinaison de \(E\)).
On appelle \(p\)-combinaison de \(E\) tout sous-ensemble de \(E\) de cardinal \(p\). On note \(C_n^p\) ou \(\left(\begin{array}{c}n \\p \end{array}\right)\) le cardinal de l’ensemble des \(p\)-combinaisons de \(E\).

Remarque La notation \(C_n^p\) est d’usage en français mais on peut trouver aussi \(\left(\begin{array}{c}n \newlinep \end{array}\right)\) qui est la notation anglophone pour le cardinal des \(p\)-arrangements. Ces quantités sont usuellement appelées coefficients binonmiaux (ou coefficients du binôme) du fait de la formule de Newton, présentée plus bas.

On montre facilement, par récurrence, que \(C_n^p=\frac{n!}{p!(n-p)!}\).
Cette formule peut aussi se déduire sans récurrence en voyant qu’il y un nombre \(p!\) de \(p\)-arrangements qui donnent en fait \(p\)-combinaison et donc \(C_n^p=\frac1{p!}A_n^p=\frac{n!}{p!(n-p)!}\).
Elle peut aussi se déduire du fait que le groupe \(\sigma(E)\) des permutations de \(E=\{1,2,...,e\}\) agit transitivement sur l’ensemble des \(p\)-combinaisons de \(E\), que le stabilisateur \(S\) de \(F=\{1,2,...,f\}\subset E\) est le produit \(A\times B\) avec \(A\) et \(B\) respectivement les groupes de permutations de \(\{1,2,...,f\}\) et \(\{f+1,f+2,...,e\}\); \(S\) a donc pour cardinal \(S=f!(e-f)!\), d’où \(C_e^f=\frac{\sigma(E)}{|S|}=\frac{e!}{f!(e-f)!}\). Un argument similaire permet d’ailleurs de montrer la formule \(A_n^p=\frac{n!}{(n-p)!}\) sans récurrence.
En outre on a les formules suivantes: \[C_n^p=C_n^{n-p}.\] \[C_{n+1}^p=C_n^p+C_n^{p+1}.\] \[\mbox{ {\bf Formule de Newton}, valable dans un anneau: si $a.b=b.a$ et $n>0$, alors: }\] \[(a+b)^n=\sum_{k=0}^n C_n^k a^k.b^{n-k}.\] \[\sum_{k=0}^n C_n^k=2^n,\ \ \sum_{k=0}^n (-1)^k C_n^k=0.\] \[\mbox{(ces deux formules sont obtenues en spécialisant la formule de Newton)}\] \[\mbox {pour }1 \leq p \leq n, \mbox{ on a } p.C_n^p=n.C_{n-1}^{p-1}.\] \[\sum_{k=0}^n k.C_n^k=n.2^{n-1},\ \ \sum_{k=0}^n (C_n^k)^2=C_{2n}^n.\] Les premières valeurs de \(C_n^p\) sont : \[\begin{array}{c|ccccc} & p=0 & p=1 & p=2 & p=3 & p=4 \\ \hline n=0 & 1 & 0 & 0 & 0 & 0 \\ n=1 & 1 & 1 & 0 & 0 & 0 \\ n=2 & 1 & 2 & 1 & 0 & 0 \\ n=3 & 1 & 3 & 3 & 1 & 0 \\ n=4 & 1 & 4 & 6 & 4 & 1 \newline \end{array}\]

Quelques applications

On parlera ici de la dimension d’espaces de polynômes, de combinatoire, du binôme de Newton et de familles sommables infinies.

Dimension des polynômes homogènes

Pour \(n\geq 1\) et \(d\geq 0\), notons \(C_{n,d}\) la dim des polynômes de \(n\) indéterminées, homogènes de degré \(d\) (i.e. tous les termes sont de degré \(d\)). On a clairement \(\forall n\geq 1\), \(C_{n,0}=1\) (les polynômes homogènes de degré \(0\) sont les constantes) et \(\forall d\geq 0\), \(C_{1,d}=1\) (avec une seule indéterminée, l’espace des polynômes homogènes de degré \(d\) est \(Vect(X^d)\)). Par ailleurs, on peut montrer la relation \(\forall n\geq 2\), \(\forall d\geq 1\), \(C_{n,d}=C_{n-1,d}+C_{n,d-1}\). Cette formule s’obtient en partitionnant les monômes homogènes unitaires en deux catégories : ceux avec \(X_n\) de puissance nulle : ce sont des polynômes homogènes de degré \(d\) et à \(n-1\) indéterminées, il y en a \(C_{n-1,d}\) ; il reste les polynômes pour lesquels \(X_n\) a une puissance \(\geq 1\). En les factorisant par \(X_n\), on trouve des polynômes unitaires de degré \(d-1\), il y en a donc \(C_{n,d-1}\). Notre formule est ainsi prouvée.

Par ailleurs, la quantité \(C_{n+d-1}^d\) vérifie les mêmes “conditions au bord” (valeurs pour \(n=1\) et \(d=0\)) et la même relation de récurrence. On peut en déduire l’égalité de ces suites doubles par récurrence, et ainsi \[\forall n\geq 1,\ \forall d\geq 0,\quad C_{n,d}=C_{N+d-1,d}.\]

Une formule utile de combinatoire

Soit \(n\) un entier naturel. On a alors \[\sum_{k=0}^{n}C_n^k(-1)^{n-k}k^p=\left\{ \begin{array}{c c c} 0 & \mbox{si} & p<n \newline n! & \mbox{si} & p=n \end{array} \right. .\]

Apllication Ce résultat est utile pour la proposition [elebeau].

Comme \(C_n^k=C_n^{n-k}\), la somme présentée est le coefficient \(c_n\) du produit de Cauchy suivant :

\[f_p(x)=\sum_{m\geq 0} c_m x^m= \underbrace{\left(\sum_{k=0}^nC_n^k (-1)^kx^k\right)}_{(1-x)^n} \underbrace{\left(\sum_{l\geq 0}l^p x^l\right)}_{g_p(x)},\]

où toutes les séries entières présentées ont un rayon de convergence d’au moins 1. La famille de fonctions \((g_p)_{p\geq 0}\) est également définie par récurrence comme suit :

\[g_0(x)=\frac{1}{1-x}\mbox{ et }g_{p+1}(x)=xg_p'(x).\]

Pour tout entier naturel \(p\), il existe un polynôme \(h_p\) de degré \(p\) tel que \(g_p(x)=h_p(x)/(1-x)^{p+1}\).
begindivdemonstrationbegintext endtext Récurrence évidente.

Si \(p<n\), alors \(f_p(x)=h_p(x)(1-x)^{n-p-1}\) est un polynôme de degré \((n-1)\), si bien que \(c_n=0\).

Supposons maintenant que \(p=n\). On a alors :

\[f_n(x)=\frac{h_n(x)}{1-x}=h_n(x)(1+x+x^2+\ldots).\]

Comme \(h_n\) est de degré \(n\), le coefficient \(c_n\) vaut la somme des coefficients de \(h_n\). Autrement dit, \(c_n=h_n(1)\). On déduit de la relation \(g_{p+1}(x)=xg_p'(x)\) que

\[\frac{h_{p+1}(x)}{(1-x)^{p+2}}=\frac{xh_p'(x)}{(1-x)^{p+1}} +\frac{(p+1)xh_p(x)}{(1-x)^{p+2}}.\]

En multipliant par \((1-x)^{p+2}\) puis en prenant \(x=1\), il vient \(h_{p+1}(1)=(p+1)h_p(1)\). Comme \(h_0(1)=1\), on obtient \(h_p(1)=p!\) pour tout \(p\). En particulier, \(c_n=h_n(1)=n!\) et la proposition est démontrée.enddivdemonstration

Généralisation du binôme de Newton

Dans un anneau commutatif, pour \(n\) non nul, \[(x_1+...+x_p)^n=\sum_{i_1+i_2+...+i_p=n,i_j\geq 0} \left( \frac{n!}{i_1!i_2!...i_p!}\right)x_1^{i_1}x_2^{i_2}...x_p^{i_p}\]

Le coefficient \(\frac{n!}{i_1!i_2!...i_p!}\) pouvant se noter \(C_n^i\) avec \(i=(i_1,...,i_p)\).

Apllication Ces nombres apparaissent par exemple dans le calcul du nombre d’anagrammes d’un mot.

Un mot constitué de \(N\) lettres deux à deux différentes possède \(N!\) anagrammes.

Par exemple, le mot « matheux » possède \(7!=5040\) anagrammes.

Mais plus généralement, considérons un mot de \(N\) lettres est constitué de \(i_1\) fois une première lettre, de \(i_2\) fois une deuxième droite, ..., de \(i_p\) fois une \(p\)-ième lettre (les \(p\) lettres étant deux-à-deux différentes) avec donc \(N=\sum_{k=1}^pi_k\). Un tel mot possèdera \(\frac{N!}{i_1!i_2!...i_p!}=C_N^{(i_1,i_2,...,i_p)}\) anagrammes.

Par exemple, le mot « anticonstitutionnellement » possède \[\frac{25!}{3!3!2!5!2!5!}=7480328917501440000\] anagrammes (environ 7,5 milliards de milliards).

Voici un programme Maple capable de calculer le nombre d’anagrammes d’un mot.

Exemple Maple
\({\ }\ \ \ \ local\ occur,i,Nb;\)
\({\ }\ \ \ \ for\ i\ from\ "a"\ to\ "z"\ do\ occur[i]:=0;\ od;\)
\({\ }\ \ \ \ for\ i\ from\ 1\ to\ length(mot)\ do\ occur[mot[i]]:=occur[mot[i]]+1;\ od;\)
\({\ }\ \ \ \ Nb:=length(mot)!;\)
\({\ }\ \ \ \ for\ i\ from\ "a"\ to\ "z"\ do\ Nb:=Nb/occur[i]!;\ od;\)
\({\ }\ \ \ \ Nb;\)
\({\ }\ \ \ \ end;\)

\(>\ Nb\_Anagrammes("matheux");\) \(5040\)

\(>\ Nb\_Anagrammes("anticonstitutionnellement");\) \(7480328917501440000\)

Familles sommables infinies

(sommable de somme \(x\)).
Une famille \((x_i)_{i \in I}\) de nombres complexes est sommable de somme \(x\) si pour tout \(\epsilon\) il existe \(J \subset I\) finie telle que, pour tout \(K\) fini, \(J \subset K \subset I\) implique \(|x-\sum_{i \in K} x_i | \leq \epsilon\).
Si une famille \((x_i)\) de nombres réels est sommable, alors la famille de ses termes positifs est sommable, et la famille de ses termes négatifs est sommable.
Supposons que la famille des \((x_i)\) soit sommable, et supposons que la famille des \((max(x_i,0))\) ne le soit pas. Alors la somme des \((max(x_i,0))\) pour \(i\in J\) avec \(J\) fini peut être arbitrairement grande. Or la somme des \((x_i)\) pour \(i\) dans \(J'=\{ j \in J ; x_j>0\}\) est tout aussi grande, et peut donc être arbitrairement grande elle aussi. D’où le résultat pour la famille des réels positifs. Le raisonnement pour la famille négative est le même.
Toute famille sommable de nombres réels est de support dénombrable (i.e. seule une quantité au plus dénombrable de ces réels est non nulle). Il en va de même des familles de nombres complexes.
En vertu du lemme précédent, on se contente de démontrer ce résultat pour une famille de nombres réels positifs. Le résultat dans le cas général s’obtient par le lemme précédent. Il existe un nombre fini de réels plus grands que \(1/n\), pour tout \(n\). En notant \(A_n\) la famille des réels \(>1/n\), on voit que la réunion des \(A_n\) est le support de la famille; une réunion dénombrable d’ensembles finis étant dénombrable, la famille est dénombrable.

Bibliographie

  • [GIO] W. Giorgi, Thèmes mathématiques pour l’agrégation, Masson, 1998.


Barre utilisateur

[ID: 45] [Date de publication: 25 avril 2021 23:09] [Catégorie(s): Le cours d'agrégation ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 5 ] [Auteur(s): Christophe Antonini Olivier Teytaud Pierre Borgnat Annie Chateau Edouard Lebeau ]




Commentaires sur le cours

Documents à télécharger

Combinatoire et dénombrements
Télécharger Télécharger avec les commentaires

L'article complet