Dénombrement

Nous allons mettre au point quelques méthodes pour compter des objets : éléments d'un ensemble défini d'une certaine façon.
Mise en garde : il est bon, pour profiter intégralement de ce cours, d'avoir vu au moins un cours élémentaire sur les Ensembles puis les Relations, et souhaitable d'être initié à la Logique élémentaire (Ce n'est pas bien long).

[modifier ( modifier-402-section-1.cours)]Mise en place d'une base essentielle : les entiers naturels

On considérera dans cette leçon des ensembles finis, c'est-à-dire dont on peut épuiser les élémens en les comptant.
On les notera (aucun élément), (un élément), (deux éléments),...

[modifier ( modifier-402-section-8.cours)]Réunion et intersection

Soient deux ensembles quelconques. Alors on a dans le cas général :

Preuve
On peut écrire
, ce qui définit comme réunion de deux ensembles disjoints : et .
En effet, si , soit il appartient à , soit il appartient à sans appartenir à , c'est-à-dire .
On peut donc écrire

D'autre part, on peut écrire
, où et sont disjoints (l'un contient des élément qui ne sont pas dans , l'autre des éléments qui y sont)
On a donc

En tout, en éliminant dans les deux égalités trouvées, on obtient :

Exemple simple
Dans une classe de 30 élèves, il y a 14 anglicistes, 8 germanistes, et deux élèves étudient à la fois l'anglais et l'allemand.
Combien d'élèves étudient au moins l'une de ces deux langues ? Combien n'étudient aucune de ces deux langues ?
Solution : Soit la classe, les ensembles des anglicistes et de germanistes.
Le nombre d'élèves étudiant au moins l'une de ces deux langues est
soit 14 + 8 - 2 = 20.
Le nombre d'élèves n'étudiant aucune de ces deux langues est
Exercice
Montrer que pour trois ensembles quelconques, on a

[modifier ( modifier-402-section-9.cours)]Applications d'un ensemble fini vers un autre

Soit , où sont des ensembles finis.
On note l'ensemble des applications de vers . (lire : puissance )
Le nombre d'applications de vers est :

En effet,
Supposons que .
Appelons les éléments de  :
Définir une application , c'est tout simplement choisir dans , dans cet ordre.
Ce qui revient à définir un p-uplet
Comme , .
Ce qui veut dire qu'il y a applications différentes de dans .
Exemple
J'ai 10 chemises et une commode à 4 tiroirs. Combien ai-je de façons possibles de ranger mes chemises dans cette commode ?
Solution :
Chaque chemise va dans un et un seul tiroir.
Un rangement est donc une application de l'ensemble des chemises vers l'ensemble des tiroirs. Il y a donc façons de ranger les dix chemises dans quatre tiroirs.
(attention, aucune chemise ne reste à l'extérieur de la commode à l'issue d'un rangement !)

[modifier ( modifier-402-section-10.cours)]Nombre d'injections d'un ensemble fini dans un autre

Soient deux ensembles, avec
Le nombre d'injections de dans est le produit de facteurs

On le note

et on l'appelle souvent nombre d'arrangements de objets pris dans un ensemble de objets.
Définition
Si , on pose (factorielle )
On posera aussi et
Cette définition garantit qu'on aura toujours
Alors, on peut exprimer autrement

Preuve
Soit
Pour définir une injection , il suffit de définir les éléments de ,
Pour définir il y a choix possibles.
A chacun de ces choix, on peut faire correspondre choix possibles pour , puisque l'on doit avoir .
Le principe de multiplication nous indique qu'il y a donc manières de définir
En continuant jusqu'au bout, on trouve que le nombre de manières de définir est , soit (vérifier que cela fait bien facteurs).
Exemples
1) 0≠1≠1 ; 2! = 2 ; 3! = 6 ; 4! = 24 ; 5! = 120 ...
2) (se rappeler : "4 facteurs")
ou

3) Quel est le nombre de jeux possibles au tiercé lorsqu'il y a 23 chevaux au départ (on n'admet pas d'ex aequo) ?
Un "jeu" possible au tiercé est la donnée d'un premier cheval, d'un deuxième et d'un troisième dans cet ordre.
Cela revient bien à définir une injection de dans l'ensemble des chevaux.
En effet, chaque rang d'arrivée, 1,2 ou 3 correspond à un et un seul cheval, et deux rangs différents correspondent à deux chevaux différents (donc injection)...
Le nombre de jeux possibles, ou d'arrivées a priori possibles, est donc

[modifier ( modifier-402-section-11.cours)]Nombre de bijections d'un ensemble fini dans un autre (de même cardinal)

