Pascal Matrices and Restricted Words

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 examined two functions f_{m} and c_{m}, related to the enumeration of restricted words over a finite alphabet. The definitions of these functions depend on an initial arithmetic function f_{0} taking nonnegative integer values. In this paper, we consider four types of initial functions, the values of which are binomial coefficients. In particular, we give a new combinatorial interpretation of the figurate numbers.

1 Introduction

In the previous papers [3, 4], for an initial arithmetic function f_{0} having nonnegative integer values, we defined two functions f_{m} and c_{m} in the following way: The function f_{m} is the mth invert transform of f_{0}. The function c_{m}(n, k) is defined by

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)

We investigate the problem of enumeration of some words over a finite alphabet relating to these functions. In [3, 4], a number of results about restricted words enumeration is obtained. Since the problem may be reduced to enumeration of weighted compositions, other authors also obtained results of this kind, for instance [1, 2, 5].

We first restate some results from [3, 4], necessary for the present investigation:

(A) The following recurrence holds:

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

In particular, c_{m}(n, 1) = f_{m−1}(n).

(B) We consider the array c_{m}(n, k) as a lower triangular matrix of order n, which we denote by C_{m}(n). If L_{n} is the lower triangular Pascal matrix, then

C_{m}(n) = C_{1}(n) · L_{n}^{m−1}.

In other words, we have

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

(C) We have

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

(D) The following formula is true:

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

We consider four types of initial functions, the values of which are binomial coefficients. In the first case, the values are the binomial coefficients from a row of Pascal matrix. In the second case, they are from a column, that is, the figurate numbers. In these cases, we describe the restricted words counted by f_{m} and c_{m}, and derive explicit formulas for these functions. In the third case, the values of f_{0} are the central binomial coefficients. In the fourth case, we take f_{0}(n) = \binom{2n−1}{n}, (n ≥ 1).

Remark 1. In the last two cases, only the functions f_{1}, f_{2} and c_{1} will be investigated. Namely, we could not find a sequence in Sloane [7], generated by some of c_{m}, (m > 1) or f_{m}, (m > 2).

We investigate the following four types of restricted words:

1. Words in which the letters of particular subwords are arranged in increasing order.

2. Words in which particular subwords contain no rises.

3. Words in which each binary subword has an equal number of ones and zeros.

4. Words such that in each binary subword, the number of zeros exceeds the number of ones by 1.

We start with an extension of [4, Proposition 10]. Let 1 ≤ m, 1 ≤ k ≤ n be integers. Assume that f_{m−1}(n) is the number of words w_{n−1} of length d_{m−1}(n − 1) over the finite alphabet Ω having a property P. Assume next that the empty word has the property P. It follows that f_{m−1}(1) = 1 and d_{m−1}(0) = 0, since the empty word is the only word of length 0. Furthermore, let Δ be a finite alphabet such that Ω ∩ Δ = ∅.

We want to count the words of the form

w_{i_{1}−1}, x_{1}, w_{i_{2}−1}, x_{2}, …, w_{i_{k−1}−1}, x_{k−1}, w_{i_{k}−1},  (2)

where i_{1} + i_{2} + ⋯ + i_{k} = n. Next, x_{1}, x_{2}, …, x_{k−1} are words over Δ having a property Q, and its number is N(k − 1). From (1), we obtain the following result.

Proposition 2. The value of N(k − 1) · c_{m}(n, k) is the number of words of the form (2) and of length ∑_{t=1}^{k} d_{m−1}(i_{t} − 1) + k − 1.

Remark 3. If Δ consists of one letter, and if d_{m−1}(i_{t} − 1) = i_{t} − 1, for all t, then Proposition 2 becomes [4, Proposition 10]. Remark 4. Note that, in this case, a letter from Δ may occupy any position in a word (2).

We next consider the case when empty the word does not satisfy the property P. Hence, in sequence (2), there is no the empty word. We now count the words of the form

w_{i_{1}}, x_{1}, w_{i_{2}}, x_{2}, …, w_{i_{k−1}}, x_{k−1}, w_{i_{k}},  (3)

where the length of w_{i_{t}} is d_{m−1}(i_{t}) > 0. We have

