---------------------------- Original Message ----------------------------
Subject: références sommes d'entiers
From:    "Michel Nguyen The" <mnguyen@lix.polytechnique.fr>
Date:    Sun, August 3, 2008 4:47 pm
To:      Alain Bruyère <fa085799@skynet.be>
         "Jean Nicolas MAISONNIER" <jean.nicolas@maisonnier.com>
         "Jacques Malbrancke" <jacques.malbrancke@free.fr>
Cc:      "Matthieu Guillermin" <matthieu.guillermin@wanadoo.fr>
--------------------------------------------------------------------------

Bonjour,

Vous travaillez sur des sujets connexes portant sur la sommation d'entiers,
donc je vous envoie un mail collectif puisque des idées reviennent autour
de l'utilisation de séries génératrices. Je mets aussi Matthieu en copie
étant donné son profil scientifique. Lorsque le site permettra à nouveau
l'upload,
je pourrai mettre ce mail -- ou un texte reprenant ce mail -- sur le site.

Un excellent ouvrage sur l'usage des séries génératrices se trouve à la page
http://algo.inria.fr/flajolet/Publications/book.pdf

Pour la lisibilité des formules Maple insérées dans ce mail, il est
préférable
d'utiliser une fonte de type machine à écrire. Vous pouvez par exemple
copier le contenu de ce mail dans un Notepad.

Concernant les travaux d'Alain Bruyère, on peut résumer la distribution
des nombres de sa bioarithmétique par le polynôme
(1+z)*(1+z^2)*(1+z^3)*(1+z^4)*(1+z^5)*(1+z^6)
et un bref usage de Maple permet de vérifier qu'on obtient ainsi
64 représentations de nombre, et 22 nombres différents de 0 à 21,
ainsi que le nombre de représentations par nombre.
Si je tape

P:=(1+z)*(1+z^2)*(1+z^3)*(1+z^4)*(1+z^5)*(1+z^6);
subs(z=1,P);
series(P,z,40);

en mode texte dans Maple j'obtiens :

> P:=(1+z)*(1+z^2)*(1+z^3)*(1+z^4)*(1+z^5)*(1+z^6);
                              2        3        4        5        6
           P := (1 + z) (1 + z ) (1 + z ) (1 + z ) (1 + z ) (1 + z )

> subs(z=1,P);
                                      64

> series(P,z,40);
         2      3      4      5      6      7      8      9      10      11
1 + z + z  + 2 z  + 2 z  + 3 z  + 4 z  + 4 z  + 4 z  + 5 z  + 5 z   + 5 z   +

       12      13      14      15      16      17      18    19    20    21
    5 z   + 4 z   + 4 z   + 4 z   + 3 z   + 2 z   + 2 z   + z   + z   + z

On notera néanmoins que la distribution des représentations de nombres
est différente de la distribution des codons rappelée dans
http://fr.wikipedia.org/wiki/Code_g%C3%A9n%C3%A9tique
Par exemple les nombres 9, 10, 11 et 12 possèdent chacun 5 représentations,
ce qui est le maximum de représentations possible, tandis que plusieurs
codons possèdent 6 représentations.

Si on veut, dans la lignée des travaux de Jacques, poursuivre avec un nombre
de sommants arbitraire, il faut considérer un produit infini des polynômes
(1+z^n). À la page 581 (593 du pdf) du document
http://algo.inria.fr/flajolet/Publications/book.pdf
on trouve l'équivalent asymptotique du nombre de représentations de
l'entier n,
lorsque n tend vers l'infini. J'ai travaillé sur ce genre de méthode
pendant ma thèse, et les méthodes de Mellin sont parmi les plus compliquées.

D'un point de vue pratique, si je veux connaître le nombre de
représentations de 11,
comme je sais que 12 n'interviendra pas dans la sommation, je peux toujours
me contenter d'un polynôme de degré fini et taper

P:=(1+z)*(1+z^2)*(1+z^3)*(1+z^4)*(1+z^5)*(1+z^6)*(1+z^7)*(1+z^8)*(1+z^9)*(1+z^10)*(1+z^11);
series(P,z,40);

