On the Enumeration of Restricted Words over a Finite Alphabet

Daniel Birmajer Department of Mathematics Nazareth College Rochester, NY 14618 USA

                   abirmaj6@naz.edu

Juan B. Gil and Michael D. Weiner Department of Mathematics and Statistics Penn State Altoona Altoona, PA 16601 USA

                     jgil@psu.edu
                     mdw8@psu.edu

Abstract

We present a method for the enumeration of restricted words over a finite alphabet. Restrictions are described through the inclusion or exclusion of suitable building blocks used to construct the words by concatenation. Our approach, which relies on the invert transform and its representation in terms of partial Bell polynomials, allows us to generalize and address in a systematic manner previous results in the subject.

1 Introduction

Motivated by a recent paper of Janjić [7], we examine the problem of enumerating words over a finite alphabet using the invert transform, partial Bell polynomials, and building blocks that allow us to effectively manage a wide variety of restrictions.

Recall that, given a sequence x = (x_{n}), its invert transform 𝒴 (x) = (y_{n}) is defined by

1 + ∑_{n=1}^{∞} y_{n}t^{n} = \frac{1}{1 − ∑_{n=1}^{∞} x_{n}t^{n}} ,

see, e.g., the paper by Cameron [5], and the work by Bernstein and Sloane [2]. In short, if X(t) = ∑_{n=1}^{∞} x_{n}t^{n} and Y (t) = ∑_{n=1}^{∞} y_{n}t^{n}, then

1 + Y (t) = \frac{1}{1 − X(t)}, and so Y (t) = \frac{X(t)}{1 − X(t)}.

This map is clearly invertible on the space of linear recurrence sequences with constant coefficients, and we have 𝒴 ^{m}(x) = \frac{1}{m}𝒴 (mx) for every m ∈ ℕ. Indeed, inductively, if Y_{m}(t) denotes the generating function of 𝒴 ^{m}(x), then

Y_{m}(t) = \frac{Y_{m−1}(t)}{1 − Y_{m−1}(t)} = \frac{\frac{X(t)}{1−(m−1)X(t)}}{1 − \frac{X(t)}{1−(m−1)X(t)}} = \frac{X(t)}{1 − mX(t)}.

The following statement is straightforward.

Lemma 1. For b ∈ ℕ, the invert transform of x_{n} = b^{n−1} is given by y_{n} = (b + 1)^{n−1}. Thus for n > 1, y_{n} counts the number of words of length n − 1 over the alphabet {0, 1, …, b}. Moreover, by applying the invert transform m times, we get that 𝒴 ^{m}(x) counts the words over the alphabet {0, 1, …, b + m − 1}.

Corollary 2. Let x = (x_{n}) be a sequence of nonnegative integers. If x_{n} ≤ b^{n−1} for all n ∈ ℕ, then the elements of 𝒴 ^{m}(x) count some restricted words over the alphabet {0, 1, …, b+m−1}.

This is clear since, if x_{n} ≤ w_{n} for every n, then (1 − ∑_{n=1}^{∞} x_{n}t^{n})^{−1} ≤ (1 − ∑_{n=1}^{∞} w_{n}t^{n})^{−1}.

For b = 1, several families of restricted words were considered by Janjić in [7, Prop. 20]. Consistent with op. cit., we let f_{m} denote the m-th invert transform of a given sequence f_{0}, i.e., f_{m} = 𝒴 ^{m}(f_{0}). In [7, Corollary 24, 28, and 33], Janjić discussed three examples in which f_{0} is a binary sequence. He posted the problem of finding, for an arbitrary sequence f_{0}, either a recurrence or an explicit formula for f_{m}(n) in terms of m and n, together with a description of the set of restricted words over the alphabet {0, 1, …, m} counted by f_{m}(n). He also discussed two instances in which the sequence f_{0} is not binary but satisfies a second order linear recurrence relation. For all these examples, Janjić gives recurrence relations for f_{m} obtained from the recurrence relation satisfied by f_{0}.

In this paper, we present a somewhat different method for the enumeration of restricted words that may be applied to a wide class of restrictions, see Section 2. Our approach relies on a family of building blocks that we utilize to construct words by concatenation, and on a representation of the invert transform in terms of partial Bell polynomials. We discuss several binary and nonbinary examples (Sections 3 and 4, respectively) and shed some light on the examples considered by Janjić [7]. For all of the examples discussed here, we give closed combinatorial expressions.

We finish the introduction by recalling that, by means of Faà di Bruno’s formula, the invert transform can be written in terms of partial Bell polynomials, see e.g. [4]. Indeed, if (y_{n}) is the invert transform of x = (x_{n}), then

y_{n} = ∑_{k=1}^{n} \frac{k!}{n!}B_{n,k}(1!x_{1}, 2!x_{2}, …) for n ≥ 1,  (1)

where B_{n,k} denotes the (n, k)-th partial Bell polynomial defined as

B_{n,k}(z_{1}, …, z_{n−k+1}) = ∑_{α∈π(n,k)} \frac{n!}{α_{1}!α_{2}! ⋯ α_{n−k+1}!} (\frac{z_{1}}{1!} )^{α_{1}} ⋯ (\frac{z_{n−k+1}}{(n − k + 1)!})^{α_{n−k+1}}

