Words and Linear Recurrences

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

                        agnus@blic.net

Abstract

In previous papers, for an arithmetical function f_{0}, we defined the functions f_{m} and c_{m}, and designated the number 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 f_{0} such that f_{m} and c_{m} enumerate these words. We derive explicit formulas for f_{m} and c_{m}.

The Fibonacci, Mersenne, Pell, Jacosthal, Tribonacci, and Padovan numbers all appear as values of f_{m}. We give new combinatorial interpretations and explicit formulas for f_{m}.

1 Introduction

This paper is a continuation of the investigations of the problem of restricted words enumeration from the author’s previous papers [2, 3, 4], where two functions f_{m} and c_{m} were defined as follows. For an initial arithmetic function f_{0}, the function f_{m}, (m ≥ 1) is the m^{th} invert transform of f_{0}. The function c_{m}(n, k) was defined as

c_{m}(n, k) = ∑_{i_{1}+i_{2}+···+i_{k}=n} f_{m−1}(i_{1}) · f_{m−1}(i_{2}) ⋯ f_{m−1}(i_{k}),  (1)

where the sum is over positive i_{1}, i_{2}, …, i_{k}.

The functions f_{m} and c_{m} depend only on the initial function f_{0}, and are related to the enumeration of weighted compositions. Namely, if f_{m−1}(i), (i = 1, 2, …) is the weight of i, then f_{m}(n) is the number of all weighted compositions of n, and c_{m}(n, k) is the number of weighted compositions of n into k parts.

In Janjić [2, 3, 4], weighted compositions were related to restricted words over a finite alphabet. For a given initial function f_{0}, we investigated restricted words counted by f_{m} and c_{m}. In this paper, we reverse the problem. Namely, for each of five types of restricted words, we first find the initial function f_{0} that counts such words. We then derive formulas for f_{m} and c_{m} and give its combinatorial meanings in terms of restricted words.

We firstly restate results from our recent papers [2, 3, 4], which will be used in this work.

(A) [2, Theorem 6] Let f_{0} be an arithmetic function, and let k be a positive integer. If there exist constants a_{0}(1), a_{0}(2), …, a_{0}(k) such that

f_{0}(n + k; k) = ∑_{i=1}^{k} a_{0}(i)f_{0}(n + k − i; k), (n ≥ 1),

where f_{0}(1; k), f_{0}(2; k), …, f_{0}(k; k) are arbitrary numbers. Then we have

f_{1}(i; k) = ∑_{j=1}^{i} f_{0}(j; k)f_{1}(i − j; k), (i = 1, 2, …, k), and

f_{1}(n + k; k) = ∑_{i=1}^{k} a_{1}(i)f_{1}(n + k − i; k), (n ≥ 1),

where

a_{1}(1) = a_{0}(1) + f_{0}(1; k),

a_{1}(i) = a_{0}(i) + f_{0}(i; k) − ∑_{j=1}^{i−1} a_{0}(j)f_{0}(i − j; k), (2 ≤ i ≤ k).

(B) [2, Corollary 9]. If f_{0}(1), f_{0}(2), a_{0}(1), a_{0}(2) are arbitrary, and

f_{0}(n + 2) = a_{0}(1)f_{0}(n + 1) + a_{0}(2)f_{0}(n),

then

f_{m}(1) = f_{0}(1), f_{m}(2) = mf_{0}(1)^{2} + f_{0}(2),
f_{m}(n + 2) = a_{m}(1)f_{m}(n + 1) + a_{m}(2)f_{m}(n),

where

a_{m}(1) = a_{0}(1) + mf_{0}(1), a_{m}(2) = a_{0}(2) − ma_{0}(1)f_{0}(1) + mf_{0}(2).

(C) [2, Proposition 23]. Assume that f_{0}(1) = 0, and f_{0}(i) = 1, (i > 1). Then we have

f_{m}(1) = 0, f_{m}(2) = 1,

and

f_{m}(n + 2) = f_{m}(n + 1) + mf_{m}(n).

(D) [3, Corollary 2]. The following formula holds:

f_{m}(n) = ∑_{k=1}^{n} c_{m}(n, k).

(E) [4, Proposition 6]. The following formula holds:

c_{m}(n, k) = ∑_{i=k}^{n}(m − 1)^{i−k}\binom{i − 1}{k − 1}c_{1}(n, i), (1 ≤ k ≤ n).

(F) [4, Propositions 12]. Assume that f_{0}(1) = 1 and m > 1. Assume next that, for n ≥ 1, we have f_{m−1}(n) words of length n−1 over a finite alphabet α. Let x be a letter which is not in α. Then, c_{m}(n, k) is the number of words of length n − 1 over the alphabet α ∪ {x} in which x appears exactly k − 1 times.