pour obtenir

> P:=(1+z)*(1+z^2)*(1+z^3)*(1+z^4)*(1+z^5)*(1+z^6)*(1+z^7)*(1+z^8)*(1+z^9)*(1+z^10)*(1+z^11);
                   2        3        4        5        6        7        8
P := (1 + z) (1 + z ) (1 + z ) (1 + z ) (1 + z ) (1 + z ) (1 + z ) (1 + z )

          9        10        11
    (1 + z ) (1 + z  ) (1 + z  )

> series(P,z,40);
         2      3      4      5      6      7      8      9       10       11
1 + z + z  + 2 z  + 2 z  + 3 z  + 4 z  + 5 z  + 6 z  + 8 z  + 10 z   + 12 z

           12       13       14       15       16       17       18       19
     + 14 z   + 16 z   + 19 z   + 22 z   + 25 z   + 28 z   + 32 z   + 35 z

           20       21       22       23       24       25       26       27
     + 39 z   + 43 z   + 46 z   + 49 z   + 53 z   + 56 z   + 59 z   + 62 z

           28       29       30       31       32       33       34       35
     + 64 z   + 66 z   + 68 z   + 69 z   + 69 z   + 70 z   + 69 z   + 69 z

           36       37       38       39      40
     + 68 z   + 66 z   + 64 z   + 62 z   + O(z  )

et observer que le nombre 11 possède 12 représentations, ou plus
brièvement taper
> coeff(P,z,11);
                                      12

Jacques, tu peux peut-être vérifier que les coefficients des monômes de
degré < 11
correspondent à ce que tu as trouvé.

Si je veux reconnaître en détail les différentes combinaisons d'un entier
donné,
je peux marquer les sommants par une autre variable (je marque n par an).
Regardons ce qu'on trouve pour 9, 10 et 11.

P:=(1+a1*z)*(1+a2*z^2)*(1+a3*z^3)*(1+a4*z^4)*(1+a5*z^5)*(1+a6*z^6)*(1+a7*z^7)*(1+a8*z^8)*(1+a9*z^9)*(1+a10*z^10)*(1+a11*z^11);
coeff(P,z,9);
coeff(P,z,10);
coeff(P,z,11);

> P:=(1+a1*z)*(1+a2*z^2)*(1+a3*z^3)*(1+a\
> 4*z^4)*(1+a5*z^5)*(1+a6*z^6)*(1+a7*z^7\
> )*(1+a8*z^8)*(1+a9*z^9)*(1+a10*z^10)*(1+a11*z^11);
                         2           3           4           5           6
P := (1 + a1 z) (1 + a2 z ) (1 + a3 z ) (1 + a4 z ) (1 + a5 z ) (1 + a6 z )

             7           8           9            10            11
    (1 + a7 z ) (1 + a8 z ) (1 + a9 z ) (1 + a10 z  ) (1 + a11 z  )

> coeff(P,z,9);
       a2 a7 + (a3 + a1 a2) a6 + (a4 + a1 a3) a5 + a2 a3 a4 + a1 a8 + a9

> coeff(P,z,10);
(a3 + a1 a2) a7 + (a4 + a1 a3) a6 + (a1 a4 + a2 a3) a5 + a1 a2 a3 a4 + a2 a8

     + a1 a9 + a10

> coeff(P,z,11);
(a4 + a1 a3) a7 + (a5 + a1 a4 + a2 a3) a6 + (a2 a4 + a1 a2 a3) a5

     + (a3 + a1 a2) a8 + a2 a9 + a1 a10 + a11

On retrouve par exemple 4 + 7 = 11, 1 + 3 + 7 = 11, ..., 11 = 11.

Jacques s'est posé la question d'effectuer des additions sur les
représentations
de nombre. Il peut être utile d'utiliser des diagrammes de Ferrers aussi
appelé
diagrammes de Young, liés au tableaux de Ferrers / tableaux de Young.
La différence avec ce qui intéresse Jacques, c'est qu'un sommant peut
apparaître
plusieurs fois.

