dénombrements

Publié le par jö

On dit que deux éléments sont (non-)distingables ou (in-)distincts si la situation qui les met en jeu (n') est (pas)  différente de la situation où les deux sont intervertis.

Les erreurs courantes quand on fait du dénombrement proviennent souvent de l'attribution du caractère distingable à des éléments qui ne le sont pas et vice versa.

En considérant par exemple une étude, issue du croisement littéraire improbable entre Raimbault et Pérec, qui consiste à dénombrer les relations f possibles entre s=5 Lettres (A, E, I, U, Y) et  j=8 Couleurs (bLEUE, mAUVE, nOIRE, oRANGE, pOURPRE, rOUGE, tURQUOISE, vERT) telles qu'une C donnée doive correspondre à une L et telle qu'à une C donnée ne puisse correspondre qu'une L possible : L=f(C).

Schématiquement, les L peuvent être vues comme des sites distincts sur chacun desquels on peut placer aucune, une ou plusieurs C vues alors comme des jetons distincts.

Il existe alors un classement naturel, permettant de présenter les s^j fonctions f possibles, composé de s chapitres principaux (correspondants aux s sites possibles pour le jeton bLEU), eux-mêmes composés de s sous-chapitres (pour le mAUVE) etc ... et on se demande s'il est possible de trouver une autre forme de classement composé  de d chapitres principaux tels que le premier chapitre principal corresponde au découpage :
  • une L composée de j Couleurs
  • les autres L sans Couleur,
le second chapitre principal corresponde au découpage :
  • une L composée de j-1 Couleurs
  • une autre L composée de 1 Couleur
  • les autres L sans Couleur,
etc... jusqu'au d-ième c'est-à-dire à partir des situations mettant en jeu des éléments non-distingables, les sous-chapitres se limitant alors à réintégrer la distinction entre les éléments.

On a en fait d(8,5)=18 (voir le calcul de d=d(j,s)) manières de répartir 8 couleurs sur 5 lettres de la plus déséquilibrée (une lettre reçoit toutes les couleurs) à la plus probable (1 lettre reçoit 3 couleurs, 2 lettres reçoivent 2 couleurs, les deux dernières lettres se partagent la dernière couleur). On remarque au passage que la situation la plus équilibrée n'est pas la plus probable et on va vérifier deux relations :


chapitres principaux valeur 1 nb d'occurrences valeur 2 nb d'occ. valeur 3 nb d'occ. valeur 4 nb d'occ. j!/Prod(val!^occ) s!/Prod(occ!) j!s!/(Prod(val!^occ)Prod(occ!))
{8,0,0,0,0} 8 1 0 4         1 5 5
{7,1,0,0,0} 7 1 1 1 0 3     8 20 160
{6,2,0,0,0} 6 1 2 1 0 3     28 20 560
{4,4,0,0,0} 4 2 0 3         70 10 700
{5,3,0,0,0} 5 1 3 1 0 3     56 20 1120
{6,1,1,0,0} 6 1 1 2 0 2     56 30 1680
{5,1,1,1,0} 5 1 1 3 0 1     336 20 6720
{4,1,1,1,1} 4 1 1 4         1680 5 8400
{5,2,1,0,0} 5 1 2 1 1 1 0 2 168 60 10080
{4,2,2,0,0} 4 1 2 2 0 2     420 30 12600
{2,2,2,2,0} 2 4 0 1         2520 5 12600
{3,3,2,0,0} 3 2 2 1 0 2     560 30 16800
{4,3,1,0,0} 4 1 3 1 1 1 0 2 280 60 16800
{3,3,1,1,0} 3 2 1 2 0 1     1120 30 33600
{4,2,1,1,0} 4 1 2 1 1 2 0 1 840 60 50400
{2,2,2,1,1} 2 3 1 2         5040 10 50400
{3,2,1,1,1} 3 1 2 1 1 3     3360 20 67200
{3,2,2,1,0} 3 1 2 2 1 1 0 1 1680 60 100800
                       
                  cumul colonne 495 390625


On a construit le tableau à partir des 18 chapitres principaux (1ère colonne) dont on donne une description dans les 8 colonnes suivantes. Par exemple la quatrième ligne {4,4,0,0,0} correspond à la situation où deux des lettres (2) reçoivent quatre couleurs (4) et les trois autres lettres (3) ne reçoivent aucune couleur (0) : les deuxième et troisième colonnes recensent alors la valeur 4 (deuxième colonne="valeur1") présente 2 fois (troisème colonne="occurrence1"). De même les quatrièmes et cinquième colonne recensent la valeur 0 (quatrième colonne="valeur2") présente 3 fois (cinquième colonne="occurrence2"). Les colonnes sont donc remplies deux par deux et on n'en a que 8 car, ici, on n'a jamais plus de quatre valeurs distinctes tout chapitre confondu.

On détaille alors le calcul de l'antépénultième colonne :
70=8! / [(valeur1 !)^occurrence1 (valeur2 !)^occurrence2]=8!/( (4!)^2 (0!)^3),
celui de l'avant-dernière :
10=5! / [ (2!) (3!)],
la dernière étant leur produit : 700=70.10

La première relation est vérifiable en sommant dans S l'avant-dernière colonne et en notant C_{N,n}=N! / [n! (N-n)!] :
495=C_{12,8} car S=C_{ j+s-1, j}.

La seconde relation est vérifiable en sommant dans T la dernière colonne :
390625=5^8 car T=s^j.

Publié dans mathblog

Commenter cet article