with π(n, k) denoting the set of multi-indices α ∈ ℕ_{0}^{n−k+1} such that α_{1} + α_{2} + ⋯ = k and α_{1} + 2α_{2} + 3α_{3} + ⋯ = n. For the basic properties of these polynomials, we refer to Comtet’s book [6, Section 3.3]. A large collection of Bell identities and convolution formulas is available throughout the literature, see e.g. [1, 3, 9].

From its definition, it is clear that B_{n,k} is homogeneous of degree k:

B_{n,k}(az_{1}, …, az_{n−k+1}) = a^{k}B_{n,k}(z_{1}, …, z_{n−k+1}).

Thus, since 𝒴 ^{m}(x) = \frac{1}{m}𝒴 (mx) for every m ∈ ℕ, we get from (1) that the terms y_{m,n} of the m-th invert transform of x = (x_{n}) can be written as

y_{m,n} = ∑_{k=1}^{n} \frac{k!}{n!}m^{k−1}B_{n,k}(1!x_{1}, 2!x_{2}, …) for n ≥ 1.

As we will illustrate in the next sections, this representation of 𝒴 ^{m} provides an effective tool to enumerate restricted words and leads to interesting combinatorial formulas.

2 Restricted words

For a fixed b ∈ ℕ we consider the following family of building blocks:

Let W_{b}(j) be the set of words of length j, starting with b, followed by j −1 letters from the alphabet {0, 1, …, b − 1}.

Observe that |W_{b}(j)| = b^{j−1}. Moreover, any word of length n over the alphabet {0, 1, …, b}, starting with b, can be made by unique concatenation of blocks in W_{b}(j) for j = 1, …, n.

Given b ∈ ℕ and a sequence f_{0} of nonnegative integers, let {U_{j}} be a fixed sequence of subsets U_{j} ⊆ W_{b}(j) such that |U_{j}| = f_{0}(j) for j = 1, 2, …, and let 𝒰_{b,n}(f_{0}) be the set of words of length n over the alphabet {0, 1, …, b}, starting with b, made by concatenation of blocks from U_{j} for j = 1, …, n. If f_{0}(j) = 0, no block from U_{j} is used.

Theorem 3. Let f_{0} be a sequence of nonnegative integers such that f_{0}(j) ≤ b^{j−1} for every j ∈ ℕ and some b ∈ ℕ. Then the sequence

f_{1}(1) = 1, f_{1}(n) = ∑_{k=1}^{n} \frac{k!}{n!}B_{n,k}(1!f_{0}(1), 2!f_{0}(2), …),

counts the number of words in 𝒰_{b,n}(f_{0}). Moreover, each term \frac{k!}{n!}B_{n,k}(1!f_{0}(1), 2!f_{0}(2), …) counts the number of such words made with exactly k blocks.

Proof. By definition, every word in 𝒰_{b,n}(f_{0}) can be written as a unique concatenation of blocks from a subset of W_{b}(j) with f_{0}(j) elements for j = 1, …, n. Any of these words must start with a block from W_{b}(j) for some j, followed by a word in 𝒰_{b,n−j}(f_{0}). Thus we have the recurrence relation

f_{1}(n) = ∑_{j=1}^{n} f_{0}(j)f_{1}(n − j) with f_{1}(0) = 1,

which at the level of generating functions implies

1 + ∑_{n=1}^{∞} f_{1}(n)t^{n} = \frac{1}{1 − ∑_{n=1}^{∞} f_{0}(n)t^{n}} .

In other words, the sequence f_{1} is the invert transform of f_{0}, which as discussed in the introduction, can be written in terms of partial Bell polynomials, as claimed. Finally, the statement about the number of words made with exactly k blocks is a direct consequence of the definition of the partial Bell polynomials.

The case of binary building blocks (b = 1) will be discussed with more details in the next section, and the importance of greater values of b will be illustrated in Section 4.

Remark 4. We will choose b based on the type of restricted words we are interested in counting, not on the size of the alphabet. Once b is fixed, we can enlarge the alphabet by repeatedly applying the invert transform.

Given b ∈ ℕ and a sequence f_{0} of nonnegative integers, let {U_{j}} be a fixed sequence of subsets U_{j} ⊆ W_{b}(j) such that |U_{j}| = f_{0}(j) for j = 1, 2, . . .. Every word in U_{j} has length j and starts with b followed by j − 1 letters from the alphabet {0, 1, …, b − 1}. If we allow the character b to be replaced by any element of the set {b, …, b + m − 1} for m ∈ ℕ, then every word in U_{j} generates m words over the alphabet {0, 1, …, b + m − 1}. Thus each U_{j} gives rise to a set of words of length j, call it U_{j}^{m}, such that |U_{j}^{m}| = m · |U_{j}|. We let 𝒰_{b,n}^{m}(f_{0}) be the set of words of length n over the alphabet {0, 1, …, b + m − 1}, starting with b, made by concatenation of blocks from U_{j}^{m} for j = 1, …, n. If f_{0}(j) = 0, no block from U_{j}^{m} is used.

Corollary 5. Let f_{0} be a sequence of nonnegative integers such that f_{0}(j) ≤ b^{j−1} for every j ∈ ℕ and some b ∈ ℕ. For m ∈ ℕ, the sequence

f_{m}(1) = 1, f_{m}(n) = ∑_{k=1}^{n} \frac{k!}{n!}m^{k−1}B_{n,k}(1!f_{0}(1), 2!f_{0}(2), …),

counts the number of words in 𝒰_{b,n}^{m}(f_{0}). Note that f_{m} is the m-th invert transform of f_{0}.