We consider the following five types of restricted words over a finite alphabet:

1. Words over {0, 1, …, a−1, …}, such that no two adjacent letters from {0, 1, …, a−1} are the same.

2. Words over {0, 1, …, a − 1, …} such that letters 0, 1, …, a − 1 avoid a run of odd length.

3. Words over {0, 1, …, a, …} avoiding subwords of the form 0i, (i = 1, …, b), for b < a.

4. Words over {0, 1, …} such that 0 and 1 appear only as subwords of the form 1i, where i is a run of zeros.

5. Words over {0, 1, …} in which 0 appears only in a run of even length, and 1 appears only in a run the length of which is divisible by 3.

We note that the initial function f_{0} will be defined by a linear homogeneous recurrence in all cases.

2 Case 1

To solve the problem posed in Case 1, we consider the following linear recurrence:

f_{0}(1) = 1, f_{0}(2) = a,
f_{0}(n + 2) = (a − 1)f_{0}(n + 1), (n ≥ 1),

where a > 0. It is easy to see that

f_{0}(n) = a(a − 1)^{n−2}, (n ≥ 2).

Remark 1. This formula appears in Birmajer at al. [1, Example 17]. Also, the case a = 1 is considered in [4, Example 18].

The function f_{0} has the following combinatorial interpretation:

Proposition 2. The number f_{0}(n) is the number of words of length n−1 over {0, 1, …, a−1} such that no two adjacent letters are the same.

Proof. We have f_{0}(1) = 1, since only the empty word has length 0. Also, f_{0}(2) = a, since a word of length 1 may consist of an arbitrary letter. To obtain a word of length n + 2, for n > 0, we need to insert a − 1 letters in front of each word of length n + 1.

As an immediate consequence of (B), we obtain

Corollary 3. For m ≥ 0, the following recurrence holds:

f_{m}(1) = 1, f_{m}(2) = m + a,
f_{m}(n + 2) = (m + a − 1)f_{m}(n + 1) + mf_{m}(n), (n ≥ 1).

We now describe words counting by f_{m}.

Proposition 4. The number f_{m}(n) is the number of words of length n − 1 over the alphabet {0, 1, …, a − 1, a, …, m + a − 1}, such that no two adjacent letters from {0, 1, …, a − 1} are the same.

Proof. We have f_{m}(1) = 1, since only the empty word has length 0. Also, f_{m}(2) = m + a since a word of length 1 may consist of any letter of the alphabet. Assume that n > 2. Consider a word of length n + 1. In front of such a word, we insert a letter different from the first letter of the word. In this way, we obtain all words of length n + 2 beginning with two different letters. The remaining words must begin with two same letters. Since there are mf_{m}(n) such words, the statement is true.

Remark 5. For a = 2, the continued fraction [f_{0}(1); f_{0}(2), f_{0}(3), …] equals \sqrt{2}. The sequence f_{1}(1), f_{1}(2), …, f_{1}(n) is the numerator of the nth convergent of \sqrt{2}. Also, f_{1}(n) is the number of ternary words of length n − 1 avoiding 00 and 11.

Since f_{m}(1) = 1, we may apply (F) to obtain

Proposition 6. The number c_{m}(n, k) is the number of words of length n−1 over {0, 1, …, a− 1, …, m + a − 1} in which k − 1 letters equal m + a − 1, and no two adjacent letter from {0, 1, …, a − 1} are identical.

We next derive an explicit formula for c_{1}(n, k).

Proposition 7. We have

c_{1}(n, n) = 1,

c_{1}(n, k) = ∑_{i=0}^{k−1} \binom{k}{i}\binom{n − k − 1}{k − i − 1}a^{k−i}(a − 1)^{n−2k+i}, (k < n).

Proof. From (1), we firstly obtain c_{1}(n, n) = 1. Assume that k < n. Since at most k − 1 of i_{t}, (t = 1, 2, …, k) may equal 1, then

c_{1}(n, k) = ∑_{i=0}^{k−1} \binom{k}{i} ∑_{j_{1}+j_{2}+···+j_{k−i}=n−i} f_{0}(j_{1})f_{0}(j_{2}) ⋯ f_{0}(j_{k−i})

= ∑_{i=0}^{k−1} \binom{k}{i}a^{k−i}(a − 1)^{n−2k+i} ∑_{j_{1}+j_{2}+···+j_{k−i}=n−i} 1,

where the last sum is taken over j_{t} ≥ 2. It follows that

c_{1}(n, k) = ∑_{i=0}^{k−1} a^{k−i}(a − 1)^{n−2k+i}\binom{k}{i}\binom{n − k − 1}{k − i − 1}.

