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]
Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2271-2283.

Pour m2, on définit les nombres de m-bonacci F k =2 k pour 0km-1 et F k =F k-1 +F k-2 ++F k-m pour km. 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 m2, we consider the m-bonacci numbers defined by F k =2 k for 0km-1 and F k =F k-1 +F k-2 ++F k-m for km. 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.

DOI : 10.5802/aif.2240
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
Edson, Marcia 1 ; Zamboni, Luca Q. 1

1 University of North Texas Department of Mathematics PO Box 311430 Denton, TX 76203-1430 (USA)
@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},
     pages = {2271--2283},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     doi = {10.5802/aif.2240},
     zbl = {1147.11012},
     mrnumber = {2290781},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/aif.2240/}
}
TY  - JOUR
AU  - Edson, Marcia
AU  - Zamboni, Luca Q.
TI  - On the Number of Partitions of an Integer in the $m$-bonacci Base
JO  - Annales de l'Institut Fourier
PY  - 2006
SP  - 2271
EP  - 2283
VL  - 56
IS  - 7
PB  - Association des Annales de l’institut Fourier
UR  - http://archive.numdam.org/articles/10.5802/aif.2240/
DO  - 10.5802/aif.2240
LA  - en
ID  - AIF_2006__56_7_2271_0
ER  - 
%0 Journal Article
%A Edson, Marcia
%A Zamboni, Luca Q.
%T On the Number of Partitions of an Integer in the $m$-bonacci Base
%J Annales de l'Institut Fourier
%D 2006
%P 2271-2283
%V 56
%N 7
%I Association des Annales de l’institut Fourier
%U http://archive.numdam.org/articles/10.5802/aif.2240/
%R 10.5802/aif.2240
%G en
%F 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) no. 7, pp. 2271-2283. doi : 10.5802/aif.2240. http://archive.numdam.org/articles/10.5802/aif.2240/

[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

Cité par Sources :