Proof. By Theorem 3, the expression \frac{k!}{n!}B_{n,k}(1!f_{0}(1), 2!f_{0}(2), …) counts the number of words in 𝒰_{b,n}(f_{0}) of the form w_{j_{1}} ⋯ w_{j_{k}}, where each w_{j_{i}} is a subword in U_{j_{i}} for i = 1, …, k. If each of the subwords w_{j_{2}}, …, w_{j_{k}} is allowed to be replaced by any of the corresponding m blocks in U_{j_{2}}^{m}, …, U_{j_{k}}^{m}, respectively, we obtain \frac{k!}{n!}m^{k−1}B_{n,k}(1!f_{0}(1), 2!f_{0}(2), …) words in 𝒰_{b,n}^{m}(f_{0}). Note that every word in 𝒰_{b,n}^{m}(f_{0}) can be constructed in this manner.

Adding over k from 1 to n, we obtain the total number of elements of 𝒰_{b,n}^{m}(f_{0}).

3 Restricted words of binary type

For b = 1, the building blocks in W_{b}(j) are words of the form 10 ⋯ 0 with j − 1 zeros. Then, for m ∈ ℕ and a given binary sequence f_{0}, the set

𝒰_{1,n}^{m}(f_{0}) consists of words of length n over the alphabet {0, 1, …, m}, starting with 1, made by concatenating blocks of the form k 0 ⋯ 0 with j − 1 zeros, k ∈ {1, …, m}, where blocks of length j are used only if f_{0}(j) = 1.

For example, if f_{0} is the sequence 1, 0, 1, 1, 0, 0, …, then the elements of 𝒰_{1,5}^{2}(f_{0}) are words of length 5 over the alphabet {0, 1, 2}, starting with 1, made by using only the building blocks of length 1, 3, and 4:

1, 2 ∈ U_{1}^{2}, 100, 200 ∈ U_{3}^{2}, and 1000, 2000 ∈ U_{4}^{2}.

Moreover, the set 𝒰_{1,5}^{2}(f_{0}) consists of 32 such words:

11111, 11112, 11121, 11211, 12111,

11122, 11212, 11221, 12112, 12121, 12211,

11222, 12122, 12212, 12221, 12222,

10011, 10012, 10021, 10022, 11001, 11002, 12001, 12002, 11100, 11200, 12100, 12200, 10001, 10002, 11000, 12000.

Observe that the block restrictions given through the sequence f_{0} carry over to the words in 𝒰_{1,n}^{m}(f_{0}). For instance, in the above example, the sequence f_{0} induces the restrictions that 𝒰_{1,5}^{2}(f_{0}) contains no words with an isolated zero (f_{0}(2) = 0) and no words with more than three consecutive zeros (f_{0}(j) = 0 for j ≥ 5).

Remark 6. By treating the first 1 as a dummy character, we get a natural bijection between 𝒰_{1,n+1}^{m}(f_{0}) and the set of all words of length n with the restrictions determined by f_{0}.

We proceed to illustrate the results from Section 2 with a few examples. In the remaining part of this section, we will freely use some basic properties of partial Bell polynomials found in Comtet’s book [6, Section 3.3]. More intricate identities will be proved in the Appendix.

Example 7 (cf. [7, Cor. 33]). Suppose we wish to count the number of words of length n over the alphabet {0, 1, …, m} avoiding runs of ℓ zeros, ℓ ≥ 1. This can be done by computing f_{m}(n + 1) = |𝒰_{1,n+1}^{m}(f_{0})| with

f_{0}(j) = \begin{cases}1, & if 1 ≤ j ≤ ℓ; \\ 0, & otherwise. \end{cases}

By Corollary 5, we have

f_{m}(n + 1) = ∑_{k=1}^{n+1} \frac{k!}{(n + 1)!}m^{k−1} B_{n+1,k}(1!, 2!, …, ℓ!, 0, …).

By Identity 1 in the Appendix, we have

B_{n+1,k}(1!, 2!, …, ℓ!, 0, …) = \frac{(n + 1)!}{k!} ∑_{j=0}^{⌊ \frac{n+1−k}{ℓ} ⌋}(−1)^{j}\binom{k}{j}\binom{n − ℓj}{k − 1},

and therefore,

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

For various values of ℓ and m, this gives the sequences \underline{A000045}, \underline{A028859}, \underline{A125145}, \underline{A086347}, \underline{A180033}, \underline{A000073}, \underline{A119826}, \underline{A000078}, \underline{A209239}, \underline{A000322} in Sloane [8].

Example 8 (cf. [7, Cor. 28]). Consider words of length n over the alphabet {0, 1, …, m} avoiding runs of zeros of odd length. By adding a 1 to the left of each of these words, we obtain the set 𝒰_{1,n+1}^{m}(f_{0}) with

f_{0}(j) = \begin{cases}1, & if j is odd; \\ 0, & if j is even. \end{cases}

In this case, f_{m}(n + 1) = |𝒰_{1,n+1}^{m}(f_{0})| is given by

f_{m}(n + 1) = ∑_{k=1}^{n+1} \frac{k!}{(n + 1)!}m^{k−1} B_{n+1,k}(1!, 0, 3!, 0, 5!, …).

It is easy to see that B_{n+1,k}(1!, 0, 3!, 0, 5!, …) = 0 unless n + 1 + k is even. Moreover,

