entropie : bilan pratique

Publié le par jö

Cet article conclut une longue série d'articles consacrée à la fonction baptisée entropie qui donne le nombre d'associations possibles entre un ensemble de récipients de capacités données et un ensemble de jetons de multiplicités données, la somme des capacités étant égale à la somme des multiplicités (les associations sont en fait des bijections).

On a d'abord donné une interprétation au sens des graphes, puis mis en évidence la propriété de symétrie et enfin donné une formule de calcul.

On va finalament donner une procédure permettant d'énumérer ces associations de manière contrôlée. On commence par rappeler qu'une bijection entre 2 ensembles u et v peut être représentée par une matrice binaire répondant à la contrainte du problème des tours.

Par exemple avec u={3,2,1} et v={3,1,1,1} et comme les permutations dans les sous-blocs sont sans conséquences, la matrice

    3   1 1 1
  0 0 0 1 0 0
3 0 0 0 0 1 0
  0 0 0 0 0 1
2 1 0 0 0 0 0
  0 1 0 0 0 0
1 0 0 1 0 0 0

est par exemple équivalente à la matrice

    3   1 1 1
  0 0 0 1 0 0
3 0 0 0 0 1 0
  0 0 0 0 0 1
2 0 1 0 0 0 0
  0 0 1 0 0 0
1 1 0 0 0 0 0

et on la symbolisera dans un premier temps par


  3 1 1 1
3 0 1 1 1
2 2 0 0 0
1 1 0 0 0

et, sous cette forme, on en déduit que chaque case (d'indice ligne l et d'indice colonne c) peut dans l'absolu varier entre 0 et min(l,c). De plus, on observe que la somme des éléments d'une ligne (colonne) d'indice l (c) vaut l (c) si bien qu'on peut finalement réduire l'étude à des matrices plus petites en supprimant une ligne et une colonne. Dans l'exemple, on n'a donc autant d'informations qu'au départ en travaillant sur

0 1 1
2 0 0

en ayant supprimé la dernière ligne et la dernière colonne de la matrice précédente. Les {3,2,1}@{3,1,1,1}=19 associations possibles peuvent ainsi être énumérées en énumérant les matrices

0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 2 0 0 2 0 0 2 0 0 2 0 1 2 0 1 2 0 1 2 1 0 2 1 0 2 1 0 3 0 0 3 0 0 3 0 0
2 0 0 1 1 0 2 0 0 1 0 1 2 0 0 1 0 0 2 0 0 0 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1
 
possibles répondant aux contraintes.

Publié dans mathblog

Pour être informé des derniers articles, inscrivez vous :

Commenter cet article