Voir des liens
http://www.ams.org/notices/200702/whatis-yong.pdf
http://en.wikipedia.org/wiki/Young_tableau
http://mathworld.wolfram.com/YoungTableau.html

Ce qui intéresse Jacques, ce sont des diagrammes de Young avec des entiers
distincts. On parle de quelque chose d'approchant dans
http://algo.inria.fr/Alcophys/Papers/corteel1.ps
http://algo.inria.fr/seminars/sem00-01/corteel.pdf
(le pdf ci-dessus est le résumé d'un séminaire auquel j'ai assisté
et que j'ai ensuite résumé). La règle verticale est très interessante :
on considère le diagramme comme un tas de sable,
et si on rajoute un grain de sable, celui-ci s'écoule
et cela permet il me semble de vérifier la condition de distinction
des sommants comme le désire Jacques.

Il existe des additions sur les tableaux de Young, qui sont une version
debuguée des diagrammes de young, puisqu'on rajoute des entiers dans les
cases.
Voir par exemple
http://archive.numdam.org/ARCHIVE/SDPP/SDPP_1974-1975__16_1/SDPP_1974-1975__16_1_A2_0/SDPP_1974-1975__16_1_A2_0.pdf
Du point de vue énumératif, on peut passer des tableaux au diagrammes
via les nombres de Hook. Les tableaux de Young sont utilisés en théorie
quantique des champs.

De même que j'ai parlé d'ajouter les grains de sable un à un dans un
diagramme
de Young, on peut rajouter un entier dans un tableau de Young. Voir
http://pauillac.inria.fr/ups/private/ds17.pdf

Il se trouve que j'ai travaillé sur l'algorithme de Robinson-Schensted
dans mon DEA
en 96/97 car je devais faire un résumé sur le monoïde chinois, mais je
n'ai pas
de trace écrite de ce travail.

Concernant les travaux de Jean-Nicolas, c'est un peu plus difficile de
traduire
la règle du nabatéen en termes de polynômes : un poids ne peut intervenir
qu'une seule fois, mais possède deux modes d'intervention, à savoir de
manière
positive ou de manière négative. Théoriquement, il faudrait que je fasse
la somme
de polynômes de la forme :
(1+z)*(1+z^3)*(1+z^9)*(1+z^27),
(1+z^{-1})*(1+z^3)*(1+z^9)*(1+z^27),
...
(1+z^{-1})*(1+z^{-3})*(1+z^{-9})*(1+z^{-27}),
puis enlever 2^4-1, puisque le terme 1 apparaît dans chacun des 2^4
polynômes.
L'énumération de ces polynômes est automatisable puisqu'il s'agit d'énumérer
les nombres de 1 à 2^4 en binaire, mais pour aller plus vite je vais suivre
une autre approche.

Dans un premier temps, pour vérifier que les poids 1, 3, 9 et 27 permettent
de générer les nombres de 1 à 40, je vais d'abord un peu changer les règles.
Je vais permettre à un poids d'intervenir de manière simultanée de manière
positive
et de manière négative. Cela ne change en rien à la nature des nombres
accessibles,
puisque si un poids intervient à la fois de manière positive et négative,
il s'annule. Ce qui change, c'est le nombre de représentations d'un nombre.

Si je tape

P:=(1+z)*(1+z^3)*(1+z^9)*(1+z^27);
Q:=subs(z=1/z,P);
series(P*Q,z,40);

j'obtiens

> P:=(1+z)*(1+z^3)*(1+z^9)*(1+z^27);
                                      3        9        27
                   P := (1 + z) (1 + z ) (1 + z ) (1 + z  )

> Q:=subs(z=1/z,P);
                               /     1  \ /     1  \ /     1 \
                Q := (1 + 1/z) |1 + ----| |1 + ----| |1 + ---|
                               |      3 | |      9 | |     27|
                               \     z  / \     z  / \    z  /

> series(P*Q,z,40);
 -40      -39    -38      -37      -36      -35    -34      -33    -32
z    + 2 z    + z    + 2 z    + 4 z    + 2 z    + z    + 2 z    + z    + 2

     -31      -30      -29      -28      -27      -26      -25      -24
    z    + 4 z    + 2 z    + 4 z    + 8 z    + 4 z    + 2 z    + 4 z    + 2

     -23    -22      -21    -20      -19      -18      -17    -16      -15
    z    + z    + 2 z    + z    + 2 z    + 4 z    + 2 z    + z    + 2 z    +

     -14      -13      -12      -11      -10      -9      -8      -7      -6
    z    + 2 z    + 4 z    + 2 z    + 4 z    + 8 z   + 4 z   + 2 z   + 4 z

          -5      -4      -3      -2      -1      0
     + 2 z   + 4 z   + 8 z   + 4 z   + 8 z   + O(z )

J'effectue un développement limité autour de z=0 donc ce sont les puissances
négatives qui sont dominantes, mais comme en réalité le polynôme PQ
est le même que sa réciproque PQ(1/z) j'obtiendrais des coefficients
similaires
concernant les puissances positives.

On voit que tous les nombres de 1 à 40 apparaissent, donc on peut bien peser
tous les entiers de 1 à 40.

Maintenant si je veux éliminer les doublons dûs au poids qui s'annulent,
je peux marquer les poids par une lettre, comme montré plus haut pour le
problème
de Jacques. Puis j'élimine les lettres qui apparaissent comme puissances
de deux.
Je suis obligé d'effectuer cette opération plusieurs fois sous Maple,
car Maple cherche à factoriser et peut écrire un terme sous la forme par
exemple
               2                     2
    ((a c d + b  c d a) c + a d + a b  d) d)