Proposition 5. The value of N(k − 1) · c_{m}(n, k) is the number of words of the form (3) of length equal to the values of ∑_{t=1}^{k} d_{m−1}(i_{t}) + k − 1, where i_{1} + i_{2} + ⋯ + i_{k} = n.

Also, a letter x from Δ may appear only in the form w_{i}xw_{j}, where w_{i}, w_{j} are the words from Ω satisfying P.

2 Rows of Pascal matrix

For a fixed positive integer a, we want to count the number of words over the finite alphabet Ω = {0, 1, …, a − 1, …}, in which letters of each subword over {0, 1, …, a − 1} appear in increasing order. We denote this property by P_{1}. The values of the initial function f_{0} are given by the binomial coefficients from the ath row of the Pascal matrix. Namely, if we define f_{0} by

f_{0}(n) = \binom{a}{n − 1}, (n = 1, 2, …),

then f_{0}(n) is the number of words of length n − 1 over {0, 1, …, a − 1} satisfying P_{1}. Since f_{0}(1) = 1 and the empty word satisfies P_{1}, we can use Proposition 2 to obtain the following results.

Proposition 6. Let m, n, k, a be integers such that a, m > 0 and 1 ≤ k ≤ n.

1. Let Δ be a finite alphabet such that Ω ∩ Δ = ∅. Assume that N(k − 1) is the number of words of length k − 1 over Δ satisfying a property Q_{1}. Then, N(k − 1) · c_{m}(n, k) is the number of words of the form (2), and of length n − 1 over Ω ∪ Δ.

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

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

Proposition 7. For integers a > 0 and 1 ≤ k ≤ n, we have

c_{1}(n, k) = \binom{ak}{n − k}.

Proof. We use induction on k. From (A), we obtain c_{1}(n, 1) = f_{0}(n), which means that the statement holds for k = 1. Suppose that the statement holds for k − 1, (k > 1). Using the recurrence (A) and the induction hypothesis, we obtain

c_{1}(n, k) = ∑_{i=1}^{n−k+1} \binom{a}{i − 1}\binom{ak − a}{n − i − k + 1},  (4)

and the statement follows by the Vandermonde convolution.

As a consequence of (B) and (C), we obtain the following explicit formulas for c_{m}(n, k) and f_{m}(n).

Corollary 8. For integers a > 0, m ≥ 1, and 1 ≤ k ≤ n, we have

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

f_{m}(n) = ∑_{i=1}^{n} m^{i−1}\binom{ia}{n − i}.

We illustrate our results with several particular cases which give new combinatorial interpretations for some known sequences of integers. The corresponding A-numbers in the On-line Encylopedia of Integer Sequences [7] are given at the end of each item.

Example 9. 1. For a = 2, the binomial coefficient \binom{2k}{n−k} is equal to the number of ternary words of length n − 1 having k − 1 letters equal to 2, and the letters of each binary subword are written in increasing order. \underline{A116088} (without the first column)

2. For a = 2, the value of ∑_{k=1}^{n} \binom{2k}{n−k} equals the number of ternary words of length n − 1, in which the letters of each binary subword are written in increasing order. \underline{A002478} (the bisection of the Narayana’s cows sequence)

3. For a = 3, the binomial coefficient \binom{3k}{n−k} is equal to the number of quaternary words of length n − 1 having k − 1 letters equal 3, and the letters in each ternary subword are written in increasing order. \underline{A116089}

4. For a = 3, the value of ∑_{k=1}^{n} \binom{3k}{n−k} equals the number of quaternary words in which the letters in each ternary subword are written in increasing order. \underline{A099234}

5. For a = 2, k = n − 2, n > 2, Δ = {2, 3}, 2^{n−3} · (2n^{2} − 9n + 10) is equal to the number quaternary words of length n − 1, in which n − 3 letters are either equal to 2 or 3, and the letters 0 and 1 are written in increasing order. \underline{A086950}

6. For a = 2, n ≥ 3, k = n − 2, N(k − 1) = k, (n − 2)^{2} · (2n − 3) is equal to the number of words of length n − 1 over {0, 1, 2, …, n} having n − 2 letters from 2, 3, …, n which are written in increasing order, as are the letters in each binary subword. \underline{A015237}