Remark 8. Note that, in the preceding formula, terms in which i < 2k − n would equal zero.

To obtain an explicit formula for c_{m}(n, k), we use (E). Extracting the term for i = n, we obtain

c_{m}(n, k) = (m − 1)^{n−k}\binom{n − 1}{k − 1} + ∑_{i=k}^{n−1}(m − 1)^{i−k}\binom{i − 1}{k − 1}c_{1}(n, i).

Next, we have

c_{m}(n, k) = (m − 1)^{n−k}\binom{n − 1}{k − 1}+

∑_{i=k}^{n−1} ∑_{j=0}^{i−1}(m − 1)^{i−k}a^{i−j}(a − 1)^{n−2i+j}\binom{i}{j}\binom{i − 1}{k − 1}\binom{n − i − 1}{i − j − 1}.

Explicit formula for f_{m}(n) may be obtained from (C).

The following arrays in Sloane [5] are related with this case: \underline{A154929}, \underline{A113413}, \underline{A054458}, \underline{A116412}.

Let a be a positive integer. Define f_{0} as follows:

f_{0}(1) = 1, f_{0}(2) = 0,
f_{0}(n + 2) = af_{0}(n), (n ≥ 1).

Proposition 9. For a > 0, the number f_{0}(n) is the number of words of length n − 1 over the alphabet {0, 1, …, a − 1} in which there are no runs of odd length.

Proof. Let d(n) denote the number of words of length n, which we wish to count. Firstly, d(0) = 1 since only the empty word has length 0. Next, d(1) = 0 as there are no runs of length 1. Assume that n > 2. A word of length n must begin with two identical letters. Hence, there are ad(n − 2) such words. We conclude that the following recurrence holds:

d(0) = 1, d(1) = 0, d(n) = ad(n − 2), (n ≥ 2),

which yields d(n − 1) = f_{0}(n), (n ≥ 1).

From (3), we easily obtain the following explicit formula for f_{0}:

f_{0}(n) = \begin{cases}0, & if n = 2t; \\ a^{t}, & if n = 2t + 1. \end{cases}

Using (B) yields

Corollary 10. For m ≥ 0, the following recurrence holds:

f_{m}(1) = 1, f_{m}(2) = m,
f_{m}(n + 2) = mf_{m}(n + 1) + af_{m}(n), (n ≥ 1).

Proposition 11. The number f_{m}(n) is the number of words of length n−1 over {0, 1, …, a− 1, …, a + m − 1}, such that letters 0, 1, …, a − 1 avoid runs of odd length.

Proof. We let d(n) denote the number of desired words of length n−1. It is clear that d(0) = 1 and d(1) = m. A word of length n + 1 may begin with a letter from {a, a + 1, …, a + m − 1}. There are md(n) such word. If a word begins with a letter from {0, 1, …, a − 1}, it must be followed by the same letter. Hence, there are ad(n − 1) such words. We conclude that d(n) = f_{m}(n + 1).

Some well-known classes of numbers satisfy the recurrence from Corollary 10. We give the appropriate combinatorial meaning for some of them.

1. The case a = 1, m = 1 concerns the Fibonacci numbers. The number of binary words of length n − 1 in which 0 avoids a run of odd length is F_{n}.

2. The case a = 1, m = 2 concerns the Pell numbers P_{n} ( \underline{A000129}). The number of ternary words of length n − 1 in which 0 avoids runs of odd length is P_{n}.

3. The case a = 2, m = 1 concerns the Jacobsthal numbers J_{n} (\underline{A001045}). The number of ternary words of length n − 1 in which 0 and 1 avoid runs of odd length is J_{n}.

From the combinatorial interpretation, we easily derive an explicit formula for f_{m}(n).

Proposition 12. We have

f_{m}(n) = ∑_{j=0}^{⌊ \frac{n−1}{2} ⌋} m^{n−2j−1}a^{j}\binom{n − 1 − j}{j}.

Proof. According to Proposition 11, in a word counted by f_{m}, the letters from {0, 1, …, a−1} may appear only in pairs. There are a such pairs. We may choose j, (0 ≤ j ≤ ⌊\frac{n−1}{2}⌋) pairs in a word of length n−1. These j pairs may be chosen in \binom{n−j−1}{j} ways. When we have chosen j pairs from {0, 1, …, a−1}, the remaining n−1−2j letters are from {a, a+1, …, a+m−1}, which are m in number.

As a consequence, we obtain the following similar explicit formulas for the Fibonacci, Pell and Jacobsthal numbers:

F_{n} = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{n − j − 1}{j}, P_{n} = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} 2^{n−2j−1}\binom{n − j − 1}{j},