B_{n+1,k}(1!, 0, 3!, 0, 5!, 0, …) = \frac{(n + 1)!}{(n + 1 − k)!}B_{n+1−k,k}(0, 2!, 0, 4!, 0, …)

= \frac{(n + 1)!}{(\frac{n+k+1}{2})!}B_{\frac{n+k+1}{2} ,k}(1!, 2!, 3!, …) = \frac{(n + 1)!}{k!}\binom{\frac{n+k−1}{2}}{k − 1}.

Hence the number of elements in 𝒰_{1,n+1}^{m}(f_{0}) is given by

f_{m}(n + 1) = ∑_{\begin{matrix}1≤k≤n+1 \\ n+k+1 ≡ 0 (mod 2) \end{matrix}} \binom{\frac{n+k−1}{2}}{k − 1}m^{k−1} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}m^{n−2k}.

For m = 1, …, 10, this gives the sequences \underline{A000045}, \underline{A000129}, \underline{A006190}, \underline{A001076}, \underline{A052918}, \underline{A005668}, \underline{A054413}, \underline{A041025}, \underline{A099371}, \underline{A041041} in Sloane [8].

Example 9. For ℓ ∈ ℕ let

f_{0}(j) = \begin{cases}0, & if j ≤ ℓ; \\ 1, & otherwise. \end{cases}

Then the sequence

f_{m}(n) = ∑_{k=1}^{n} \frac{k!}{n!}m^{k−1} B_{n,k}(0, …, 0, (ℓ + 1)!, (ℓ + 2)!, …)

counts the number of words of length n over the alphabet {0, 1, …, m}, starting with 1, such that every nonzero element is followed by at least ℓ zeros.

Since

B_{n,k}(0, …, 0, (ℓ + 1)!, (ℓ + 2)!, …) = \frac{n!}{(n − ℓk)!}B_{n−ℓk,k}(1!, 2! …) for ℓk < n,

and since B_{n−ℓk,k}(1!, 2!, …) = \frac{(n−ℓk)!}{k!} \binom{n−ℓk−1}{k−1}, we get

\frac{k!}{n!}B_{n,k}(0, …, 0, (ℓ + 1)!, (ℓ + 2)!, …) = \binom{n − ℓk − 1}{k − 1} for ℓk < n.

Note that B_{n,k}(0, …, 0, (ℓ + 1)!, (ℓ + 2)!, …) = 0 for ℓk ≥ n. Thus we arrive at

f_{m}(n) = ∑_{k=1}^{⌊ \frac{n−1}{ℓ} ⌋} \binom{n − ℓk − 1}{k − 1}m^{k−1}.

In this case, all words in 𝒰_{1,n}^{m}(f_{0}) for n ≥ 2ℓ + 1 start with a 1 followed by at least ℓ zeros, and end with ℓ zeros. By removing these 2ℓ + 1 common characters, we get words of length n − 2ℓ − 1 such that every nonzero element not in the last position is followed by at least ℓ zeros. In conclusion, the number

f_{m}(n + 2ℓ + 1) = ∑_{k=1}^{⌊ \frac{n+2ℓ}{ℓ} ⌋} \binom{n − ℓ(k − 2)}{k − 1}m^{k−1}

counts the number of words of length n over the alphabet {0, 1, …, m} having at least ℓ zeros between any two nonzero elements.

For ℓ = 1 this example was discussed by Janjić [7, Cor. 24], and for ℓ = 2 and m = 1, the sequence f_{1}(n + 3) gives the Narayana cows sequence, \underline{A000930} in Sloane [8]. For ℓ = 2 and m = 2, …, 4, we get the sequences \underline{A003229}, \underline{A084386}, \underline{A089977}. Other values of ℓ and m lead to: \underline{A003269}, \underline{A052942}, \underline{A143454}, \underline{A003520}, \underline{A143447}, \underline{A143455}, \underline{A005708}.

We finish the section with a couple of more elaborate examples.

Example 10. Let

f_{0}(j) = \begin{cases}1, & if j = 1 or j = ℓ + 1; \\ 0, & otherwise. \end{cases}

The sequence f_{m}(n + 1) = |𝒰_{1,n+1}^{m}(f_{0})| counts the number of words of length n over the alphabet {0, 1, …, m} containing zeros only in substrings of length ℓ. By Corollary 5,

f_{m}(n + 1) = ∑_{k=1}^{n+1} \frac{k!}{(n + 1)!}m^{k−1} B_{n+1,k}(1!, 0, …, (ℓ + 1)!, 0 …).

By Identity 2 in the Appendix, we have

B_{n,k}(1!, 0, …, (ℓ + 1)!, 0 …) = \binom{n}{n − k + \frac{n−k}{ℓ}} \frac{(n − k)!}{(\frac{n−k}{ℓ})!} for n − k ≡ 0 (mod ℓ),

and therefore,

f_{m}(n + 1) = ∑_{\begin{matrix}1≤k≤n+1 \\ n+1−k ≡ 0 (mod ℓ) \end{matrix}}\frac{k!}{(n + 1)!} m^{k−1}\binom{n + 1}{n + 1 − k + \frac{n+1−k}{ℓ}} \frac{(n + 1 − k)!}{(\frac{n+1−k}{ℓ})!}.

Writing n + 1 = qℓ + r with 0 ≤ r < ℓ, we obtain