7. For a = 2, n ≥ 3, k = n − 2, N(k − 1) = k!, (n − 2)! · (2n − 5) is equal to the number of words of length n − 1 over {0, 1, 2, …, n + 1} having n − 2 letters from 2, 3, …, n, no two of them ere the same, and the letters of each binary subword are written in increasing order. \underline{A175925}

3 Columns of Pascal matrix

Let a be a positive integer. We say that a word over {0, 1, 2 …, a − 1} that has no rises has the property P_{2}. We examine the following problem: find the number of words of length n − 1 over the finite alphabet {0, 1, …, a − 1, …} such that subwords from {0, 1, …, a − 1} satisfy P_{2}. We show that the values of the initial function are figurate numbers, that is, the numbers forming columns of the Pascal matrix. We let d_{a}(n − 1) denote the number of such words of length n − 1.

Proposition 10. For positive integers a, n, the following formula holds:

d_{a}(n − 1) = \binom{n + a − 2}{a − 1}.  (5)

Proof. We first have d_{a}(0) = 1, since the empty word does not have a rise. Assume that n > 1. We have

d_{a+1}(n − 1) = d_{a}(n − 1) + d_{a+1}(n − 2), (n > 1).

Namely, if a word of length n − 1 over {0, 1, …, a − 1, a} having no rises begins with a letter from {0, 1, …, a − 1}, then the letter a can not appear in such a word. Hence, there are d_{a}(n − 1) such words. There remain the words of length n − 1 beginning with a. Obviously, there are d_{a+1}(n − 2) such words. It follows that

d_{a+1}(n − 1) − d_{a+1}(n − 2) = d_{a}(n − 1),
d_{a+1}(n − 2) − d_{a+1}(n − 3) = d_{a}(n − 2),
⋮
d_{a+1}(1) − d_{a+1}(0)  = d_{a}(1).

Adding the expressions on the left-hand sides, as well as those on the right-hand side, we obtain the following recurrence:

d_{a+1}(n − 1) = ∑_{i=1}^{n} d_{a}(i − 1).  (6)

To prove (5), we use induction on a. If a = 1, then d(n − 1, 1) = 1, since the alphabet consists of the empty word. Assume that the statement holds for a ≥ 1. Then, (6) takes the form

d_{a+1}(n − 1) = ∑_{i=1}^{n} \binom{i + a − 2}{a − 1},

and the statement holds according to the horizontal recurrence for the binomial coefficients.

Therefore, f_{0}(n) = \binom{n+a−2}{a−1}, (n = 1, 2, …). Since f_{0}(1) = 1, and the empty word satisfies P_{2}, we may use Proposition 2 to obtain the following result.

Proposition 11. Let m, n, k, a be integers such that a, m > 0 and 1 ≤ k ≤ n. The following assertions hold:

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

2. Consider the alphabets Ω = {0, 1, …, a + m − 1} and Δ = {a + m, a + m + 1, …, a + m+p−1}. Assume that N(k −1) is the number of words of length k −1 over Δ having a property Q_{2}. Then, the number of words of the form (2), of length n − 1, over Ω ∪ Δ, and satisfying P_{2}, and Q_{2} is equal to N(k − 1) · c_{m}(n, k).

To derive an explicit formula for c_{1}(n, k), we need the following binomial identity.

Identity 12. Let u ≥ v ≥ w ≥ 1 be integers. Then,

\binom{u}{v} = ∑_{i=w}^{u−v+w} \binom{i − 1}{w − 1}\binom{u − i}{v − w}.  (7)

Proof. We know that \binom{u}{v} is the number of binary words of length u having v zeros. We let i denote the position of the wth zero in a word, counting from left to right. It is clear that w ≤ i ≤ u − v + w. For a fixed i, the number of words is \binom{i−1}{w−1}\binom{u−i}{v−w}. Summing over all i, we obtain (7).

Note 13. The identity (7) generalizes the horizontal recurrence for binomial coefficients, which we obtain for either w = 1 or w = v.

Proposition 14. Let n, k, a be integers such that a > 0 and 1 ≤ k ≤ n. Then

c_{1}(n, k) = \binom{n + ak − k − 1}{ak − 1}.

