Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7

On Linear Recurrence Equations Arising from Compositions of Positive Integers

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


For an arithmetic function f0, we define a new arithmetic function f1, generalizing the linear recurrence for the numbers of compositions of positive integers. Using f1 in the same way, we then define f2, and so on.

We establish some patterns related to the sequence f1, f2, ... . Our investigations depend on the following result: if f0 satisfies a linear recurrence equation of order k, then each function fm will also satisfy a linear recurrence equation of the same order.

In several results, we derive a recurrence equation for fm(n) in terms of m and n. For each result, we give a combinatorial meaning for fm(n) in terms of the number of restricted words over a finite alphabet.

We also find new combinatorial interpretations of the Fibonacci polynomials, as well as the Chebyshev polynomials of the second kind.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000045 A000073 A000078 A000079 A000129 A000244 A001045 A001076 A001090 A001109 A001353 A001401 A001591 A001592 A001906 A003480 A003948 A003949 A003950 A003951 A003952 A003953 A003954 A004187 A004189 A004190 A004191 A004254 A005668 A006130 A006131 A006190 A007655 A008616 A008676 A008677 A015440 A015441 A015442 A015443 A015445 A015446 A015447 A015451 A015453 A015454 A015455 A015456 A015457 A018913 A020699 A025192 A025795 A025839 A028859 A029144 A029280 A041025 A041041 A049660 A052918 A053404 A054413 A075843 A077412 A077421 A078362 A078364 A078366 A078368 A079262 A086347 A092499 A093138 A097778 A099842 A104144 A109707 A119826 A122189 A122265 A122391 A125145 A126473 A126501 A126528 A145839 A145840 A145841 A155020 A161434 A168082 A168083 A168084 A170732 A170733 A170734 A180033 A180037 A180167 A209239 A220469 A220493 A249169.)

Received November 9 2014; revised version received January 30 2015; February 5 2015; February 25 2015. Published in Journal of Integer Sequences, May 17 2015.

Return to Journal of Integer Sequences home page