f_{m}(n + 1) =  ∑_{\begin{matrix}1≤k≤n+1 \\ n+1−k ≡ 0 (mod ℓ) \end{matrix}} \frac{k!}{(qℓ + r)!}m^{k−1}\binom{qℓ + r}{qℓ + r − k + \frac{qℓ+r−k}{ℓ}} \frac{(qℓ + r − k)!}{(\frac{qℓ+r−k}{ℓ})!}

= ∑_{i=0}^{q} \frac{(ℓi + r)!}{(qℓ + r)!}m^{ℓi+r−1}\binom{qℓ + r}{(ℓ + 1)(q − i)}\frac{((ℓ + 1)(q − i))!}{(q − i)!} = ∑_{i=0}^{q} \binom{ℓi + r}{q − i}m^{ℓi+r−1}.

In conclusion, the number of words of length n over the alphabet {0, 1, …, m} containing zeros only in substrings of length ℓ, is given by

f_{m}(n + 1) = ∑_{i=0}^{⌊ \frac{n+1}{ℓ} ⌋} \binom{n + 1 − ℓi}{i}m^{n−ℓi}.

For ℓ = 2 and m = 1, …, 6, this gives the sequences \underline{A068921}, \underline{A255115}, \underline{A255116}, \underline{A255117}, \underline{A255118}, \underline{A255119} in Sloane [8]. And for m = 1 and ℓ = 3, …, 7, we get \underline{A003269}, \underline{A003520}, \underline{A005708}, \underline{A005709}, \underline{A005710}.

Example 11. For ℓ ∈ ℕ let

f_{0}(j) = \begin{cases}0, & if j = ℓ + 1; \\ 1, & otherwise. \end{cases}

Then the sequence

f_{m}(n + 1) = ∑_{k=1}^{n+1} \frac{k!}{(n + 1)!}m^{k−1} B_{n+1,k}(1!, …, ℓ!, 0, (ℓ + 2)!, (ℓ + 3)!, …)

counts the number of words of length n over the alphabet {0, 1, …, m} avoiding runs of exactly ℓ zeros. By means of Identity 3 in the Appendix, the partial Bell polynomials can be written as

B_{n+1,k}(1!, …, ℓ!, 0, (ℓ + 2)!, (ℓ + 3)!, …)

= \frac{(n + 1)!}{k!} (∑_{κ<k}(−1)^{κ}\binom{k}{κ}\binom{n − (ℓ + 1)κ}{k − κ − 1} + (−1)^{k}δ_{n+1,(ℓ+1)k}) ,

where δ_{n+1,(ℓ+1)k} is the Kronecker delta function. Thus

f_{m}(n + 1) = ∑_{k=1}^{n+1} (∑_{κ<k}(−1)^{κ}\binom{k}{κ}\binom{n − (ℓ + 1)κ}{k − κ − 1} + (−1)^{k}δ_{n+1,(ℓ+1)k}) m^{k−1}.

If n + 1 = (ℓ + 1)q, then

f_{m}(n + 1) = (−1)^{q}m^{q−1} + ∑_{κ=0}^{q−1} ∑_{k=κ+1}^{n+1−ℓκ}(−1)^{κ}\binom{k}{κ}\binom{n − (ℓ + 1)κ}{k − κ − 1}m^{k−1},

and if n + 1 ≢ 0 modulo (ℓ + 1), then

f_{m}(n + 1) = ∑_{κ=0}^{⌊ \frac{n+1}{ℓ+1} ⌋} ∑_{k=κ+1}^{n+1−ℓκ}(−1)^{κ}\binom{k}{κ}\binom{n − (ℓ + 1)κ}{k − κ − 1}m^{k−1}.

For various values of ℓ and m, this gives the sequences \underline{A005251}, \underline{A120925}, \underline{A255813}, \underline{A255814}, \underline{A255815}, \underline{A049856}, \underline{A108758} in Sloane [8].

4 Further (nonbinary) examples

In [7, Corollary 37], Janjić discusses 01-avoiding words over a finite alphabet by considering the m-th invert transform of the sequence f_{0}(j) = j for j ∈ ℕ. He verifies that f_{m} satisfies the same recurrence relation as the sequence counting such words, but there is no other indication of how this f_{0} is combinatorially related to the given restriction.

In this section, we will use our results from Section 2 to shed some light on the counting of 01-avoiding words and will discuss examples that lead to the invert transform of the triangle numbers and other more general figurate numbers.

Example 12 (cf. [7, Cor. 37]). We start by considering words of length n over the alphabet {0, 1, 2}, starting with 2, that avoid the pattern 01. With the terminology from Section 2, this can be done with blocks in W_{b}(j) with b = 2 and j = 1, …, n. For example, for j = 1, …, 4, we have the building blocks

W_{2}(1) W_{2}(2) W_{2}(3) W_{2}(4)
2  20  200  2000
21  201  2001
210  2010
211  2011

2100 2101 2110 2111

and the colored blocks are the ones we wish to avoid. Observe that, once these building blocks are removed, every word made by concatenation of the remaining blocks will be a word that starts with 2 and avoids the subword 01. Also note that the building blocks avoiding 01 are precisely those where the digits are in nonincreasing order.

Let U_{j} be the subset of W_{2}(j) consisting of the j building blocks whose digits are in nonincreasing order. With this choice, the number of 01-avoiding words of length n, starting with 2, is equal to the number of elements in 𝒰_{2,n}(f_{0}) with f_{0} given by f_{0}(j) = j for j = 1, 2, …, recall the definition before Theorem 3. By removing the starting digit 2 from each word in 𝒰_{2,n}(f_{0}), we get a natural bijection to the set of 01-avoiding words of length n − 1 over the alphabet {0, 1, 2}.