J_{n} = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} 2^{j}\binom{n − j − 1}{j}.

From (F), we obtain

Proposition 13. The number c_{m}(n, k) is the number of words of length n − 1 over the alphabet {0, 1, …, a − 1, …, a + m − 1} in which the letter a + m − 1 appears k − 1 times, and letters from {0, 1, …, a − 1} avoid runs of odd length.

We now derive an explicit formula for c_{1}(n, k).

Proposition 14. The following equation holds:

c_{1}(n, k) = \begin{cases}a^{\frac{n−k}{2}} \binom{\frac{n+k}{2} −1}{k−1}, & if n − k is even; \\ 0, & if n − k is odd . \end{cases}

Proof. Each term in (1) in which i_{t} is even equals zero. Hence, (1) becomes

c_{1}(n, k) = ∑_{2j_{1}+1+2j_{2}+1+···+2j_{k}+1=n} a^{j_{1}} · a^{j_{2}} ⋯ a^{j_{k}}

= a^{\frac{n−k}{2}} ∑_{s_{1}+s_{2}+···+s_{k}= \frac{n+k}{2}} 1 = a^{\frac{n−k}{2}} \binom{\frac{n+k}{2} − 1}{k − 1}.

Note that the last sum is over positive s_{1}, s_{2}, …, s_{k}.

As a consequence of (D), we obtain the following explicit formulas for the Fibonacci and Jacobsthal numbers:

F_{2n} = ∑_{k=1}^{n} \binom{n + k − 1}{n − k}, F_{2n−1} = ∑_{k=1}^{n} \binom{n + k − 2}{n − k},

J_{2n} = ∑_{k=1}^{n} 2^{n−k}\binom{n + k − 1}{n − k}, J_{2n−1} = ∑_{k=1}^{n} 2^{n−k}\binom{n + k − 2}{n − k}.

Furthermore, we derive an explicit formula for c_{2}(n, k). Using (E), for even n, we obtain

c_{2}(2n, k) = ∑_{i=k}^{2n} \binom{i − 1}{k − 1}c_{1}(2n, i) = ∑_{j=⌈ \frac{k}{2} ⌉}^{n} \binom{2j − 1}{k − 1}c_{1}(2n, 2j)

= ∑_{j=⌈ \frac{k}{2} ⌉}^{n} a^{n−j}\binom{2j − 1}{k − 1}\binom{n + j − 1}{n − j}.

For odd n, we have

c_{2}(2n − 1, k) = ∑_{i=k}^{2n−1} \binom{i − 1}{k − 1}c_{1}(2n, i) = ∑_{j=⌈ \frac{k+1}{2} ⌉}^{n} \binom{2j − 2}{k − 1}c_{1}(2n − 1, 2j − 1)

= ∑_{j=⌈ \frac{k+1}{2} ⌉}^{n} a^{n−j}\binom{2j − 2}{k − 1}\binom{n + j − 2}{n − j}.

In particular, for a = 1, we obtain the following formulas for Pell numbers:

P_{2n} = ∑_{k=1}^{2n} ∑_{j=⌈ \frac{k}{2} ⌉}^{n} \binom{2j − 1}{k − 1}\binom{n + j − 1}{n − j},

P_{2n−1} = ∑_{k=1}^{2n−1} ∑_{j=⌈ \frac{k+1}{2} ⌉}^{n} \binom{2j − 2}{k − 1}\binom{n + j − 2}{n − j}.

Remark 15. Using (E), we easily obtain an explicit formula for c_{m}(n, k).

The following arrays in [5] are related with this case: \underline{A000129},\underline{A001045},\underline{A168561}, \underline{A037027}, \underline{A054456}, \underline{A132964}, \underline{A073370}.

Let a > b > 0 be integers. We define f_{0} by the following recurrence:

f_{0}(1) = 1, f_{0}(2) = a,
f_{0}(n + 2) = af_{0}(n + 1) − bf_{0}(n), (n ≥ 1).

Proposition 16. The number f_{0}(n) is the number of words of length n − 1 over the alphabet {0, 1, …, a}, avoiding subwords of the form: 0i, (i = 1, …, b).

Proof. We let d(n) denote the number of words of length n − 1. Firstly, d(0) = 1, since only the empty word has length 0. Next, d(1) = a, since there are no restrictions on words of length 1. Assume that n > 1. We have a · d(n − 1) words beginning with arbitrary letter. From this number, we must subtract words which begin with subwords 0i, (i = 1, 2, …, b). Hence, d(n) satisfies the same recurrence as f_{0}(n).

Example 17. 1. If a = 2, b = 1, we have

f_{0}(1) = 1, f_{0}(2) = 2,
f_{0}(n + 2) = 2f_{0}(n + 1) − f_{0}(n), (n ≥ 1),

