Statistics on restricted Fibonacci words

Document Type : Research Paper


Department of Computer Science, University of California Santa Barbara, CA 93106, USA


We study two foremost Mahonian statistics, the major index and the inversion number for a class of binary words called restricted Fibonacci words. The language of restricted Fibonacci words satisfies recurrences which allow for the calculation of the generating functions in two different ways. These yield identities involving the $q$-binomial coefficients and provide non-standard $q$-analogues of the Fibonacci numbers. The major index generating function for restricted Fibonacci words turns out to be a $q$-power multiple of the inversion generating function.


Main Subjects

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and its Applications, 2, Addison-Wesley
Publishing Co., Reading, Mass.-London-Amsterdam, 1976.
[2] G. E. Andrews, C. D. Savage and H. S. Wilf, Hypergeometric identities associated with statistics on words, Advances
in Combinatorics, Springer, Heidelberg, (2013) 77–100.
[3] L. Carlitz, Fibonacci notes. III: q-Fibonacci numbers, Fibonacci Quart., 12 (1974) 317–322.
[4] L. Carlitz, Fibonacci notes. IV: q-Fibonacci Polynomials, Fibonacci Quart., 13 (1975) 97–102.
[5] L. Carlitz, A combinatorial property of q-Eulerian numbers, Amer. Math. Monthly, 82 (1975) 51-54.
[6] J. Cigler, q-Fibonacci polynomials, Fibonacci Quart., 41 (2003) 31–40.
[7] R. J. Clarke, E. Steingrimsson and J. Zeng, New Euler-Mahonian statistics on permutations and words, Adv. in
Appl. Math., 18 (1990) 237–270.
[8] D. Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc., 19 (1968) 236–240.
[9] D. Foata, Rearrangements of words, in Combinatorics on Words (M. Lothaire, Ed.), Encyclopedia of Mathematics
and Its Applications, 17, G.-C. Rota, Ed., Cambridge Univ. Press, Cambridge, 1984.
[10] S. Heubach, A. Knopfmacher, M. E. Mays and A. Munagi, Inversions in compositions of integers, Quaest. Math, 34
(2011) 187–202.
[11] V. E. Jr. Hoggatt and M. Bicknell, Roots of Fibonacci polynomials, Fibonacci Quart., 11 (1973) 271–274.
[12] K. W. J. Kadell, Weighted inversion numbers, Restricted Growth Functions, and Standard Young Tableaux, J.
Combin. Theory Ser. A, 40 (1985) 22–44.
[13] P. A. MacMahon, Combinatory analysis, Two volumes (bound as one) Chelsea Publishing Co., New York, 1960.
[14] B. E. Sagan and C. D. Savage, Mahonian pairs, J. Combin. Theory Ser. A, 119 (2012) 526–545.
[15] E. Saygı and Ö. Eğecioğlu, q-cube Enumerator Polynomial of Fibonacci Cubes, Discrete Appl. Math., 226 (2017)
[16] R. P. Stanley, Enumerative Combinatorics, 1, Cambridge University Press, Cambridge, 1997.