On the Number of Partitions of an Integer in the $m$-bonacci Base

Edson, Marcia; Zamboni, Luca Q.

On the Number of Partitions of an Integer in the

m

-bonacci Base
[Sur le nombre de partitions d’un entier en base

m

-bonacci]

Edson, Marcia ; Zamboni, Luca Q.

Annales de l'Institut Fourier, Tome 56 (2006), p. 2271-2283 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

Pour $m \geq 2$ , on définit les nombres de $m$ -bonacci $F_{k} = 2^{k}$ pour $0 \leq k \leq m - 1$ et $F_{k} = F_{k - 1} + F_{k - 2} + \dots + F_{k - m}$ pour $k \geq m .$ Dans le cas $m = 2,$ on retrouve les nombres de Fibonacci. Chaque entier positif $n$ s’écrit comme une somme distincte de nombres de $m$ -bonacci d’une ou plusieurs façons. Soit $R_{m} (n)$ le nombre de partitions de $n$ en base $m$ -bonacci. En utilisant un théorème de Fine et Wilf on déduit une formule pour $R_{m} (n)$ comme somme de coefficients binomiaux modulo $2 .$ De plus, nous montrons que cette formule peut-être utilisée pour déterminer le nombre de partitions de $n$ dans des systèmes généraux de numération incluant les systèmes de nombres d’Ostrowski généralisés associés aux suites episturmiennes.

For each $m \geq 2,$ we consider the $m$ -bonacci numbers defined by $F_{k} = 2^{k}$ for $0 \leq k \leq m - 1$ and $F_{k} = F_{k - 1} + F_{k - 2} + \dots + F_{k - m}$ for $k \geq m .$ When $m = 2,$ these are the usual Fibonacci numbers. Every positive integer $n$ may be expressed as a sum of distinct $m$ -bonacci numbers in one or more different ways. Let $R_{m} (n)$ be the number of partitions of $n$ as a sum of distinct $m$ -bonacci numbers. Using a theorem of Fine and Wilf, we obtain a formula for $R_{m} (n)$ involving sums of binomial coefficients modulo $2 .$ In addition we show that this formula may be used to determine the number of partitions of $n$ in more general numeration systems including generalized Ostrowski number systems in connection with Episturmian words.

Publié le : 2006-01-01

MR 2290781 | Zbl 1147.11012

DOI : https://doi.org/10.5802/aif.2240
Classification: 11B39, 11B50, 68R15
Mots clés: systèmes de numération, nombres de Fibonacci, théorème de Fine et Wilf, suites episturmiennes

@article{AIF_2006__56_7_2271_0,
     author = {Edson, Marcia and Zamboni, Luca Q.},
     title = {On the Number of Partitions of an Integer in the $m$-bonacci Base},
     journal = {Annales de l'Institut Fourier},
     volume = {56},
     year = {2006},
     pages = {2271-2283},
     doi = {10.5802/aif.2240},
     zbl = {1147.11012},
     mrnumber = {2290781},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_2006__56_7_2271_0}
}

Edson, Marcia; Zamboni, Luca Q. On the Number of Partitions of an Integer in the $m$-bonacci Base. Annales de l'Institut Fourier, Tome 56 (2006) pp. 2271-2283. doi : 10.5802/aif.2240. http://gdmltest.u-ga.fr/item/AIF_2006__56_7_2271_0/

Bibliographie

[1] Berstel, J. An exercise on Fibonacci representations, A tribute to Aldo de Luca, RAIRO, Theor. Inform. Appl., Tome 35 (2002), pp. 491-498 | Article | Numdam | MR 1922290 | Zbl 1005.68119

[2] Berthé, V. Autour du système de numération d’Ostrwoski, Bull. Belg. Math. Soc. Simon Stevin, Tome 8 (2001), pp. 209-239 (Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000)) | MR 1838931 | Zbl 0994.68100

[3] Carlitz, L. Fibonacci representations, Fibonacci Quarterly, Tome 6(4) (1968), pp. 193-220 | MR 236094 | Zbl 0167.03901

[4] Fine, N.J.; Wilf, H.S. Uniqueness theorem for periodic functions, Proc. Amer. Math. Soc., Tome 16 (1965), pp. 109-114 | Article | MR 174934 | Zbl 0131.30203

[5] Jenkinson, O.; Zamboni, L.Q. Characterizations of balanced words via orderings, Theoret. Comput. Sci., Tome 310 (2004), pp. 247-271 | Article | MR 2020344 | Zbl 1071.68090

[6] Justin, J. Episturmian words and morphisms (results and conjectures), Algebraic combinatorics and Computer Science, Springer Italia, Milan (2001), pp. 533-539 | MR 1854492 | Zbl 0971.68125

[7] Justin, J.; Pirillo, G. Episturmian words and Episturmian morphisms, Theoret. Comput. Sci., Tome 302 (2003), pp. 1-34 | MR 1896357 | Zbl 1002.68116

[8] Justin, J.; Pirillo, G. Episturmian words: shifts, morphisms and numeration systems, Internat. J. Found. Comput. Sci., Tome 15 (2004), pp. 329-348 | Article | MR 2071462 | Zbl 1067.68115

[9] Justin, J.; Vuillon, L. Return words in Sturmian and Episturmian words, Theor. Inform. Appl., Tome 34 (2000), pp. 343-356 | Article | Numdam | MR 1829231 | Zbl 0987.68055

[10] Kocábová, P.; Masácová, Z.; Pelantová, E. Ambiguity in the $m$ -bonacci numeration system (2004) (preprint)

[11] Ostrowski, A. Bemerkungen zur Theorie der Diophantischen Approximation I, Abh. Math. Sem. Hamburg, Tome 1 (1922), pp. 77-98 | Article

[12] Tijdeman, R.; Zamboni, L.Q. Fine and Wilf words for any periods, Indag. Math. (N.S.), Tome 14 (2003), pp. 135-147 | Article | MR 2015604 | Zbl 02075522

[13] Zeckendorff, E. Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Royale Sci. Liège, Tome 42 (1972), pp. 179-182 | MR 308032 | Zbl 0252.10011