which yields that f_{0}(n) = n. Hence, n is the number of binary words of length n − 1 avoiding subword 01, which is obvious.

2. If a = 3, b = 1, we have

f_{0}(1) = 1, f_{0}(2) = 3,
f_{0}(n + 2) = 3f_{0}(n + 1) − f_{0}(n), (n ≥ 1),

which is a well-known recurrence for the Fibonacci numbers F_{2n}.

We thus obtain the following combinatorial interpretation of the bisection of the Fiboncci numbers.

Corollary 18. The number of ternary words of length n − 1 avoiding 01 is F_{2n}.

We consider the particular case a = b + 1.

Corollary 19. If b > 1 and a = b + 1, then

f_{0}(n) = \frac{b^{n} − 1}{b − 1}.

Proof. We denote \frac{b^{n}−1}{b−1} by g_{0}(n). We have g_{0}(1) = 1, g_{0}(2) = 1 + b = a. Further,

(b + 1) · g_{0}(n + 1) − b · g_{0}(n) = (b + 1) · \frac{b^{n+1} − 1}{b − 1} − b · \frac{b^{n} − 1}{b − 1} = \frac{b^{n+2} − 1}{b − 1}.

By induction, we conclude that g_{0} = f_{0}.

In particular, for a = 3, b = 2, we have f_{0}(n) = 2^{n} − 1, which yields

Corollary 20. The Mersenne number 2^{n} − 1 is the number of ternary words of length n − 1 avoiding 01 and 02.

Using (B), we obtain

f_{m}(1) = 1, f_{m}(2) = m + a,
f_{m}(n + 2) = (a + m)f_{m}(n + 1) − bf_{m}(n), (n ≥ 1).

This means that f_{m} counts the same sort of words as f_{0}, with m + a instead of a.

Using (F) and (D), we obtain the following combinatorial interpretations of c_{m}(n, k) and f_{m}(n).

Corollary 21. 1. The number c_{m}(n, k) is the number of words of length n − 1 over {0, 1, …, b − 1, b …, m + a − 1} having exactly k − 1 letters equal m + a − 1 and avoiding subwords 0j, (j = 1, 2, …, b).

2. The number f_{m}(n) is the number of words of length n−1 over the alphabet {0, 1, …, b− 1, b …, m + a − 1} and avoiding subwords 0j, (j = 1, 2, …, b).

We next derive an explicit formula for c_{1}(n, k). A generating function for the sequence f_{0}(1), f_{0}(2), … is \frac{1}{bx^{2}−ax+1}. According to [4, Equation (1)], we have

\frac{x^{k}}{(bx^{2} − ax + 1)^{k}} = ∑_{n=k}^{∞} c_{1}(n, k)x^{k}.

The numbers α = \frac{a+\sqrt{a^{2}−4b}}{2b} and β = \frac{a−\sqrt{a^{2}−4b}}{2b} are the solutions of the equation bx^{2} −ax+1 = 0. We thus obtain

Proposition 22. The following equation holds:

c_{1}(n, k) = \frac{1}{b^{k}} ∑_{j=0}^{n−k} \frac{1}{α^{j+k}β^{n−j}} \binom{n − j − 1}{k − 1}\binom{k + j − 1}{k − 1}.

Proof. We expand \frac{x^{k}}{b^{k}(α−x)^{k}(β−x)^{k}} into powers of x. Since

\frac{1}{(γ − x)^{k}} = ∑_{i=0}^{∞} \binom{k + i − 1}{k − 1}\frac{x^{i}}{γ^{i+k}} ,

we easily obtain

\frac{x^{k}}{b^{k}(α − x)^{k}(β − x)^{k}} = ∑_{i=0}^{∞} [∑_{j=0}^{i} \frac{1}{b^{k}α^{j+k}β^{i−j+k}} \binom{k + j − 1}{k − 1}\binom{k + i − j − 1}{k − 1}] x^{i+k},

and the statement follows by replacing i by n − k.

In the case a = b + 1, we have α = 1 and β = \frac{1}{b}. Therefore, the following formula holds:

c_{1}(n, k) = ∑_{i=0}^{n−k} b^{n−k−i}\binom{n − i − 1}{k − 1}\binom{k + i − 1}{k − 1}.  (2)

Using (1), we obtain the following identity:

Identity 23.

∑_{i_{1}+i_{2}+···+i_{k}=n} [∏_{t=1}^{k}(b^{i_{t}} − 1)] = ∑_{i=0}^{n−k} b^{n−k−i}\binom{n − i − 1}{k − 1}\binom{k + i − 1}{k − 1},

where i_{t} > 0, (t = 1, 2, …, k).

