Top Coefficients of the Denumerant

Résumé : Considérons une liste $\alpha = [\alpha_1,\alpha_2,\ldots , \alpha_N, \alpha_{N+1}]$ de $N+1$ entiers positifs. Le dénumérant $E(\alpha)(t)$ est la fonction qui compte le nombre de solutions en entiers positifs ou nuls de l’équation $\sum^{N+1}_{i=1}x_i\alpha_i=t$, où $t$ varie dans les entiers positifs ou nuls. Il est bien connu que cette fonction est une fonction quasi-polynomiale de $t$, de degré $N$. Nous donnons un nouvel algorithme qui calcule, pour chaque entier fixé $k$ (mais $N$ n’est pas fixé, les $k+1$ plus hauts coefficients du quasi-polynôme $E(\alpha)(t)$ en termes de fonctions en dents de scie. Notre algorithme utilise la structure d’ensemble partiellement ordonné des pôles de la fonction génératrice de $E(\alpha)(t)$. Les $k+1$ plus hauts coefficients se calculent à l’aide de fonctions génératrices de points entiers dans des cônes polyèdraux de dimension inférieure ou égale à $k$.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.1149-1160, 2013, DMTCS Proceedings
Liste complète des métadonnées

https://hal.inria.fr/hal-01229687
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:57
Dernière modification le : jeudi 11 janvier 2018 - 06:12:14
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:38:37

Fichier

dmAS0197.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229687, version 1

Collections

Citation

Velleda Baldoni, Nicole Berline, Brandon Dutra, Matthias Köppe, Michele Vergne, et al.. Top Coefficients of the Denumerant. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.1149-1160, 2013, DMTCS Proceedings. 〈hal-01229687〉

Partager

Métriques

Consultations de la notice

119

Téléchargements de fichiers

155