The number of such words is then counted by the invert transform of f_{0}, see Theorem 3. Moreover, the set 𝒰_{2,n}^{m}(f_{0}) for m ≥ 1 contains all 01-avoiding words of length n, starting with 2, over the larger alphabet {0, 1, …, m+1}. If f_{m}(n) = |𝒰_{2,n}^{m}(f_{0})|, Corollary 5 together with Identity 4 with r = 0 (see Appendix) give

f_{m}(n) = ∑_{k=1}^{n} \frac{k!}{n!}m^{k−1}B_{n,k}(1! · 1, 2! · 2, 3! · 3, …) = ∑_{k=1}^{n} \binom{n + k − 1}{n − k}m^{k−1} for n > 1.

In conclusion, if f_{0}(j) = j for j ∈ ℕ, then for n > 1 the number of 01-avoiding words of length n − 1 over the alphabet {0, 1, …, m + 1} is given by

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

For m = 1, …, 10, this gives the sequences \underline{A001906}, \underline{A001353}, \underline{A004254}, \underline{A001109}, \underline{A004187}, \underline{A001090}, \underline{A018913}, \underline{A004189}, \underline{A004190}, \underline{A004191} in Sloane [8].

Corollary 13. It was noted in [7, Corollary 37] that the above sequence f_{m}(n) coincides with U_{n−1}(\frac{m+2}{2}), where U_{n} is the n-th Chebyshev polynomial of the second kind. As a consequence, we obtain the identity:

U_{n}(\frac{x+2}{2}) = ∑_{k=0}^{n} \binom{n + k + 1}{n − k}x^{k}.

Example 14. Following the idea of the last example, we now let b = 3 and let U_{j} be the building blocks in W_{3}(j) whose digits are in nonincreasing order. For instance, out of the 9 blocks in W_{3}(3):

300 301 302 310 311 312 320 321 322

there are 3 blocks that do not satisfy the restriction, so U_{3} has only 6 elements. In general, for every j ∈ ℕ there are \binom{j+1}{2} such blocks, and they are precisely the building blocks that avoid the patterns 01, 02, and 12. Thus with f_{0}(j) = \binom{j+1}{2} and U_{j} as above, the set 𝒰_{3,n}(f_{0}) consists of words of length n over the alphabet {0, 1, 2, 3}, starting with 3, and avoiding the patterns 01, 02, and 12. Moreover, as discussed in Section 2, the set 𝒰_{3,n}^{m}(f_{0}) for m ≥ 1 consists of words over the alphabet {0, 1, …, m + 2}, starting with 3, with the same restrictions as the words in 𝒰_{3,n}(f_{0}). Note that 𝒰_{3,n}^{m}(f_{0}) has the same number of elements as the set of words of length n − 1 over {0, 1, …, m + 2}, avoiding 01, 02, and 12.

Finally, by means of Corollary 5 and Identity 4 with r = 1 (see Appendix), we conclude that for n > 1 the sequence

f_{m}(n) = ∑_{k=1}^{n} \frac{k!}{n!}m^{k−1}B_{n,k}(1!\binom{2}{2}, 2!\binom{3}{2}, 3!\binom{4}{2}, …) = ∑_{k=1}^{n} \binom{n + 2k − 1}{n − k}m^{k−1}

gives the number of words of length n − 1 over the alphabet {0, 1, …, m + 2}, avoiding the patterns 01, 02, and 12.

For m = 1, 2, we get the sequences \underline{A052529} and \underline{A200676} in Sloane [8].

Remark 15. In each of the previous two examples, f_{0} is of the form f_{0}(j) = \binom{j+r}{r+1} for r ≥ 0. Example 12 corresponds to r = 0 and Example 14 is the case when r = 1. Choosing b = r+1 for the construction of 𝒰_{b,n}^{m}(f_{0}), and choosing building blocks with a nonincreasing restriction on its digits, one gets words that avoid certain patterns.

Example 16. Let r ∈ ℕ and f_{0}(j) = \binom{j+r}{r+1} for j ≥ 1. Then for n > 1, f_{m}(n) = |𝒰_{r+1,n}^{m}(f_{0})| counts the number of words of length n − 1 over the alphabet {0, 1, …, m + r + 1}, avoiding all patterns of the form a_{1}a_{2} with a_{1}, a_{2} ∈ {0, …, r + 1} and a_{1} < a_{2}. Applying Corollary 5 together with Identity 4 from the Appendix, we then get

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

For m = 1 and r = 2, …, 5, this gives the sequences \underline{A055991}, \underline{A079675}, \underline{A099242}, \underline{A099253} in Sloane [8].

We finish this section by revisiting another example considered by Janjić [7, Cor. 41]. While our final formula does not seem to give information that could have not been obtained from the recurrence relation given in [7], the goal here is to provide more combinatorial insight and to illustrate the versatility of the building block approach introduced in Section 2.

Example 17 (cf. [7, Cor. 41]). For q ∈ ℕ consider the set of ii-avoiding words of length n over the alphabet {0, 1, …, q} for i ∈ {0, 1, …, q − 1}. This set of words can be completely described with building blocks in W_{q}(j) for j = 1, …, n+1. The elements of W_{q}(j) are strings of length j, starting with q, followed by j − 1 letters from the alphabet {0, 1, …, q − 1}. Clearly, there is only one word in W_{q}(1), and there are q words in W_{q}(2), q0, q1, …, q(q − 1), none of which is of the form ii. Moreover, for j > 2 there are exactly q ·(q −1)^{j−2} ii-avoiding words in W_{q}(j). Thus, if f_{0} is defined by