Remark 24. Using (D) and (E), we obtain explicit formulas for f_{m}(n) and c_{m}(n, k).

The following arrays in [5] are related with this case: \underline{A078812}, \underline{A125662}, \underline{A207823}, \underline{A207824}, \underline{A110441}, \underline{A116414}.

5 Case 4

We let R_{4} denote the condition given in this case. We first solve the problem for binary words.

Proposition 25. Let f_{0}(n) be the number of binary words satisfying R_{4}. Then,

f_{0}(1) = 1, f_{0}(2) = 0,
f_{0}(n + 2) = f_{0}(n + 1) + f_{0}(n), (n > 1).
f_{0}(n) = F_{n−2}, (n > 1).

Proof. We have f_{0}(1) = 1, since the empty word has length 0. Next, f_{0}(2) = 0, since no words of length 1 satisfy R_{4}. Also, f_{0}(3) = 1, since 10 is the only word of length 2 satisfying R_{4}. Next, f_{0}(4) = 1, since 100 is the only word of length 3 satisfying R_{4}. Assume that n > 1. Then,

f_{0}(n + 4) = f_{0}(n + 2) + f_{0}(n + 1) + ⋯,

since a word of length greater than 3 must begin with a subword of the form 10 … 0. Analogously, we obtain

f_{0}(n + 5) = f_{0}(n + 3) + f_{0}(n + 2) + · · · .

Comparing these two equations, we get

f_{0}(n + 5) = f_{0}(n + 4) + f_{0}(n + 3).

The explicit formula follows from the preceding recurrence.

Since f_{0}(1) = 1, and so f_{m}(1) = 1, using (D) and (F), we obtain the following combinatorial interpretations of f_{m} and c_{m}(n, k).

Corollary 26. 1. The number c_{m}(n, k) is the number of words of length n − 1 over {0, 1, …, m + 1} having k − 1 letters equal m + 1 and satisfying R_{4}.

2. The number f_{m}(n) is the number of words of length n−1 over the alphabet {0, 1, …, m+ 1} satisfying R_{4}.

We next derive an explicit formula for c_{1}(n, k). It is known that c_{1}(n, k) is the coefficient of x^{n} in the expansion of (∑_{i=1}^{∞} F_{i−2}x^{i})^{k} into powers of x.

We consider the following auxiliary initial function:

\overline{f}_{0}(1) = 0, \overline{f}_{0}(n) = 1, (n > 1).

From [2, Proposition 23], we obtain \overline{f}_{1}(n) = F_{n−1}. It is proved in [3, Proposition 13] that

\overline{c}_{1}(n, k) = \binom{n − k − 1}{k − 1}, (k = 1, 2, …, ⌊\frac{n}{2}⌋) ,

and \overline{c}_{1}(n, k) = 0 otherwise.

Using (E) yields

\overline{c}_{2}(n, k) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ i=k \end{matrix} \binom{i − 1}{k − 1}\binom{n − i − 1}{i − 1}.

Hence,

(∑_{i=1}^{∞} F_{i−1}x^{i})^{k} = ∑_{n=k}^{∞} \overline{c}_{2}(n, k)x^{n}.  (3)

We let X denote ∑_{i=1}^{∞} F_{i−1}x^{i}. We have to expand the expression Y^{k}, where Y = ∑_{i=1}^{∞} F_{i−2}x^{i}. Since F_{−1} = 1, we have that Y = x(1 + X), which yields

Y^{k} = x^{k} (1 + ∑_{i=1}^{k} \binom{k}{i}X^{i})^{k} = ∑_{n=k}^{∞} c_{1}(n, k)x^{n}.

Using the binomial theorem and (3) yields

Y^{k} = x^{k} + ∑_{i=1}^{k} ∑_{j=i}^{∞} \binom{k}{i}\overline{c}_{2}(j, i)x^{j+k}.

For j+k = n, the coefficient of x^{n} on the right-hand side of this equation equals ∑_{i=1}^{k} \binom{k}{i}\overline{c}_{2}(n− k, i). We thus obtain Proposition 27. The following equations hold:

c_{1}(n, n) = 1,

c_{1}(n, k) = ∑_{i=1}^{k} \begin{matrix}⌊ & \frac{n−k}{2} & ⌋ \\ ∑ \\ j=i \end{matrix} \binom{k}{i}\binom{j − 1}{i − 1}\binom{n − k − j − 1}{j − 1}, (n > k).

Proposition 28. We have

c_{1}(n, n) = 1,

c_{1}(n, k) = ∑_{t=1}^{k} \begin{matrix}⌊ & \frac{n−k}{2} & ⌋ \\ ∑ \\ j=t \end{matrix} \binom{k}{t}\binom{j − 1}{t − 1}\binom{n − k − j − 1}{j − 1}, (n > k).