et après élimination de b*b il reste encore du d*d à éliminer.

P:=(1+a*z)*(1+b*z^3)*(1+c*z^9)*(1+d*z^27);
Q:=subs(z=1/z,P);
series(P*Q,z,40);
subs({a^2=0,b^2=0,c^2=0,d^2=0},%);
subs({a^2=0,b^2=0,c^2=0,d^2=0},%);
subs({a^2=0,b^2=0,c^2=0,d^2=0},%);
subs({a=1,b=1,c=1,d=1},%);

> P:=(1+a*z)*(1+b*z^3)*(1+c*z^9)*(1+d*z^27);
                                      3          9          27
               P := (1 + a z) (1 + b z ) (1 + c z ) (1 + d z  )

> Q:=subs(z=1/z,P);
                               /     b  \ /     c  \ /     d \
                Q := (1 + a/z) |1 + ----| |1 + ----| |1 + ---|
                               |      3 | |      9 | |     27|
                               \     z  / \     z  / \    z  /

> series(P*Q,z,40);
         -40         2         -39            -38           2       -37
b c d a z    + (1 + a ) b c d z    + b c d a z    + (a + a b ) c d z    +

          2         2            -36           2       -35            -34
    (1 + a  + (b + a  b) b) c d z    + (a + a b ) c d z    + b c d a z    +

          2         -33            -32         2           -31
    (b + a  b) c d z    + b c d a z    + (a b c  + a b) d z    +

           2                2        -30         2           -29
    ((c + a  c) b c + (1 + a ) b) d z    + (a b c  + a b) d z    +

               2               2     -28
    ((a c + a b  c) c + a + a b ) d z    +

           2             2                  2         2          -27
    ((c + a  c + (b c + a  b c) b) c + 1 + a  + (b + a  b) b) d z    +

               2               2     -26         2           -25
    ((a c + a b  c) c + a + a b ) d z    + (a b c  + a b) d z    +

             2               2       -24         2           -23
    ((b c + a  b c) c + b + a  b) d z    + (a b c  + a b) d z    + b c d a

     -22         2         -21            -20             2       -19
    z    + (c + a  c) b d z    + b c d a z    + (a c + a b  c) d z    +

          2             2            -18             2       -17
    (c + a  c + (b c + a  b c) b) d z    + (a c + a b  c) d z    + b c d a

     -16           2         -15            -14                 2     -13
    z    + (b c + a  b c) d z    + b c d a z    + (a b c + b c d  a) z    +

           2              2            -12                 2     -11
    ((1 + a ) b c + (d + a  d) b c d) z    + (a b c + b c d  a) z    +

             2                2          -10
    ((a + a b ) c + (a d + a b  d) c d) z    +

           2         2                 2             2               -9
    ((1 + a  + (b + a  b) b) c + (d + a  d + (b d + a  b d) b) c d) z   +

             2                2          -8                 2     -7
    ((a + a b ) c + (a d + a b  d) c d) z   + (a b c + b c d  a) z   +

           2                2            -6                 2     -5
    ((b + a  b) c + (b d + a  b d) c d) z   + (a b c + b c d  a) z   +

          2             2                  -4
    (a b c  + a b + (b c  d a + a b d) d) z   +

           2                2               2                  2           -3
    ((c + a  c) b c + (1 + a ) b + ((c d + a  c d) b c + (d + a  d) b) d) z

             2             2                  -2
     + (a b c  + a b + (b c  d a + a b d) d) z   +

               2               2              2                     2
    ((a c + a b  c) c + a + a b  + ((a c d + b  c d a) c + a d + a b  d) d)

     -1      0
    z   + O(z )