Proof. We use induction on k. From (A), we have

c_{1}(n, 1) = f_{0}(n) = \binom{n + a − 2}{a − 1},

which means that the statement is true for k = 1. Using induction, we conclude that the statement is equivalent to the binomial identity

\binom{n + ak − k − 1}{ak − 1} = ∑_{i=1}^{n−k+1} \binom{i + a − 2}{a − 1}\binom{n + ak − k − a − i}{ak − a − 1}.

We prove that this identity follows from Identity 7. Namely, taking w + 1 instead of w and replacing i − 1 by j yields

\binom{u}{v} = ∑_{j=w}^{u−v+w} \binom{j}{w}\binom{u − j − 1}{v − w − 1}.

Then, taking w = a − 1 and replacing j by i + a − 2 implies

\binom{u}{v} = ∑_{i=1}^{u−v+1} \binom{i + a − 2}{a − 1}\binom{u − a − i + 1}{v − a}.

Finally, taking u = n + ak − k − 1, and v = ak − 1, we obtain the desired result.

Using (B) and (C), we obtain the following explicit formulas:

Proposition 15. Let m, n, k, a be integers such that a, m > 0 and 1 ≤ k ≤ n. We have

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

f_{m}(n) = ∑_{i=1}^{n} m^{i−1}\binom{n + ai − i − 1}{ai − 1}.

Note that the case a = 2 was considered in [4, Example 31]. We finish this section with a number of particular results.

Example 16. 1. For a = 3, m = 1, \binom{n+2k−1}{3k−1} is equal to the number of quaternary words of length n − 1 having k − 1 letters equal to 3, and avoiding 01, 02, and 12. \underline{A127893}

2. For a = 3, m = 1, ∑_{k=1}^{n} \binom{n+2k−1}{3k−1} is the number of quaternary words of length n − 1 avoiding 01, 02, 12. \underline{A052529}

3. For a = 3, m = 2, ∑_{i=1}^{n} 2^{i−1}\binom{n+2i−1}{3i−1} equals the number of words of length n − 1 over \{0, 1, 2, 3, 4\} avoiding 01, 02, and 12. \underline{A200676}

4. For a = 4, m = 1, the value of ∑_{k=1}^{n} \binom{n+3k−1}{4k−1} is equal to the number of words of length n − 1 over \{0, 1, 2, 3, 4\} such that subwords from \{0, 1, 2, 3\} have no rises. \underline{A055991}

5. For a = 5, m = 1, the value ∑_{k=1}^{n} \binom{n+4k−1}{5k−1} is equal to the number of words of length n−1 over \{0, 1, 2, 3, 4, 5\} such that subwords from \{0, 1, 2, 3, 4\} have no rises. \underline{A079675}

4 Central binomial coefficients

In this section, we consider the problem of enumeration of words over a finite alphabet {0, 1, …} such that each binary subword has the same number of zeros and ones. We let P_{3} denote this property. If we define f_{0} by f_{0}(n) = \binom{2n−2}{n−1}, then f_{0}(n) is the number of binary words of length 2n − 2 having equal number of zeros and ones. The empty word satisfies P_{3}. Also, f_{0}(1) = 1, so we may apply Proposition 2. Hence, we count the words of the form (2). We have d_{0}(n − 1) = 2n − 2. Take Ω = {0, 1}. Let Δ = {2, 3, …} be a finite alphabet, and let N(k − 1) be the number of words of length k − 1 over Δ having a property Q_{3}. Taking x_{i}x_{i} instead of x_{i}, for all x_{i} ∈ Δ, we obtain the following results.

Proposition 17. Let n, k be integers such that 1 ≤ k ≤ n. We have

1. The number of words over Ω ∪ Δ of length 2n − 2 having k − 1 subwords of the form x_{i}x_{i} from Δ satisfying Q_{3}, and all binary subwords satisfy P_{3} is N(k − 1) · c_{1}(n, k).

2. The number of ternary words of length 2n − 2 in which 2 appears only in runs of even lengths, and all binary subwords satisfy P_{3} is equal to f_{1}(n).

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

Proposition 18. For integers 1 ≤ k ≤ n, we have

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

