Words and Linear Recurrences

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

                        agnus@blic.net

Abstract

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

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

1 Introduction

We continue the investigation of restricted word enumeration from previous papers Janji¸ [2, 3, 4], where functions f_{m} and c_{m} were defined as follows. For an initial arithmetic function f_{0} and m ≥ 1, the function f_{m} 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 integers 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 the value of f_{m−1}(i) is the weight of i, then the value of f_{m}(n) is the number of weighted compositions of n, and the value of c_{m}(n, k) is the number of weighted compositions of n into k parts.

In [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 consider the reverse problem. For each of the five types of restricted words, we first find the initial function f_{0} which counts these words. We then derive formulas for f_{m} and c_{m} and give their combinatorial meanings in term of restricted words.

To begin with, we restate the results from papers [2, 3, 4] that we will use in this work.

(A) [2, Theorem 6] Let f_{0} be an arithmetic function and let k be a positive integer. Assume that 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),

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,
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 that 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, the value of 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 proceed to 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 (Property P_{1}).

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

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

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 (Property P_{4}).

5. Words over {0, 1, …} in which 0 appears only in a run of even length, and 1 appears only in a run of a length divisible by 3 (Property P_{5}).

We also note that, in all types, the initial function f_{0} is defined by a linear homogenous recurrence.

2 Type 1

In this case, 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 value of f_{0}(n) is the number of words of length n−1 over {0, 1, …, a−1} satisfying P_{1}.

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 the following result.

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 counted by f_{m}.

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

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. At the front of such a word, we insert a letter different from the first letter of the word. In this way, we obtain all the words of length n + 2 beginning with two different letters. The remaining words must begin with two identical 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, the value of 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 the following result.

Proposition 6. 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 which satisfy P_{1} equals the value of c_{m}(n, k).

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} a^{k−i}(a − 1)^{n−2k+i}\binom{k}{i}\binom{n − k − 1}{k − i − 1}, (k < n).

Proof. From (1), we first 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. Then we have

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}.  (2)

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

We use (E) to derive an explicit formula for c_{m}(n, k). Extracting the term for i = n yields

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).

Using (2), we obtain

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}.

An explicit formula for f_{m}(n) can easily be obtained from (C).

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

Let a be a positive integer. Define f_{0} by

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

Proposition 9. For a > 0, the value of f_{0}(n) is the number of words of length n − 1 over the alphabet {0, 1, …, a − 1} satisfying P_{2}.

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),  (3)

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}  (4)

Using (B), we obtain the following result.

Corollary 10. For m ≥ 0, we have

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

Proposition 11. The value of f_{m}(n) is the number of words of length n−1 over {0, 1, …, a− 1, …, a + m − 1} which satisfy P_{2}.

Proof. We let d(n) denote the number of 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 words. If a word begins with a letter from {0, 1, …, a−1}, the second letter must be the same. Hence, there are ad(n − 1) such words. We conclude that next 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 the Fibonacci, the Pell, and the Jacobhstal numbers.

1. The case a = 1, m = 1 is related to 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 is related to 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 is related to 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}.  (5)

Proof. A word of length n−1 can contain 2j letters from {0, 1, …, a−1}, so that each letter appears in a run of even length, where 0 ≤ j ≤ ⌊\frac{n−1}{2}⌋. The remaining n − 1 − 2j places are filled by letters from \{a, a + 1, …, a + m − 1\} arbitrarily. For a fixed j, we have a^{j} · \binom{n−j−1}{j} subwords from {0, 1, …, a−1} and m^{n−1−2j} subwords from {a, a+1, …, a+m−1}. Summing over j, we obtain (5).

As a consequence, we obtain the following explicit formulas for the Fibonacci, the Pell, and the 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 the following result.

Proposition 13. The value of 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 which satisfy P_{2}.

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

Proposition 14. The following formula 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. According to (4), each term in formula (1) equals zero if some i_{t} is even. 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 integers s_{1}, s_{2}, …, s_{k}.

As a consequence of (D), we obtain the following explicit formulas for the Fibonacci and the 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}.

Now, we derive an explicit formula for c_{2}(2n, k). Using (E), 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}.

Furthermore,

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 the 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 to this type: \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

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

