Dénombrement (Probabilités) sur [[1, n]]
Théorie des ensembles finis : dénombrer un ensemble fini
Ensemble fini : E est fini s'il est vide ou s'il existe n>=1 et une bijection de l'ensemble [[1, n]] dans E
L'entier n est appelé cardinal
Si E et F deux ens finis de même cardinal, il existe une bijection de E sur F
Réciproquement : si E ens fini et F ens fini en bijection avec E, E aussi fini et Card(E)=Card(F)
Les calculs de dénombrement faits sur un ens fini non vide E ne dépendront pas de la nature de ses éléments, mais de son cardinal n
ensemble dont on peut numéroter les éléments de 1 à n
dès que n>=2, la bijection f n'est plus finie
Toute partie A d'un ensemble fini E est finie, et card A <= card E
Card A = Card E ssi A=E
Outils du dénombrement
Les erreurs à ne pas commettre
oublier certains éléments ou en compter qui n'appartiennent pas à l'ensemble
confondre des éléments distincts
compter plusieurs fois le même élément
Principe de la somme
Principe du produit
Arrangements
Permutations
Applications
Combinaisons
Principe de la somme
Cardinal d'une réunion disjointe
Card(A∪B)=Card(A)+Card(B) ; généralisation possible à Ai
E fini, Card(E)=n : Card(Abarre) = n - Card(A)
Formule de Poincaré (ou formule du crible)
Card(A ∪ B) = Card(A) + Card(B) − Card(A ∩ B)
voir poly pour l'égalité générale
Lorsque les ensembles ne sont pas 2à2 disjoints, leur réunion s'obtient par une formule un peu plus compliquée (Poincaré)
permet d'écrire l'ensemble E comme union de sous-ensembles 2à2 disjoints dont on sait déterminer les cardinaux, Card(E) est alors la somme des cardinaux des sous-ensembles mis en évidence
Principe du produit
Lemme des bergers : E ens tq E = union des Ai 2à2 disjoints et de même cardinal p : card(E)=np
Cardinal du produit cartésien d'ensembles finis
E et F finis, Card(ExF)=Card(E)xCard(F)
Card(E^k)=n^k
Card(E1 × . . . × Ek) = CardE1 × . . . × CardEk
Principe multiplicatif : Soit E non vide dont chaque élément peut se définir par 2 étapes (la 1e offrant n possibilités, la 2e p), CardE=np
Généralisons : k étapes alors CardE=n1n2...nk
Le nombre de possibilités ne dépendre que du numéro de l'étape, et non du résultat précédent
Arrangements : E est un ensemble fini non vide de cardinal n et p >=1
p-arrangement avec répétition de e tout élément de E^p (tout p-uplet, p-liste) d'éléments de E suite ordonnée d'éléments de E dans laquelle le même élément peut apparaître pls fois
p-arrangement de E tout élément de E^p dont les composantes sont 2à2 distinctes suite ordonnée d'élém de E tous différents
Dénombrement des p-arrangements
nombre de p-arrangements avec rép de E : n^p
nombre de p-arrangement de E :
Permutations
permutation d'un ensemble E de cardinal n : tout n-arrangement de E
Un ensemble de cardinal n admet n! permutations
Applications entre ensembles finis
Nombre d'applications d'un ens de card n dans un ens de card p : p^n (ne pas confondre les espaces de départ et d'arrivée)
Nombre d'injections d'un ens de card n dans un ens de card p : 
(p et n inversés)
Applications entre ens de même cardinal : équivalence entre f surjective f bijective et f injective
Nombre de bijections entre 2 ens finis de même cardinal : n!
Combinaisons : Soit E ens fini et P(E) l'ens de ses parties, on va montrer que l'ensemble P(E) est fini
Fonction indicatrice d'une partie : 1 si x est dans l'ensemble, 0 si x n'y est pas
La fonction caractéristique est bijective de P(E) dans F(E,{0,1})
Cardinal de l'ensemble des parties : si card E = n, alors card (P(E)) = 2^n
p-combinaison de E : toute partie de E ayant p éléments; correspond à un sous-ensemble de P(E)
⚠ différence entre les p-arrangements et p-combinaisons : les 2 sont des p éléments distincts de E, mais arrangement = ordre, pas combinaisons
Nombre de parties à p éléments d'un ensemble à n éléments : 
Triangle de Pascal
Binôme de Newton
Lorsque le dénombrement concerne des objets totalement ou partiellement indiscernables
Combinaison avec répétition : p-combinaison avec répétition de E tout groupement non ordonné de p éléments de E non nécessairement distincts : pas une partie de E
Nombre de p-combi avec rép : npmbre de n-uplet d'entiers tq leur somme = p
Calcul explicite du nombre de p-combinaisons avec rép : 
Permutation avec répétition : Soit E = {x1...xn}, p-permutation avec répétitions de E tout p-uplet k1,...,kn d'élém de E dans lequel l'élément xi apparaît exact ki fois
Nombre de permutations avec rép : 