> subs({a^2=0,b^2=0,c^2=0,d^2=0},%);
         -40          -39            -38          -37         2       -36
b c d a z    + b c d z    + b c d a z    + a c d z    + (1 + b ) c d z    +

           -35            -34          -33            -32          -31
    a c d z    + b c d a z    + b c d z    + b c d a z    + a b d z    +

      2           -30          -29       2         -28
    (c  b + b) d z    + a b d z    + (a c  + a) d z    +

           2             2     -27       2         -26          -25
    ((c + b  c) c + 1 + b ) d z    + (a c  + a) d z    + a b d z    +

      2           -24          -23            -22          -21            -20
    (c  b + b) d z    + a b d z    + b c d a z    + b c d z    + b c d a z

              -19         2       -18          -17            -16          -15
     + a c d z    + (c + b  c) d z    + a c d z    + b c d a z    + b c d z

                -14          -13           2       -12          -11
     + b c d a z    + a b c z    + (b c + d  b c) z    + a b c z    +

              2     -10          2            2          -9             2
    (a c + a d  c) z    + ((1 + b ) c + (d + b  d) c d) z   + (a c + a d  c)

     -8          -7           2       -6          -5               2   -4
    z   + a b c z   + (b c + d  b c) z   + a b c z   + (a b + a b d ) z   +

      2           2                -3               2   -2
    (c  b + b + (c  d b + b d) d) z   + (a b + a b d ) z   +

        2           2              -1      0
    (a c  + a + (a c  d + a d) d) z   + O(z )

> subs({a^2=0,b^2=0,c^2=0,d^2=0},%);
         -40          -39            -38          -37        -36          -35
b c d a z    + b c d z    + b c d a z    + a c d z    + c d z    + a c d z

                -34          -33            -32          -31        -30
     + b c d a z    + b c d z    + b c d a z    + a b d z    + b d z    +

           -29        -28     2         -27        -26          -25        -24
    a b d z    + a d z    + (c  + 1) d z    + a d z    + a b d z    + b d z

              -23            -22          -21            -20          -19
     + a b d z    + b c d a z    + b c d z    + b c d a z    + a c d z    +

         -18          -17            -16          -15            -14
    c d z    + a c d z    + b c d a z    + b c d z    + b c d a z    + a b c

     -13        -12          -11        -10         2     -9        -8
    z    + b c z    + a b c z    + a c z    + (c + d  c) z   + a c z   + a
b c

     -7        -6          -5        -4           2   -3        -2
    z   + b c z   + a b c z   + a b z   + (b + b d ) z   + a b z   +

            2   -1      0
    (a + a d ) z   + O(z )

> subs({a^2=0,b^2=0,c^2=0,d^2=0},%);
         -40          -39            -38          -37        -36          -35