c_{1}(n, k) = \frac{2^{n−k}k(k + 2) ⋯ (2n − k − 2)}{(n − k)!}, (k < n).

Proof. It is well-known that g(x) = \frac{1}{\sqrt{1−4x}} is the generating function for the sequence

\{\binom{2n − 2}{n − 1} : n = 1, 2, …\} ,

of the central binomial coefficients.

According to (D), the formula follows by the use of the Taylor expansion for the binomial series.

Calculating c_{1}(n, 1), we obtain the following result.

Identity 19. For n ≥ 2 we have

n(n + 1) ⋯ (2n − 2) = 2^{n−1}(2n − 3)!!.

Remark 20. This identity is a solution to a problem posed in Amer. Math. Monthly [6].

In the case k = 2, we obtain the following convolution identity for the central binomial coefficients.

Identity 21. For n ≥ 0, we have

4^{n} = ∑_{i_{1}+i_{2}=n+2} \binom{2i_{1} − 2}{i_{1} − 1}\binom{2i_{2} − 2}{i_{2} − 1}.

Again, we finish the section with a few examples. We assume that all binary subwords satisfy P_{3}. Note that in the following examples, in all binary subwords the number of zeros is equal the number of ones.

Example 22. 1. The array c_{1}(n, k) is \underline{A054335}.

2. The number of ternary words of length 2n − 2 in which 2 appears in a run of even length only is equal to ∑_{k=1}^{n} c_{1}(n, k). \underline{A026671}

3. For n ≥ 2, 4^{n−2} is equal to the number of ternary words of length 2n − 2 containing one subword 22. \underline{A000302}

4. For n ≥ 3, \frac{2^{n−3}(2n−5)!!}{(n−3)!} is equal to the number of ternary words of length 2n−2 containing two subwords 22. \underline{A002457}

5. For n ≥ 4, (n − 3)4^{n−4} is equal to the number of ternary words of length 2n − 2 containing three subwords 22. \underline{A002697}

6. For n ≥ 3, the number 2(n − 2)n is equal to the number of ternary words of length 2n − 2 containing n − 3 subwords 22. \underline{A054000}

7. For n ≥ 3, 4c_{1}(n, 3) is equal to the number of quaternary words of length 2n−2 having 2 subwords as either 22 or 33. \underline{A002011}

5 Binomial coefficient \binom{2n−1}{n}

Our final example is the case when f_{0}(n) = \binom{2n−1}{n}, (n = 1, 2, …). Combinatorially, the value of f_{0}(n) is the number of binary words of length 2n−1 in which the number of ones is greater by 1 than the number of zeros. We denote this property by P_{4}. The empty word does not satisfy this condition. Hence, we count words of the form (3).

We define Ω = {0, 1}, and Δ = {2, 3, …}. Let N(k −1) be the number of words of length k − 1 over Δ satisfying a property Q_{4}. From the fact that d_{0}(n − 1) = 2n − 1, the following result follows.

Proposition 23. Let n, k be integers such that 1 ≤ k ≤ n. We have

1. The number of words over Ω∪Δ of length 2n−1, having k −1 letters from Δ satisfying Q_{4}, and all binary subwords satisfy P_{4} is equal to N(k − 1) · c_{1}(n, k).

Also, each letter from Δ is both preceded and followed by a binary subword satisfying P_{4}.

2. The value of f_{1}(n) is the number of ternary words of length 2n−1 in which 2 is preceded and followed by a binary subword satisfying P_{4}.

It is known that

g(x) = \frac{1}{2x\sqrt{1 − 4x}} − \frac{1}{2x}

is a generating function for the sequence f_{0}(1), f_{0}(2), . . .. To obtain an explicit formula for c_{1}(n, k), we use the expansion (D).

Using the binomial theorem and the expansion of the binomial series, we obtain

[xg(x)]^{k} = \frac{1}{2^{k}} ∑_{j=0}^{∞} (∑_{i=1}^{k}(−1)^{k−i}\binom{k}{i}i(i + 2) ⋯ (i + 2j − 2)) \frac{2^{j}}{j!} x^{j}.  (8)

Since k is the least power of x on the left-hand side of the equation, for n < k, we obtain the following identity.

Identity 24.

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

