dimension quelconque

Publié le par jö

On travaille dans les entiers >0. On dispose de 2 uplets u={u_1,...,u_n} et v={v_1,...,v_m} tels que sum( k=1, k=n, u_k) = sum( k=1, k=m, v_k) = j.

On note @ l'opération entre u et v qui a entropy(u,v) pour résultat c'est-à-dire le nombre de façons distinctes de faire correspondre n billes (respectivement cases) de multiplicité (resp. capacités) u_i avec m cases (resp. billes) de capacités (resp. multiplicités) v_k.

On a une formule récursive qui exprime u@v en fonction des Iu({p_1,...,p_x},q) qui sont identiques à u à l'exception des x termes indicés par p_i qui vérifient Iu({p_1,...,p_x},q)_{p_i} = u_{p_i} - q (omis si nuls):


u@v = - sum( q=1, q=min(m,u_n), (-1)^q sum( k=1, k=m!/q!/(m-q)!, Iu({n},q) @ Iv({p_1,..., p_q},1) ) )

où la somme en k des Iu@Iv (où Iu est constant pour un q donné) est réalisée avec tous les Iv courants possibles distincts en omettant les 0 (exemple : avec v={1,2,3} et q=2, les Iv sont à prendre dans { {1,3}, {2,2}, {1,1,2} } ).

A la première évaluation, on simplifie le problème en se rapprochant de 0 mais on a développé par ailleurs l'expression qui comporte alors plus de @. Il faut pourtant continuer à développer les Iu@Iv car au fur et à mesure les Iu_p décroissent et quand ils s'annulent, on les fait disparaître des Iu en omettant de noter les 0.
Quand un Iu n'est plus composé que du terme Iu_p, on a {Iu_p}@v=1 pour tout v donc un @ disparaît.

Dans la formule, on souligne qu'on a donné un rôle privilégié au terme u_n désigné comme le "pivot" et, en pratique, il vaut mieux choisir de noter avec n l'indice du plus petit u_i pour arriver pus vite.


Exemple avec u={u_1,u_2,u_3}={5,3,1} et v={v_1,v_2,v_3,v_4}={4,3,1,1} : n=3,m=4

Iu({3},1)@Iv({1},1) + Iu({3},1)@Iv({2},1) + Iu({3},1)@Iv({3},1) + Iu({3},1)@Iv({4},1) est équivalent à

{5,3}@{3,3,1,1} + {5,3}@{4,2,1,1} + {5,3}@{4,3,1} + {5,3}@{4,3,1} et en continuant le développement :

{4,3}@{3,3,1} + {5,2}@{3,3,1} + {4,3}@{4,2,1} + {5,2}@{4,2,1} + 2 ({4,3}@{4,3}+{5,2}@{4,3})
puis

{3,3}@{3,3} +3 {4,2}@{3,3} + 2 {4,2}@{4,2} + 2 ({4,3}@{4,3} + {5,2}@{4,3}) + 4.

Ces 5 entropies sont développées séparément :

{3,3}@{3,3} = 2 {3,2}@{2,3} - {3,1}@{2,2} = 2 ({3,1}@{1,3} + {3,1}@{2,2} - 1 ) - 2 = 4
{4,2}@{3,3} = 2 {1,4}@{2,3} - 1 = 3
{4,2}@{4,2} = {4,1}@{3,2} + {4,1}@{4,1} -1 = 3
{4,3}@{4,3} = {4,2}@{3,3} + {4,2}@{4,2} - {4,1}@{3,2} = 4
{5,2}@{4,3} = {5,1}@{3,3}+{5,1}@{4,2} - 1 = 3

et finalement {5,3,1}@{4,3,1,1} = 37.

Avec Mathematica, une sous-fonction "omis" qui se charge de l'omission des 0 :

In[1]:= omis[t_] := Block[{w}, {
  w = {}, For[j = 1, j
    ≤ Length[t], If[¬ (t[[j]] == 0), AppendTo[w, t[[j]]]]; j++]}; w]

et la fonction récursive -perfectible sans doute- "ent" :

In[2]:= ent[u_, v_] := If[Length[u] ==
   1 ∨ Length[v] == 1, 1, -Block[{m, r}, {m = Length[v], r = Sum[(-1)^q 
    Block[{s, p}, {p = Permutations[Block[{a}, {a = Table[0, {i, m - q}],
           For[i = 1, i ≤
              q, AppendTo[a, 1]; i++]}; a]], s =
                    Sum[Block[{Iu,
                      Iv}, {Iu = Sort[omis[Block[{b}, {b = u, b[[1]] = b[[
                          1]] - q};
                              b]]], Iv = Sort[omis[v - p[[k]]]]}; If[Iu[[
                            1]] < Iv[[1]], ent[Iu, Iv], ent[Iv,
                              Iu]]], {k, 1, Length[p]}]}; s], {q, 1, Min[m,
                          u[[1]]]}]}; r]]

Vérification (note : le choix du plus rapide est automatique, il est donc inutile de chercher à attribuer n au plus petit ou le plus petit à n ou que-sais-je. Il faut quand même s'assurer que la somme du premier argument égale la somme du second car rien n'est codé dans le cas contraire) :

In[3]:= ent[{1, 3, 5}, {1, 1, 3, 4}]
Out[3]= 37

Prochain épisode en février après les examens...

 Creative Commons License
Cette création est mise à disposition sous un contrat Creative Commons.

Publié dans mathblog

Commenter cet article