[SON] Bonjour. Bienvenue dans le cours d'aléatoire. Ceci est le cours 1. Nous faisons une séance supplémentaire de rappel de combinatoire. Donc, d'abord dans ces rappels de combinatoire, nous commençons par des résultats de base. Nous allons décrire diverses manières de choisir k objets parmi n, et calculer pour chaque manière, le nombre de choix distincts possibles. Donc première possibilité. Avec répétition et avec ordre. On s'intéresse au nombre de choix possibles de k objets parmi n, en autorisant les répétitions, prendre plusieurs fois le même objet, et en tenant compte de l'ordre de choix. L'ensemble des choix possibles correspond à l'ensemble des applications ou des suites de 1, 2, 3, jusqu'à k, dans 1 jusqu'à n, qu'on peut noter ensemble {1, ..., n} puissance {1, ..., k}, ou en considérant l'ensemble des suites, {1, ..., n} puissance k. L'important, c'est qu'on peut compter ce nombre de fois facilement. Le nombre de choix, il y a n choix pour le premier terme, n choix pour le second, et ainsi de suite, jusqu'à n choix pour le k-ième terme. Donc, le nombre de choix possibles, c'est n * n * etc * n, k fois, et donc c'est n puissance k. Par convention, on dit que (n puissance 0) = 1. Deuxième possibilité. Nous pouvons faire des choix sans répétition et avec ordre. On s'intéresse donc au nombre de choix possibles de k objets parmi n, en n'autorisant pas les répétitions, et en tenant compte de l'ordre de choix. Donc, l'ensemble des choix correspond à l'ensemble des injections. On dit parfois des arrangements de l'ensemble 1 jusqu'à k, dans l'ensemble de 1 jusqu'à n. Donc, les applications de {{1, ..., k} dans {1, ..., n}, injectives}. Le nombre de choix possibles se calcule aussi. Il y a n choix pour le premier terme, (n- 1) choix pour le second, puisqu'on en a déjà pris un et qu'on n'autorise pas les répétitions. Et ainsi de suite, jusqu'à (n- k + 1) pour le k-ième. Il y a k termes dans ce produit. Ceci va être noté (n) entre parenthèses avec un k en bas, et par convention, ((n) 0) = 1. Attention, cette notation n'est pas universelle. Une notation courante en France, c'est A n k, le nombre de k arrangements parmi n. Dans le cas particulier où k = n, on parle de permutation ou de bijection. Le nombre de ces permutations et de ces bijections est n * (n- 1) * etc * jusqu'à 1, avec n termes. C'est le nombre que l'on appelle factorielle n et que l'on note (n !), avec un point d'exclamation. Par convention, (0 !) = 1. Si k est inférieur ou égal à n, alors (n) indice k, qui par définition, c'est n * (n- 1) *... * (n- k + 1), avec k termes, peut s'écrire comme étant (n !) / ((n- k) !). Une troisième possibilité, c'est de faire des choix sans répétition et sans ordre. On s'intéresse au nombre de choix de k objets parmi n, en n'autorisant pas les répétitions et en ne tenant pas compte de l'ordre de choix. L'ensemble des choix possibles correspond à l'ensemble des sous-ensembles, on dit parfois des combinaisons de k éléments parmi n, donc l'ensemble des sous-ensembles qui se notent {i 1, ..., i k} inclus dans {1, ..., n}, les liens jusqu'à i k étant distincts. Le nombre de choix possible s'obtient en remarquant que chaque sous-ensemble de cette forme correspond à exactement (k !) arrangements. Les (k !) arrangements qui correspondent chacun à une des (k !) permutations des éléments du sous-ensemble. De ce fait, le nombre de choix possibles, donc le nombre de sous-ensembles à k éléments parmi n, vaut donc le nombre d'arrangement ((n) indice k) / (k !), qui peut s'écrire à l'aide des factorielles comme étant (n !) / ((k !) * (n- k) !), et qu'on notera avec une grande parenthèse, avec un n en haut et un k en bas. Le nombre, la notation standard. Par définition, le nombre de choix de 0 élément parmi n, c'est 1. Il faut évidemment utiliser la première forme, le nombre d'arrangement ((n) indice k) / (k !), pour faire des calculs. Ces nombres s'appellent des coefficients binomiaux. Parfois on les note C n k. Notons que le nombre binomial (k choix parmi n) est égal au nombre binomial (n- k choix parmi n). Cette symétrie s'explique d'un point de vue combinatoire, et non seulement calculatoire. A tout sous-ensemble à k éléments parmi n, correspond de façon unique, et donc bijective, son complémentaire, qui est un sous-ensemble à n- k éléments parmi n. Donc, nous avons cette formule de symétrie. Le nombre de choix de k éléments parmi n est égal au nombre de choix de (n- k) éléments parmi n. Enfin, dans ce cas, on est en train de parler de sous-ensemble. Une formule connue, qui s'appelle la formule du binôme, dite parfois de Newton, même si elle était connue des mathématiciens, en particulier indiens, bien avant Newton. Les coefficients binomiaux doivent leur nom au fait qu'ils interviennent dans le développement du binôme ((a + b) puissance n) = la somme de k = 0 jusqu'à n du (coefficient binomial choix de k parmi n) * (a puissance k) * (b puissance (n- k)). C'est valable pour, par exemple, tous les a et b complexes, et plus généralement, pour des éléments d'un anneau commutatif, et une distributivité du produit par l'addition, et une commutativité du produit. De cette formule du binôme, on peut déduire quelques formules remarquables pour les coefficients binomiaux. Les plus simples sont les suivantes. La somme de k = 0 jusqu'à n des coefficients binomiaux choix de k parmi n. Par la formule du binôme, cela s'interprète comme (1 + 1) puissance n et donc 2 puissance n. La somme alternée somme de k = 0 jusqu'à n des (- 1) puissance k * (coefficient binomial de k choix parmi n), cela peut s'écrire par la formule du binôme, comme étant (- 1 + 1) puissance n, et donc cela vaut 0. Et enfin, une formule. La somme de k = 0 jusqu'à n du (coefficient binomial (choix de k parmi n)) * (a k) * (1- a) à la puissance (n- k), peut s'écrire comme étant (a + 1- a) puissance n, et donc cela vaut 1. Après avoir rappelé les résultats de base, nous allons poursuivre par quelques compléments. Un premier complément. On peut parler de sous-ensembles avec répétition. On s'intéresse au nombre de sous-ensembles avec répétition de k éléments parmi n. C'est un sujet assez délicat, même si leur combinatoire est relativement simple. C'est pourquoi il est rarement abordé. En effet, les sous-ensembles avec répétition peuvent décrire un certain nombre d'issues d'expériences aléatoires, mais la probabilité uniforme sur leur ensemble ne correspond en général pas à la réalité de ces expériences. et amène des calculs faux. Nous allons montrer cela sur un exemple. Considérons deux lancers successifs d'une pièce équilibrée. On pourrait considérer en tant qu'issues les sous-ensembles avec répétition deux piles, deux faces, et un de chaque. Or, l'issue un de chaque correspond à deux issues de l'expérience aléatoire réelle, l'issue pile puis face, et l'issue face puis pile. Donc, cette issue globale un de chaque, qui se décompose en deux issues, a probabilité (1 / 4) + (1 / 4) = 1 / 2, et non pas 1 / 3, qui serait le résultat, si on mettait la probabilité uniforme sur les sous-ensembles avec répétition deux piles, deux faces, et un de chaque. Aussi, les événements deux piles, et les événements deux faces ont une probabilité 1 / 4, et non pas 1 / 3, comme si on avait mis on avait mis la probabilité uniforme sur les sous-ensembles avec répétition. Cet exemple montre bien l'importance de choisir un bon ensemble grand oméga, sur lequel on puisse mettre une probabilité uniforme pour représenter une expérience aléatoire. Cependant, de façon assez étonnante, la probabilité uniforme sur les sous-ensembles avec répétition est à la base de ce qu'on appelle la statistique de Bose-Einstein, qui décrit certains phénomènes de la mécanique quantique. Elle concerne des particules indistinguables, qui peuvent occuper les mêmes micro-états. Un exercice porte sur ces sujets. Les sous-ensembles avec répétition, et la statistique de Bose-Einstein. Deuxième complément. Coefficients et formule du multinôme. On s'intéresse au nombre de façons de partitionner un ensemble à n éléments en (p supérieur ou égal 2) sous-ensembles à (k 1), etc, jusqu'à (k p) éléments, avec la contrainte ((k 1) +... + (k p)) = n. Les nombres binomiaux, on cherchait des sous-ensembles à k éléments parmi n, et on avait remarqué qu'en fait cela partitionnait l'ensemble en un sous-ensemble à k éléments, et son complémentaire à (n- k) éléments. C'est le (k p) = 2 ici, donc nous avons généralisé ce cas. D'un point de vue un peu plus, mettons probabiliste, c'est le nombre de façons de répartir n boules numérotées, dans p urnes numérotées de façon à avoir (k 1) boules dans la première urne, etc, jusqu'à (k p) boules dans la p-ième. Bon, une façon de procéder pour effectuer cette partition, c'est de prendre un sous-ensemble de k 1 éléments parmi n, puis un sous-ensemble à (k 2) éléments parmi les (n- k 1) éléments restants. Et ainsi de suite, jusqu'à un sous-ensemble à (k (p- 1)) éléments parmi les n- (k 1) -...- (k (p- 2)) restants. Notons que ceci détermine un dernier sous-ensemble à (k p) éléments, puisque (k 1) +... + (k p) vaut n. Donc, ce nombre vaut le produit des coefficients binomiaux. (Choix de k 1 parmi n) * (choix de k 2 parmi (n- (k 1))) *... * (choix de (k (p- 1)) parmi n- (k 1) -...- (k (p- 2))). Nous écrivons ces nombres binomiaux en fonction des factorielles. Donc, le premier nombre binomial, c'est (n !) / (((k 1) !) * ((n- k 1) !)). Le deuxième nombre, c'est donc ((n- k 1) !) / (((k 2) !) * ((n- k 1- k 2) !)). Et ainsi de suite, le dernier nombre c'est ((n- k 1 -...- (k (p- 2))) !) / (((k (p- 1)) !) * ((k p) !)), qui est n- k 1 -...- (k (p- 2)). Donc, nous voyons que beaucoup de termes se simplifient. Tous les termes en n- k 1, etc, jusqu'à n- k 1, jusqu'a (- k (p- 2)) se simplifient. Et on retrouve (n !) / ((k 1) !) * ((k 2) !) *... * ((k p) !). Donc, on a calculé le nombre. Donc, on peut directement obtenir ce nombre (n !) / ((k 1) !) *... * ((k p) !), que l'on note souvent d'une façon proche du coefficient binomial, comme étant (n sur k 1, ..., k p). Donc, on peut obtenir directement ce nombre, en remarquant qu'à partir d'une partition donnée de l'ensemble, par exemple celle qu'il y a écrite sur le slide, on a numéroté les éléments de 1 jusqu'à n, et on a choisi comme premier sous-ensemble de la partition les k 1 premiers, comme deuxième sous-ensemble de la partition, les k 2 suivants, etc, et comme p-ième sous-ensemble de la partition, les k p derniers éléments. Donc, à partir d'une partition, on peut considérer toutes les permutations des n éléments, donc il y a (n !) permutations, et on peut remarquer que pour chacune de ces positions, de ces répartitions, pardon, nous avons (((k 1) !) *... * ((k p) !)) permutations particulières qui conservent les éléments (k 1) qui sont ensembles. Donc, nous avons ((k 1) !) *... * ((k p) !) fois chaque partition possible. Donc, je répète rapidement ce que j'ai dit. Si on regarde toutes les (n !) permutations des éléments, on obtient ((k 1) !) *... * ((k p) !) fois chaque partition possible. Donc, pour compter le nombre, il faut diviser (n !) par ce nombre ((k 1) !) multiplié jusqu'à factorielle k p. Ces nombres s'appellent les coefficients multinomiaux, car ils interviennent dans le développement du multinôme (a 1 +... + a p) puissance n = la somme pour k 1, ..., jusqu'à k p positif ou nul, tel que (k 1) +... + (k p) = n, du (coefficient multinomial de n en haut, k 1, jusqu'à k p en bas entre parenthèses, fois (a 1) puissance (k 1), jusqu'à (a p) puissance (k p). De cette formule, on peut déduire quelques relations remarquables sur les coefficients multinomiaux. La plus simple, c'est que la somme de tous ces coefficients multinomiaux revient à prendre ((1 +... + 1) avec p termes) puissance n, et donc c'est p puissance n. Donc, ceci finit la séance supplémentaire, ce rappel de combinatoire.