Proposition 16. The value of f_{0}(n) is the number of words of length n−1 over {0, 1, …, a} satisfying P_{3}.

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

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 f_{0}(n) = n. Hence, n is the number of binary words of length n−1 avoiding 01, for obvious reasons.

2. If a = 3, b = 1, we have the well-known recurrence for the Fibonacci numbers F_{2n}:

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

Thus, we obtain the following combinatorial interpretation of the bisection of the Fibonacci numbers.

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

We now consider the case when 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. Furthermore,

(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 the following result.

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 value of c_{m}(n, k) is the number of words of length n − 1 over {0, 1, …, b − 1, b …, m + a − 1} having k − 1 letters equal m + a − 1 which satisfy P_{3}.

2. The value of f_{m}(n) is the number of words of length n−1 over the alphabet {0, 1, …, b− 1, b …, m + a − 1} which satisfy P_{3}.

Next, we 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.

Proposition 22. The following equality 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 with 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}.  (6)

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}, (t = 1, 2, …, k) are positive integers.

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 to this type: \underline{A078812}, \underline{A125662}, \underline{A207823}, \underline{A207824}, \underline{A110441}, \underline{A116414}.

5 Type 4

We solve the problem for binary words first.

Proposition 25. Let f_{0}(n) be the number of binary words of length n − 1 satisfying P_{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 only the empty word has length 0. Next, f_{0}(2) = 0, since no words of length 1 satisfy P_{4}. Also, f_{0}(3) = 1, since 10 is the only word of length 2 satisfying P_{4}. Next, f_{0}(4) = 1, since 100 is the only word of length 3 which satisfies P_{4}. Assume that n > 1. Then,

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

since the 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 equalities, 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 value of 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 P_{4}.

2. The value of f_{m}(n) is the number of words of length n−1 over the alphabet {0, 1, …, m+ 1} which satisfy P_{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) implies

\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}.  (7)

Let X denote ∑_{i=1}^{∞} F_{i−1}x^{i}. We expand the expression Y^{k}, where Y = ∑_{i=1}^{∞} F_{i−2}x^{i}. Since F_{−1} = 1, we have 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 (7) 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 is ∑_{i=1}^{k} \binom{k}{i}\overline{c}_{2}(n − k, i).

Proposition 27. 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

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).

Thus we obtain the following property of powers of 2. Corollary 28. For n ≥ 2, the number 2^{n−2} is the number of ternary words of length n − 1 which satisfy P_{4}.

As a consequence, the following Euler-type identity holds. Identity 29. For n > 2, the number of binary words of length n − 2 equals 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 27 and (D), we obtain the following identity for the Mersenne numbers. Identity 30.

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 the Fibonacci numbers F_{2n−1}.

Corollary 31. The number F_{2n−1} is the number of quaternary words of length n − 1 which satisfy P_{4}.

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

Identity 32.

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 33. 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 to this type: \underline{A105422}, \underline{A105306}, \underline{A062110}, \underline{A188137}.

6 Type 5

Again, we consider binary words first.

Proposition 34. The following recurrence holds:

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).

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 satisfied. A word of length n+2 begins with either two zeros or three ones and the recurrence follows.

Since we have a 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 of lengths divisible by 3. This is equivalent to the fact that the Padovan numbers count the compositions into parts 2 and 3 (see the comment in \underline{A000931}).

Corollary 35. 1. The function f_{m} satisfies

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. The value 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 P_{5}.

3. The value f_{m}(n) is the number of words of length n − 1 over {0, 1, …, m + 1} which satisfy P_{5}.

Proof. Claim 1 follows from (A) easily. Claims 2 and 3 follow from (F) and (D).

We add a short combinatorial proof of 2. Equality f_{m}(1) = 1 means that the empty word satisfies P_{5}. Furthermore, 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 with 00, or with 111.

The case m = 1 in Corollary 35 is the recurrence for Tribonacci numbers.

Corollary 36. 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, the Tribonacci numbers count ternary words satisfying P_{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}, and

\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 implies

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

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 (8) implies

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

Taking n = j + k, we get the following result. Proposition 37. 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, we have the following identity for the Tribonacci numbers. Identity 38.

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 39. 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 to this type: \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 Sequences 19 (2016), Article 16.1.3.

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

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

[4] M. Janjić, Some formulas for numbers of restricted words, J. Integer Sequences 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{A000129}, \underline{A000931}, \underline{A001045}, \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}, and \underline{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.