Soient deux ensembles finis tels que
Alors toutes les injections de dans sont automatiquement surjectives. En effet, les éléments de ont images distinctes dans , ce qui remplit totalement .
Le nombre de bijections de dans n'est donc rien d'autre que le produit des entiers
.
Le cas où ne change rien à ce résultat.
On retiendra :
Le nombre de bijections de dans un ensemble de même cardinal est
On dit aussi que le nombre de permutations de objets est .
Exemples
1) On organise un banquet avec 20 convives, et 20 places qui leur sont réservées.
Combien y a-t-il de manières de placer les convives ?
Solution : un "placement" des convives est une bijection de (ensemble des convives) dans (ensemble des places).
Il y a donc 20! manières de les placer de façons différentes, ce qui donne le nombre astronomique de 2 432 902 008 176 640 000 (plus de 2 milliards et milliards !)
2) Même question, mais on n'a que 9 convives et une table ronde dans une salle ronde ou presque...
Cette fois, si l'on faisait tourner tous les convives d'une place sur leur droite, par exemple, ils ne s'apercevraient pas de la différence, parce que la seule chose qui aurait pu compter est leur disposition par rapport aux autres convives.
On peut donc placer, disons le premier convive arrivé, n'importe où, puis placer les 8 autres par rapport à lui.
On a donc une bijection d'un ensemble de 8 personnes sur un ensemble de 8 places, donc 8! possibilités, soit 40 320.
3) Même question, mais on veut que M. X soit à côté de Mlle Y.
Solution : on place M. X n'importe où, puis on place Mlle Y à côté de lui (2 possibilités), puis on place les 7 autres convives. D'après le principe de multiplication, cela fait possibilités, soit 10 080.
4) Même question, mais on veut que M. X soit à côté de Mlle Y, et Mme Z à côté d'aucun d'eux !
Solution : On place M. X, puis Mlle Y à côté de lui, puis Mme Z dans les 9-4=5 places "possibles", et enfin les 6 autres convives dans les 6 places restantes. Cela fait possibilités.

[modifier ( modifier-402-section-12.cours)]Nombre de parties à p éléments dans un ensemble à n éléments

Si , le nombre de parties à éléments dans un ensemble à éléments est le quotient d'un produit de facteurs par un autre produit de facteurs :

soit

ou

Au lieu de , certains notent
On appelle aussi ce nombre "nombre de combinaisons de p objets pris dans un ensemble de n éléments".
Preuve
Comment définir une partie à éléments dans un ensemble à éléments ?
On peut considérer une injection de dans , parce que cette injection définit éléments de , mais dans un certain ordre : un 1er, un 2e, ..., un p-ième.
Le nombre d'injections est donc trop grand pour dénombrer les parties à éléments.
Car une même partie de correspondra à injections différentes, obtenues en changeant de toutes les manières possibles l'ordre des images de 1,2,...,p.
Donc le nombre de parties à éléments n'est autre que .
Exemples
1. On appelle "main" un ensemble de 6 cartes prises dans un jeu de 32 cartes.
Le nombre de mains est

2. Quel est le nombre de "mains" contenant un roi, deux valets et 3 cartes qui ne sont pas des figures (figure= roi, dame ou valet) ?
On utilise le principe de multiplication : nombre de manières d'obtenir un roi : 4 ;
nombre de manières d'obtenir 2 valets sur les 4 existants :  ;
nombre de manières de choisir 3 cartes qui ne sont pas des figures : .
Donc le nombre cherché est .

[modifier ( modifier-402-section-13.cours)]Nombre de parties d'un ensemble fini

On peut raisonner par récurrence. Le nombre de parties de l'ensemble vide est 1 : la seule partie de l'ensemble vide est l'ensemble vide lui-même.
Maintenant, si je considère un ensemble contenant éléments, et si j'appelle le nombre de ses parties, soit l'ensemble à éléments obtenu en adjoignant à un élément ,
les parties de sont de deux sortes : soit elles contiennent , soit elles ne le contiennent pas.
Si elles ne le contiennent pas, ce ne sont autres que les parties de , et il y en a .
Si elles le contiennent, elles sont toutes de forme , avec , donc il y en a aussi .
En tout, il y a parties dans
On peut écrire




et il est aisé de prouver par récurrence que .

[modifier ( modifier-402-section-18.cours)]Formule du multinôme de Newton

Elle généralise la formule du binôme de Newton.
Pour ,
(avec )
La preuve est une récurrence sur .
On sait que la formule est vraie pour et tout , car elle n'est alors autre que la formule du binôme de Newton :

Supposons que cette formule est vraie pour donné et tout  ; alors

Par hypothèse, ceci vaut

qui n'est autre que

On peut renommer , et la formule est prouvée.
Exemples simples :
1) Développement de  :

En effet,

2) Coefficient de dans le développement de  :
Le terme en question est

Le coefficient de est donc