Enumeration of Restricted Words and Linear Recurrence Equations

Publication date 1 June 2017

Abstract: In previous papers, for an arithmetical function

f_{0}

, we defined functions

f_{m}

and

c_{m}

and designated numbers of restricted words over a finite alphabet counted by these functions. In this paper, we examine the reverse problem for five specific types of restricted words. Namely, we find the initial function

f_{0}

such that

f_{m}

and

c_{m}

enumerate these words. In each case, we derive explicit formulas for

f_{m}

and

c_{m}

. Fibonacci, Merssen, Pell, Jacosthal, Tribonacci, and Padovan numbers all appear as values of

f_{m}

, so we obtain new formulas for these numbers. Also, we combinatorially derive explicit formulas for the solutions of five types of homogenous linear recurrence equations.

This page was built for publication: Enumeration of Restricted Words and Linear Recurrence Equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6287358)