f_{0}(j) = \begin{cases}1, & if j = 1; \\ q(q − 1)^{j−2}, & if j ≥ 2; \end{cases}

then, by Theorem 3, the sequence f_{1}(n + 1) = ∑_{k=1}^{n+1} \frac{k!}{(n+1)!}B_{n+1,k}(1!f_{0}(1), 2!f_{0}(2), …) gives the number of ii-avoiding words of length n over {0, 1, …, q} for 0 ≤ i < q.

As before, Corollary 5 gives a corresponding formula for the m-th invert transform, but before we work it out, let us simplify the partial Bell polynomial:

B_{n+1,k}(1!f_{0}(1), 2!f_{0}(2), …) = B_{n+1,k}(1!, 2!q, 3!q(q − 1), 4!q(q − 1)^{2}, …)

= ∑_{ℓ=0}^{k} \frac{(n + 1)!}{(n + 1 − k)!ℓ!}B_{n+1−k,k−ℓ}(q, 2!q(q − 1), 3!q(q − 1)^{2}, …)

= ∑_{ℓ=0}^{k} \frac{(n + 1)!}{(n + 1 − k)!ℓ!}q^{k−ℓ}(q − 1)^{n+1+ℓ−2k}B_{n+1−k,k−ℓ}(1!, 2!, …),

which for k ≤ n implies

\frac{k!}{(n + 1)!}B_{n+1,k}(1!f_{0}(1), 2!f_{0}(2), …) = ∑_{ℓ=0}^{k−1} \binom{k}{ℓ}\binom{n − k}{k − ℓ − 1}q^{k−ℓ}(q − 1)^{n+1+ℓ−2k}.

Finally, by Corollary 5, we conclude that the number of ii-avoiding words of length n over the alphabet {0, 1, …, q + m − 1} for i ∈ {0, 1, …, q − 1}, is given by

f_{m}(n + 1) = m^{n} + ∑_{k=1}^{n} ∑_{ℓ=0}^{k−1} \binom{k}{ℓ}\binom{n − k}{k − ℓ − 1}q^{k−ℓ}(q − 1)^{n+1+ℓ−2k}m^{k−1}.

For various values of m and q, this formula leads to the sequences \underline{A000045}, \underline{A001333}, \underline{A055099}, \underline{A123347}, \underline{A180035} in Sloane [8].

5 Appendix: Bell polynomial identities

Identity 1. For ℓ ∈ ℕ we have

B_{n,k}(1!, 2!, …, ℓ!, 0, …) = \frac{n!}{k!} ∑_{j=0}^{⌊ \frac{n−k}{ℓ} ⌋}(−1)^{j}\binom{k}{j}\binom{n − ℓj − 1}{k − 1}.

A proof of this identity can be found in [1, Theorem 4.1 combined with Theorem 2.1].

Identity 2. For ℓ ∈ ℕ with ℓ > 1, we have

B_{n,k}(1!, 0, …, (ℓ + 1)!, 0 …) = \binom{n}{n − k + \frac{n−k}{ℓ}} \frac{(n − k)!}{(\frac{n−k}{ℓ})!}

whenever n − k ≡ 0 (mod ℓ).

Proof. Using [6, Eqs. (3n) and (3n’), Section 3.3], we have

B_{n,k}(1!, 0, …, (ℓ + 1)!, 0 …) = ∑_{κ=0}^{k} ∑_{ν=κ}^{n} \binom{n}{ν}B_{ν,κ}(0 …, (ℓ + 1)!, 0 …)B_{n−ν,k−κ}(1, 0, 0, …)

= ∑_{κ=0}^{k} \binom{n}{n − k + κ}B_{n−k+κ,κ}(0 …, (ℓ + 1)!, 0 …)

= \binom{n}{n − k + \frac{n−k}{ℓ}} \frac{(n − k)!}{(\frac{n−k}{ℓ})!} for n − k ≡ 0 (mod ℓ).

Identity 3. For ℓ ∈ ℕ,

B_{n,k}(1!, …, ℓ!, 0, (ℓ + 2)!, (ℓ + 3)!, …)

= \frac{n!}{k!} (∑_{κ=0}^{k−1}(−1)^{κ}\binom{k}{κ}\binom{n − (ℓ + 1)κ − 1}{k − κ − 1} + (−1)^{k}δ_{n,(ℓ+1)k}),

where δ_{n,(ℓ+1)k} is the Kronecker delta function.

Proof. Let x̄_{ℓ}, ē_{ℓ}, and x̄ be defined as

x̄_{ℓ} = (1!, …, ℓ!, 0, (ℓ + 2)!, …), ē_{ℓ} = (0, …, 0, (ℓ + 1)!, 0, …), and x̄ = ē_{ℓ} + x̄_{ℓ}.

By means of [6, Eqs. (3n) and (3n’), Section 3.3], we then have

B_{n,k}(x̄_{ℓ}) = ∑_{κ≤k, ν≤n} \binom{n}{ν}B_{ν,κ}(−ē_{ℓ})B_{n−ν,k−κ}(x̄)

= ∑_{κ≤k} \binom{n}{(ℓ + 1)κ}\frac{((ℓ + 1)κ)!}{κ!}(−1)^{κ}B_{n−(ℓ+1)κ,k−κ}(x̄)

