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

Edson, Marcia; Zamboni, Luca Q.

doi:10.5802/aif.2240

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.¹

¹ University of North Texas Department of Mathematics PO Box 311430 Denton, TX 76203-1430 (USA)

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

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.

MR Zbl

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

Affiliations des auteurs :

Edson, Marcia ¹ ; Zamboni, Luca Q. ¹

¹ 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 = {https://www.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  - https://www.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 https://www.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. https://www.numdam.org/articles/10.5802/aif.2240/

Bibliographie
Cité par

[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 :