Proposition 25. Let n, k be integers such that 1 ≤ k ≤ n. Then

c_{1}(n, k) = \frac{2^{n−k}}{n!} ∑_{i=1}^{k}(−1)^{k−i}\binom{k}{i} · ∏_{j=0}^{n−1}(i + 2j).  (9)

We state several particular cases. For k = 1, we again obtain Identity 19. For k = 2, we have Identity 26. For n ≥ 1, we have

4^{n−1} = \binom{2n − 1}{n} + ∑_{i_{1}+i_{2}=n} \binom{2i_{1} − 1}{i_{1}}\binom{2i_{2} − 1}{i_{2}}.

Proof.

c_{2}(n, 2) = \frac{2^{n−2}}{n!} [∏_{j=0}^{n−1}(2 + 2j) − 2 ∏_{j=0}^{n−1}(1 + 2j)]

= \frac{2^{n−2}}{n!} [(2n)!! − 2(2n − 1)!!]

= \frac{2^{n−2}}{n!} · 2^{n} · n! − \frac{2^{n−1}(2n − 1)!!}{n!}

= 4^{n−1} − 2^{n−1} \frac{(2n − 1)!!}{n!}.

On the other hand, we have

2^{n−1} \frac{(2n − 1)!!}{n!} = 2^{n−1} \frac{(n − 1)!(2n − 1)!!}{(n − 1)!n!} = \frac{(2n − 2)!!(2n − 1)!!}{(n − 1)!n!}

= \frac{(2n − 1)!}{(n − 1)!n!} = \binom{2n − 1}{n}.

and the proof follows from (1).

Finally, for k = n, we have the following identity. Identity 27.

n! = ∑_{i=1}^{n}(−1)^{n−i}\binom{n}{i} · i · (i + 2) ⋯ (i + 2n − 2).

Note that in the following examples, in all binary subwords the number of zeros is greater than the number of ones by one. Example 28. 1. The array c_{1}(n, k) is \underline{A035324}.

2. The number of ternary words of length 2n−1 having one letters 2 preceded and followed by a binary word is equal to c_{1}(n, 2). \underline{A008549}

3. The number of ternary words of length 2n − 1 having two letters 2, both of which are preceded and followed by a binary word is equal to c_{1}(n, 3). \underline{A045720} 4. The number of ternary words of length 2n − 1 having three letters 2, all of which are

preceded and followed by a binary word is equal to c_{1}(n, 4). \underline{A045894}

5. The number of ternary words of length 2n − 1 having four letters 2, all of which are preceded and followed by a binary word is equal to c_{1}(n, 5). \underline{A035330}

6. The value of ∑_{k=1}^{n} c_{1}(n, k) is the number of ternary words of length 2n − 1 in which each 2 is preceded and followed by a binary word. \underline{A049027}

6 Acknowledgment

I would like to thank the referee for 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] V. E. Hoggatt and D. A. Lind, Fibonacci and binomial properties of weighted compositions, J. Combin. Theory 4 (1968), 121–124.

[3] M. Janjić, Words and linear recurrences, J. Integer Sequences 18 (2018), Article 18.1.4.

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

[5] L. Moser and E. L. Whitney, Weighted compositions, Canad. Math. Bull. 4 (1961), 39–43.

[6] C. D. Olds, Problem E 760, Amer. Math. Monthly 4 (1947), 108.

[7] N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://oeis.org.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 11B39. Keywords: restricted word, binomial coefficient, figurate number.

(Concerned with sequences \underline{A000302}, \underline{A002011}, \underline{A002457}, \underline{A002478}, \underline{A002697}, \underline{A008549}, \underline{A015237}, \underline{A026671}, \underline{A035324}, \underline{A035330}, \underline{A045720}, \underline{A045894}, \underline{A049027}, \underline{A052529}, \underline{A054000}, \underline{A054335}, \underline{A055991}, \underline{A079675}, \underline{A086950}, \underline{A099234}, \underline{A116088}, \underline{A116089}, \underline{A127893}, \underline{A175925}, and \underline{A200676}.)

Received March 3 2018; revised versions received May 10 2018; May 11 2018. Published in Journal of Integer Sequences, May 24 2018.

Return to Journal of Integer Sequences home page.