Exemple : \( a=3, b=2 \)
Il est clair qu'un chemin optimal consiste en exactement \( a + b \) déplacements (d'une unité de longueur chacun, celle d'un côté de pâté de maison) dont \( a \) déplacements "horizontaux" et \( b \) déplacements "verticaux". Cependant, le piéton est libre quant à l'ordre dans lequel il effectue ces déplacements. Schématiquement, on peut lister :
D'ailleurs, si on note 0 le fait de choisir un déplacement horizontal, 1 celui de choisir un déplacement vertical, alors on peut étiqueter ces schémas par les mots binaires comportant \( a \) zéros et \( b \) uns, comme suit :
00011 00101 00110 01001 01010 01100 10001 10010 10100 11000
En termes mathématiques, il y a "\( a \) parmi \( (a+b) \)" chemins possibles -- ou ce qui revient au même, "\( b \) parmi \( (a+b) \)" chemins possibles --, ce qui en notation de coefficients binômiaux s'écrit :
\[ \bbox[white, border: 2px solid black]{ \binom{a+b}{a} = \frac{(a+b)!}{a! b!} = \binom{a+b}{b} } \]Dans notre exemple :
\[ \binom{3+2}{3} = \binom{3+2}{2} = \frac{5!}{3! 2!} = 10\]Nota Bene : usuellement les coefficients binômiaux sont définis comme suit : "k parmi n", noté
\[ \binom{n}{k} \]est le nombre de sous-ensembles à \( k \) éléments d'un ensemble à \( n \) éléments. Et il vaut :
\[ \binom{n}{k} = \frac{n!}{k! (n-k)!} \]Nous parlons donc bien de la même chose, seules diffèrent légèrement les variables utilisées ; en gros pour fixer les idées :
\[ n = a + b \] \[ k = a \] \[ n-k = b \]Selon moi la notation usuelle est un [petit] frein à la généralisation, car le fait que \( k \) et \( n-k \) jouent le même rôle au fond, est [légèrement] masqué. Pour se convaincre dans cette notation qu'ils jouent le même rôle, d'une certaine manière, il faut garder à l'esprit que :
\[ n-(n-k) = k \]Tandis qu'avec une notation en \( a \) et \( b \), la symétrie des rôles de \( a \) et de \( b \) est limpide. En contrepartie, on complique l'écriture de \( n \).
Coefficients trinômiaux
Soit une ville extra-terrestre en 3 dimensions dans laquelle le réseau routier est constitué de 3 familles de droites :
- les droites parallèles à l'axe des \( x \) et qui ont pour équations : \( y = j, z = k \), avec \( j \) et \( k \) des entiers relatifs ;
- les droites parallèles à l'axe des \( y \) et qui ont pour équations : \( x = i, z = k \), avec \( i \) et \( k \) des entiers relatifs ;
- les droites parallèles à l'axe des \( z \) et qui ont pour équations : \( x = i, y = j \), avec \( i \) et \( j \) des entiers relatifs.
Le reste de l'espace est considéré être un obstacle infranchissable (soit dit en passant : ainsi, l'obstacle en 3D est connexe, ce qu'il n'était pas en 2D). Un piéton extra-terrestre, situé en \( (0,0,0) \), souhaite se rendre en \( (a, b, c) \). Combien a-t-il de chemins optimaux à sa disposition ?
Exemple : \( a=1, b=3, c=2 \)
La réponse n'est pas tellement différente de celle en 2D ! Il est clair qu'un chemin optimal consiste en exactement \( a + b + c\) déplacements dont \( a \) déplacements parallèlement à l'axe des \( x \), \( b \) déplacements parallèlement à l'axe des \( y \) et \( c \) déplacements parallèlement à l'axe des \( z \). Le piéton est libre quant à l'ordre dans lequel il effectue ces déplacements.
Si on note 0 le fait de choisir un déplacement parallèlement à l'axe des \( x \), 1 celui de choisir un déplacement parallèlement à l'axe des \( y \), et enfin 2 celui de choisir un déplacement parallèlement à l'axe des \( z \), alors on peut étiqueter les différentes possibilités par des mots ternaires comportant \( a \) zéros, \( b \) uns et \( c \) deux, comme suit :
011122 011212 011221 012112 012121 012211 021112 021121 021211 022111 101122 ... ... 221110
Le nombre de possibilité est un coefficient trinômial, que l'on note :
\[ \binom{a+b+c}{a, b, c} \]et dont on peut calculer la valeur comme suit :
\[ \bbox[white, border: 2px solid black]{ \binom{a+b+c}{a, b, c} = \frac{(a+b+c)!}{a!b!c!} } \]On remarque immédiatement la ressemblance avec la formule du coefficient binômial !
Comment démontre-t-on cette formule ? Le raisonnement est le suivant :
- par la pensée (avant de bouger), on numérote les déplacements qu'on va effectuer. On sait qu'il y en aura exactement \( (a+b+c) \) ; on peut les numéroter de \( 1 \) à \( (a+b+c) \) par exemple ;
- par la pensée toujours, on choisit \( a \) numéros dans l'ensemble des nombres de \( 1 \) à \( (a + b + c) \) : on décidera d'aller parallèlement à l'axe des \( x \) lors des déplacements portant ces numéros ;
- combien de possibilités a-t-on pour choisir \( a \) numéros parmi \( (a + b + c) \) ? La réponse est donnée par le coefficient binômial,
- pour chacune de ces possibilités [ayant porté sur l'axe des \( x \)], reste encore à fixer l'ordre dans lequel on ira soit parallèlement à l'axe des \( y \), soit parallèlement à l'axe des \( z \) ;
- il reste \( b + c \) déplacements à ordonner. On en choisit (par la pensée toujours) \( b \) : on décidera d'aller parallèlement à l'axe des \( y \) lors des déplacements portant ces numéros ;
- combien de possibilités a-t-on pour choisir \( b \) numéros parmi \( (b + c) \) ? La réponse est donnée par le coefficient binômial,
- (là c'est du zèle :) ) pour chacune de ces possibilités [ayant porté sur les axes des \( x \) et des \( y \)], reste-t-il encore à fixer un quelconque ordre ? ;
- pas vraiment, on s'en doute : les \( c \) numéros de déplacement restants sont bien évidemment destinés à se concrétiser parallèlement à l'axe des \( z \).
- donc pas le choix, mais pour la beauté, on peut dire que le nombre de choix possibles est de \( 1 \) car égal au coefficient binômial
- comment combine-t-on toutes ces possibilités donnant lieu à des sous-possibilités et à des sous-sous-possibilités ? Par un produit.
- la réponse est donc donnée par :
- maintenant il est temps d'appliquer la formule
- on obtient :
- et des simplifications s'opèrent pour finalement obtenir :
Dans notre exemple :
\[ \binom{1+3+2}{1, 3, 2} = \frac{6!}{1! 3! 2!} = 60 \]Généralisation aux coefficients multinômiaux
Maintenant, plaçons-nous en dimension \( n \). Il n'y a pas de difficulté à généraliser :
\[ \bbox[white, border: 2px solid black]{ \binom{a_1 + a_2 + \dots + a_n}{a_1, a_2, \dots, a_n} = \frac{(a_1 + a_2 + \dots + a_n)!}{a_1! a_2! \dots a_n!} } \]Du coup, pour \( n = 2 \), le coefficient binômial peut aussi être noté comme suit :
\[ \binom{n}{k} = \binom{n}{k, n-k} \]LR, 13/04/2021.