b c d a z    + b c d z    + b c d a z    + a c d z    + c d z    + a c d z

                -34          -33            -32          -31        -30
     + b c d a z    + b c d z    + b c d a z    + a b d z    + b d z    +

           -29        -28      -27        -26          -25        -24
    a b d z    + a d z    + d z    + a d z    + a b d z    + b d z    + a b d

     -23            -22          -21            -20          -19        -18
    z    + b c d a z    + b c d z    + b c d a z    + a c d z    + c d z    +

           -17            -16          -15            -14          -13
    a c d z    + b c d a z    + b c d z    + b c d a z    + a b c z    + b c

     -12          -11        -10      -9        -8          -7        -6
    z    + a b c z    + a c z    + c z   + a c z   + a b c z   + b c z   +

           -5        -4      -3        -2      -1      0
    a b c z   + a b z   + b z   + a b z   + a z   + O(z )

> subs({a=1,b=1,c=1,d=1},%);
 -40    -39    -38    -37    -36    -35    -34    -33    -32    -31    -30
z    + z    + z    + z    + z    + z    + z    + z    + z    + z    + z    +

     -29    -28    -27    -26    -25    -24    -23    -22    -21    -20    -19
    z    + z    + z    + z    + z    + z    + z    + z    + z    + z    + z

        -18    -17    -16    -15    -14    -13    -12    -11    -10    -9
     + z    + z    + z    + z    + z    + z    + z    + z    + z    + z   +

     -8    -7    -6    -5    -4    -3    -2    -1      0
    z   + z   + z   + z   + z   + z   + z   + z   + O(z )

>

À la fin on voit qu'il n'existe qu'une seule manière de peser un entier
(signé)
donné.

Pour le problème dans sa généralité, je ne pense pas que l'utilisation
de séries génératrices permette de faire l'économie d'une recherche des
solutions,
éventuellement simplifiée par programmation dynamique. Un problème
intéressant
de programmation dynamique est celui du sac-à-dos. Voir les liens
http://www.lix.polytechnique.fr/~cori/Majeure/cours2.pdf
http://wwwens.uqac.ca/~rebaine/8INF806/Chapitre5propreprogrammationdynamique.pdf
et regarder l'exercice 5 dans les fichiers (énoncé et solution)
http://wwwens.uqac.ca/~rebaine/8INF806/programmationdynamiquepropreserie2005.pdf
http://wwwens.uqac.ca/~rebaine/8INF806/Solutionnaireprogrammationdynamique.pdf

Dans ma thèse, j'ai un peu travaillé sur la reconnaissances de structures
secondaires
d'ARN à partir d'un mot d'ARN. Cela revient, grosso modo, à partir d'un mot
constitué de parenthèses, d'apparier le plus de parenthèses possibles.
La nature trouve une structure optimale par minimisation d'énergie
suivant sans doute des lois physiques, mais nous programmons cela plutôt
par programmation dynamique suivant une grammaire de règles de transition.
L'analyse asymptotique (via l'utilisation de séries génératrices)
peut éventuellement permettre de couper plus vite dans la programmation
dynamique :
dans une programmation dynamique naïve, on doit calculer certains
sous-problèmes
de manière exhaustive, mais si on a une idée de la distribution d'énergie,
pour un sous-sous-problème on peut considérer que l'énergie obtenue
est trop faible et ne pas effectuer le calcul du sous-problème jusqu'au bout.
Il est vrai que dans la nature on ne cherche pas forcément une solution
optimale mais seulement une solution sous-optimale, et du coup couper
dans la programmation dynamique fait encore plus sens.

Je vous ai transmis l'essentiel de mes connaissances par rapport à ces
divers sujets,
mais il me semblerait plus intéressant de creuser là où il y a un intérêt
philosophique. En effet, je ne vois pas poindre de bioarithmétique à
l'horizon
(voir pas exemple ma première objection en début de mail).
En outre, la question de la bioarithmétique me paraît philosophiquement
mal posée.
Par phénomène de sérendipité on peut peut-être trouver des choses,
mais pourquoi ne pas creuser là où l'on se pose des questions ?
Jacques évoque souvent des questions sur des concepts physiques
lors des repas mais jamais lors de réunion. Il faudrait faire une liste
de ce genre de questions et creuser par là.

Michel