Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.4

Words and Linear Recurrences

Milan Janjić
Department of Mathematics and Informatics
University of Banja Luka
Banja Luka, 78000
Republic of Srpska, BA


In previous papers, we defined functions fm and cm based on an arithmetical function f0, and determined numbers of restricted words over a finite alphabet counted by these functions. In this paper, we examine the reverse problem: for each of the five specific types of restricted words, we find the initial function f0 such that fm and cm enumerate these words. We derive explicit formulas for fm and cm.

Fibonacci, Mersenne, Pell, Jacosthal, Tribonacci, and Padovan numbers all appear as values of fm. We derive their new combinatorial interpretations and the explicit formulas.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000129 A000931 A001045 A037027 A054456 A054458 A062110 A073370 A078812 A104578 A104580 A105306 A105422 A110441 A113413 A116412 A116414 A125662 A132964 A154929 A168561 A188137 A207823 A207824.)

Received July 26 2017; revised versions received November 30 2017; December 24 2017; December 25 2017. Published in Journal of Integer Sequences, January 21 2018.

Return to Journal of Integer Sequences home page