Using (B), we easily obtain the following recurrence for f_{m}:

f_{m}(1) = 1, f_{m}(2) = m,

f_{m}(n + 2) = (m + 1)f_{m}(n + 1) − (m − 1)f_{m}(n).

We examine two particular cases. In the case m = 1, we obtain

f_{1}(1) = 1, f_{1}(2) = 1,

f_{1}(n + 2) = 2f_{1}(n + 1), (n > 1),

which implies

f_{1}(1) = f_{1}(2) = 1, f_{1}(n) = 2^{n−2}, (n > 2).

We thus obtain the following property of powers of 2. Corollary 29. For n ≥ 2, the number 2^{n−2} is the number of ternary words of length n − 1 satisfying R_{4}.

As a consequence, the following Euler-type identity holds: Identity 30. For n > 2, the number of binary words of length n−2 is the number of ternary words of length n − 1, in which 0 and 1 appear only in a run of the form 1i, where i is the run of zeros of length i ≥ 1.

From Propositions 28 and (D), we obtain the following identity for the Mersenne numbers: Identity 31.

2^{n−2} − 1 = ∑_{k=1}^{n} ∑_{i=1}^{k} \begin{matrix}⌊ & \frac{n−k}{2} & ⌋ \\ ∑ \\ j=i \end{matrix} \binom{k}{i}\binom{j − 1}{i − 1}\binom{n − k − j − 1}{j − 1}, (n > 2).

We now consider the case m = 2. We have

f_{2}(1) = 1, f_{2}(2) = 2,
f_{2}(n + 2) = 3f_{2}(n + 1) − f_{2}(n),

which is the recurrence for Fibonacci numbers F_{2n−1}. We thus have

Corollary 32. The Fibonacci number F_{2n−1} is the number of quaternary words of length n − 1 satisfying R_{4}.

Calculating values for c_{2}(n, k), we obtain an odious expression for F_{2n−1}.

Identity 33.

F_{2n−1} = ∑_{k=1}^{n} ∑_{i=k}^{n} ∑_{t=0}^{i} \begin{matrix}⌊ & \frac{n−i}{2} & ⌋ \\ ∑ \\ j=t \end{matrix} \binom{i − 1}{k − 1}\binom{i}{t}\binom{j − 1}{t − 1}\binom{n − i − j − 1}{j − 1}.

Remark 34. Using (E) and (D), we obtain the explicit formulas for c_{m}(n, k) and f_{m}(n).

The following arrays in [5] are related with this case: \underline{A105422}, \underline{A105306}, \underline{A062110}, \underline{A188137}.

6 Case 5

We let R_{5} denote the given condition. Again, we first consider the binary words.

Proposition 35.

f_{0}(1) = 1, f_{0}(2) = 0, f_{0}(3) = 1.
f_{0}(n + 3) = f_{0}(n + 1) + f_{0}(n), (n ≥ 1).  (4)

We have f_{0}(n) = p_{n+2}, where p_{n} is the nth Padovan number (\underline{A000931}).

Proof. It is easy to see that the initial conditions are fulfilled. A word of length n + 2 begins with either two zeros or three ones and (4) follows.

Since (4) is the recurrence for the Padovan numbers, the second statement is true.

This means that the Padovan number p_{n+2} is the number of binary words of length n − 1 in which 0 appears in runs of even length, while 1 appears in runs, the lengths of which are divisible by 3. This is equivalent to the fact that the Padovan numbers count the compositions into parts 2 and 3, which is known fact (see comment of \underline{A000931}).

Corollary 36. 1. The function f_{m} satisfies the following recurrence:

f_{m}(1) = 1, f_{m}(2) = m, f_{m}(3) = m^{2} + 1,
f_{m}(n + 3) = mf_{m}(n + 2) + f_{m}(n + 1) + f_{m}(n), (n > 1).

2. Then, c_{m}(n, k) is the number of words of length n − 1 over {0, 1, …, m + 1} having k − 1 letters equal to m + 1, and satisfying R_{5}.

3. Then, f_{m}(n) is the number of words of length n − 1 over {0, 1, …, m + 1} satisfying R_{5}.

Proof. The claim 1. easily follows from (A). The claims 2. and 3. follow from (F) and (D).

We add a short combinatorial proof for 2. Equation f_{m}(1) = 1 means that the empty word satisfies R_{5}. Further, f_{m}(2) = m means that a word of length 1 may consist of any letter except 0 and 1. Next, f_{m}(3) = m^{2} + 1 means that a word of length 2 may consist of pairs from {2, 3, …, m + 1}, which are m^{2} in number, plus the word 00. Finally, a word of length n > 2 may begin with any letter from {2, 3, …, m + 1}, or from 00, or from 111.