= \frac{n!}{k!} ∑_{κ=0}^{k−1}(−1)^{κ}\binom{k}{κ}\binom{n − (ℓ + 1)κ − 1}{k − κ − 1} + (−1)^{k} \frac{n!}{k!(n − (ℓ + 1)k)!}B_{n−(ℓ+1)κ,0}(x̄)

= \frac{n!}{k!} (∑_{κ=0}^{k−1}(−1)^{κ}\binom{k}{κ}\binom{n − (ℓ + 1)κ − 1}{k − κ − 1} + (−1)^{k}δ_{n,(ℓ+1)k}) .

Identity 4. For r ≥ 0 let t_{j}(r) = \binom{j+r}{r+1}. Then

B_{n,k}(1!t_{1}(r), 2!t_{2}(r), ⋯) = \frac{n!}{k!}\binom{n + (r + 1)k − 1}{n − k}.

Proof. For k = 1 and all n we have

B_{n,1}(1!t_{1}(r), 2!t_{2}(r), ⋯) = \frac{n!}{1!}\binom{n + r}{r + 1} = \frac{n!}{1!}\binom{n + r}{n − 1}.

Now we proceed by induction on k. For k > 1,

B_{n,k}(1!t_{1}(r), 2!t_{2}(r), ⋯) = \frac{1}{k} ∑_{j=0}^{n} \binom{n}{j}j!\binom{j + r}{r + 1}B_{n−j,k−1}(1!t_{1}(r), 2!t_{2}(r), 3!t_{3}(r), ⋯)

= \frac{1}{k} ∑_{j=1}^{n} \binom{n}{j}j!\binom{j + r}{r + 1}\frac{(n − j)!}{(k − 1)!}\binom{n − j + (r + 1)(k − 1) − 1}{n − j − k + 1}

= \frac{n!}{k!} ∑_{j=1}^{n−k+1} \binom{j + r}{j − 1}\binom{n − j + (r + 1)(k − 1) − 1}{n − j − k + 1}

= \frac{n!}{k!} ∑_{j=0}^{n−k} \binom{j + r + 1}{j}\binom{n − j + (r + 1)(k − 1) − 2}{n − k − j}

= \frac{n!}{k!} ∑_{j=0}^{n−k}(−1)^{n−k}\binom{−r − 2}{j}\binom{−(r + 1)(k − 1) − k + 1}{n − k − j}.

Using Chu-Vandermonde’s identity, we arrive at

B_{n,k}(1!t_{1}(r), 2!t_{2}(r), ⋯) = (−1)^{n−k} \frac{n!}{k!}\binom{−(r + 1)k − k}{n − k} = \frac{n!}{k!}\binom{n + (r + 1)k − 1}{n − k}.

References

[1] H. Belbachir, S. Bouroubi, A. Khelladi, Connection between ordinary multinomials, Fibonacci numbers, Bell polynomials and discrete uniform distribution, Ann. Math. Inform. 35 (2008), 21–30.

[2] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 226/228 (1995), 57–72.

[3] D. Birmajer, J. Gil, and M. Weiner, Some convolution identities and an inverse relation involving partial Bell polynomials, Electron. J. Combin. 19 (4) (2012), Paper #34.

[4] D. Birmajer, J. Gil, and M. Weiner, Linear recurrence sequences and their convolutions via Bell polynomials, J. Integer Seq. 18 (2015), Article 15.1.2.

[5] P. J. Cameron, Some sequences of integers, Discrete Math. 75 (1989), 89–102.

[6] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, D. Reidel Publishing Co., 1974.

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

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

[9] W. Wang and T. Wang, General identities on Bell polynomials, Comput. Math. Appl., 58 (2009), 104–118.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 11B83. Keywords: restricted word, invert transform, partial Bell polynomial.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A000078}, \underline{A000129}, \underline{A000322}, \underline{A000930}, \underline{A001076}, \underline{A001090}, \underline{A001109}, \underline{A001333}, \underline{A001353}, \underline{A001906}, \underline{A003229}, \underline{A003269}, \underline{A003520}, \underline{A004187}, \underline{A004189}, \underline{A004190}, \underline{A004191}, \underline{A004254}, \underline{A005251}, \underline{A005668}, \underline{A005708}, \underline{A005709}, \underline{A005710}, \underline{A006190}, \underline{A018913}, \underline{A028859}, \underline{A041025}, \underline{A041041}, \underline{A049856}, \underline{A052529}, \underline{A052918}, \underline{A052942}, \underline{A054413}, \underline{A055099}, \underline{A055991}, \underline{A068921}, \underline{A079675}, \underline{A084386}, \underline{A086347}, \underline{A089977}, \underline{A099242}, \underline{A099253}, \underline{A099371}, \underline{A108758}, \underline{A119826}, \underline{A120925}, \underline{A123347}, \underline{A125145}, \underline{A143447}, \underline{A143454}, \underline{A143455}, \underline{A180033}, \underline{A180035}, \underline{A200676}, \underline{A209239}, \underline{A255115}, \underline{A255116}, \underline{A255117}, \underline{A255118}, \underline{A255119}, \underline{A255813}, \underline{A255814}, and \underline{A255815}.)

Received September 7 2015; revised version received November 22 2015. Published in Journal of Integer Sequences, December 17 2015.

Return to Journal of Integer Sequences home page.