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

Edson, Marcia; Zamboni, Luca Q.

Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2271-2283.

Pour $m\ge 2$, on définit les nombres de $m$-bonacci $F_k=2^k$ pour $0\le k\le m-1$ et $F_k=F_{k-1}+F_{k-2}+\cdots +F_{k-m}$ pour $k\ge 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\left(n\right)$ 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\left(n\right)$ 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\ge 2,$ we consider the $m$-bonacci numbers defined by $F_k=2^k$ for $0\le k\le m-1$ and $F_k=F_{k-1}+F_{k-2}+\cdots +F_{k-m}$ for $k\ge 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\left(n\right)$ 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\left(n\right)$ 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.

Classification : 11B39, 11B50, 68R15
Keywords: Numeration systems, Fibonacci numbers, Fine and Wilf theorem, episturmian words
Mot clés : systèmes de numération, nombres de Fibonacci, théorème de Fine et Wilf, suites episturmiennes

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

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

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

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

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

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

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

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

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

[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, Volume 1 (1922), pp. 77-98 | DOI

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

[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, Volume 42 (1972), pp. 179-182 | MR | Zbl