The case m = 1 in Corollary 36 is the recurrence for Tribonacci numbers. Hence,

Corollary 37. The sequence 1, 1, 2, 4, 7, … of the Tribonacci numbers is the invert transform of the sequence 1, 0, 1, 1, 1, 2, … of the Padovan numbers.

Also, Tribonacci numbers count ternary words satisfying R_{5}.

Finally, we calculate c_{1}(n, k). We define the arithmetic function \overline{f}_{0} such that \overline{f}_{0}(2) = \overline{f}_{0}(3) = 1, and \overline{f}_{0}(n) = 0 otherwise. It is proved in [3, Propositon 5] that \overline{c}_{1}(n, k) = \binom{k}{n−2k}.

\overline{f}_{1}(1) = 0, \overline{f}_{1}(2) = 1, \overline{f}_{1}(3) = 1,
\overline{f}_{1}(n + 3) = \overline{f}_{0}(n + 1) + \overline{f}_{0}(n).

This implies that \overline{f}_{1}(n) = f_{0}(n − 1), (n > 1). The sequence f_{0}(1), f_{0}(2), … is thus obtained by inserting 1 at the beginning of the sequence \overline{f}_{1}(1), \overline{f}_{1}(2), . . ..

Using (E), we obtain

\overline{c}_{2}(n, k) = ∑_{i=k}^{n} \binom{i − 1}{k − 1} · \binom{i}{n − 2 · i},

which yields

(∑_{i=1}^{∞} \overline{f}_{1}(i)x^{i})^{k} = ∑_{n=k}^{∞} \overline{c}_{2}(n, k)x^{n}.  (5)

To obtain an explicit formula for c_{1}(n, k), we need to expand the expression X given by X = (∑_{i=1}^{∞} f_{0}(i)x^{i})^{k} into powers of x. We have

X = (x + ∑_{i=2}^{∞} f_{0}(i)x^{i})^{k} = (x + xY)^{k},

where Y = ∑_{i=1}^{∞} \overline{f}_{1}(i)x^{i}. Hence,

X = x^{k} ∑_{i=0}^{k} \binom{k}{i}Y^{i}.

Applying Equation(5) yields

X = ∑_{i=0}^{k} \binom{k}{i} ∑_{j=i}^{∞} \overline{c}_{2}(j, i)x^{j+k}.

Taking n = j + k, we get

Proposition 38. The following formulas hold:

c_{1}(n, n) = 1,

c_{1}(n, k) = ∑_{i=0}^{k} ∑_{j=i}^{n−k} \binom{k}{i}\binom{j − 1}{i − 1}\binom{j}{n − k − 2j}, (k < n).

In particular, the following identity for the Tribonacci numbers T_{n} holds:

Identity 39.

T_{n} = 1 + ∑_{k=1}^{n−1} ∑_{i=0}^{k} ∑_{j=i}^{n−k} \binom{k}{i}\binom{j − 1}{i − 1}\binom{j}{n − k − 2j}.

Remark 40. Using (E) and (D), we obtain explicit formulas for c_{m}(n, k) and f_{m}(n). The following arrays in Sloane [5] are related with this case: \underline{A104578}, \underline{A104580}.

7 Acknowledgment

I would like to thank the referee for a very careful reading of the manuscript and several useful suggestions.

References

[1] D. Birmajer, J. B. Gil, and M. D. Weiner, On the enumeration of restricted words over a finite alphabet, J. Integer Seq. 19 (2016), Article 16.1.3.

[2] M. Janjić, On linear recurrence equation arising from compositions of positive integers, J. Integer Seq. 18 (2015), Article 15.4.7.

[3] M. Janjić, Binomial coefficients and enumeration of restricted words, J. Integer Seq. 19 (2016), Article 16.7.3.

[4] M. Janjić, Some formulas for numbers of restricted words, J. Integer Seq. 20 (2017), Article 17.6.5.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 11B39. Keywords: restricted word, linear recurrence equation, Fibonacci number.

(Concerned with sequences: \underline{A001045}, \underline{A00129}, \underline{A000931}, \underline{A037027}, \underline{A054456}, \underline{A054458}, \underline{A062110}, \underline{A073370}, \underline{A078812}, \underline{A104578}, \underline{A104580}, \underline{A105306}, \underline{A105422}, \underline{A110441}, \underline{A113413}, \underline{A116412}, \underline{A116414}, \underline{A125662}, \underline{A132964}, \underline{A154929}, \underline{A168561}, \underline{A188137}, \underline{A207823}, \underline{A207824}.)