Binomial Coefficients and Enumeration of Restricted Words

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

                    agnus@blic.net

Abstract

We derive partial solutions for a recently-posed problem of the enumeration of restricted words. We obtain several explicit formulas in which the number of restricted words is expressed in terms of the binomial coefficients. These results establish relations between the partial Bell polynomials and the binomial coefficients.

In particular, we link the r-step Fibonacci numbers, the binomial coefficients and the partitions of a positive integer into at most r parts. Also, we prove that several well-known classes of integers can be interpreted in terms of compositions. We finish the paper with an extension of a recent result about Euler-type identities for integer compositions.

1 Introduction

We firstly recall the notion of the invert transform, which we express in terms of the formal power series. For an arithmetic function f_{0}, its invert transform f_{1} is defined by

(1 + ∑_{i=1}^{∞} f_{0}(i)x^{i}) · (1 − ∑_{i=1}^{∞} f_{1}(i)x^{i}) = 1.

In this paper, we consider the case when values of f_{0} are either 0 or 1. Then f_{1} takes non-negative integer values. In a previous work, Janjić [5] defined the sequence f_{1}, f_{2}, … of arithmetic functions so that f_{m} is the invert transform of f_{m−1} for m = 1, 2, . . .. The function f_{m} is called the mth invert transform of f_{0}. The functions f_{1}, f_{2}, … generalize the notion of the composition of a positive integer. Namely, if f_{m−1} takes only nonnegative integer values, then f_{m}(n) equals the number of the colored compositions of n in which the part i may appear in f_{m−1}(i) different colors. For an arithmetic function f, and a positive integer k, we define the formal power series g(x, k; f) as

g(x, k; f) = (∑_{i=1}^{∞} f(i)x^{i})^{k} .

We consider the expansion

g(x, k; f) = ∑_{n=k}^{∞} G(n, k; f)x^{n}.  (1)

It follows that g(x, k; f) is a generating function for the sequence G(n, k; f), (n = k, k+1, …). The functions g(x, k; f) and the partial Bell polynomials B_{n,k}(x_{1}, x_{2}, …) are related by

G(n, k; f) = \frac{k!}{n!}B_{n,k}(1!f(1), 2!f(2), …).  (2)

Also, the following equation is well-known:

G(n, k; f) = ∑_{i_{1}+i_{2}+···+i_{k}=n} f(i_{1}) ⋯ f(i_{k}),  (3)

where the sum is over positive i_{t}, (t = 1, …, k). Similar expansions have recently been considered by several authors. For instance, Eger [2] called the numbers G(n, k; f) the weighted integer compositions. A number of results of the weighted integer compositions and the partial Bell polynomials may be found in Eger [2, 3, 4]. The equation (3) slightly differs from Eger [2, Equation (1)], where the sum is over non-negative i_{t}, (t = 1, 2, …, k). D. Birmajer et al. [1] proved the following formula:

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

In this paper, we investigate the problem of the enumeration of some restricted words, counted by the functions f_{1}, f_{2}, …, when f_{0} is a binary function (Janjić [5, Problem 21]). We derive several explicit formulas for G(n, k; f_{0}). Consequently, we obtain a combinatorial interpretation of f_{m} in terms of the restricted words over the alphabet {0, 1, …, m}. The obtained results yield a number identities for the partial Bell polynomials. Furthermore, each G(n, k; f_{0}) is expressed in terms of the binomial coefficients. In this way, we obtain the identities connecting the partial Bell polynomials and the binomial coefficients.

In particular, we derive a result linking the r-step Fibonacci numbers, the binomial coefficients, and the partitions of positive integers into at most r parts. We also prove that several well-known classes of integers, such as positive integers, squares, cubes, triangular numbers, and so on, can be interpreted in terms of compositions. As a consequence, we generalize a recent result about Euler-type identities for integer compositions.

For a set X ⊆ ℙ, where ℙ is the set of positive integers, we will use the following notation:

1. G(n, k; X) will be the number of compositions of n with k parts in X. Also, f_{1}(n; X) will be the number of all compositions of n with parts in X.

2. G(n, k; X^{c}) will be the number of compositions of n into k parts, none of which is from X. Also, f_{1}(n; X^{c}) will be the number of all compositions of n into parts which are not from X.

For a binary function f_{0}, we denote

A = {i : f_{0}(i) = 1}, B = {i : f_{0}(i) = 0}.

There is a natural bijection between compositions of n and the binary words of length n − 1, which is given by the correspondence

1 → 1, 2 → 10, 3 → 100, …,

and then omitting the leading 1. Hence, for X ⊆ ℙ, f_{1}(n; X), and f_{1}(n; X^{c}) also count the appropriate binary words of length n − 1.

As an illustration, we present a well-known example.

Example 1. If A = {1, 2}, then G(n, k; A) equals the number of compositions of n into k parts in {1, 2}. It is well known that

G(n, k; A) = \binom{k}{n − k}, f_{1}(n; A) = F_{n+1},

where F_{n+1} is a Fibonacci number. By the preceding bijection, we obtain that F_{n+1} equals the number of binary words of length n − 1 having all zeros isolated, which is also a well-known property of the Fibonacci numbers.

As a consequence of Birmajer at al. [1, Corollary 2.2], we obtain

Corollary 2. The number f_{m}(n; A) equals the number of words of length n − 1 over the alphabet {0, 1, …, m}, in which 0 appears only in a run of length i − 1, for i ∈ A.

Also, the equation

f_{m}(n; A) = ∑_{k=1}^{n} m^{k−1}G(n, k; A)

holds.

Thus, whenever the values of G(n, k; A) are known, we can obtain the corresponding number f_{m}(n; A) of restricted words over the alphabet {0, 1, …, m}.

We consider the following cases:

1. A is finite.

2. B is finite.

3. f_{0} is periodic.

We start with a simple example.

Example 3. Let A = ℙ. A well-known property of compositions implies

G(n, k; A) = \binom{n − 1}{k − 1} for k = 1, …, n.

As a consequence of Corollary 2 and the binomial formula, we get

f_{m}(n; A) = (m + 1)^{n−1}.

Equation (2) implies the following well-known identity:

Identity 4.

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

The Lah numbers are on the right-hand side of the equation.

2 The case when A is finite

Assume that A = {a_{1}, a_{2}, …, a_{r}}, where 1 ≤ a_{1} < a_{2} < ⋯ < a_{r}, (r ≥ 1). A formula for G(n, k; A) may be derived from the multinomial formula. We derive a formula in a different way, as a generalization of the formula from Example 1.

Proposition 5. We have

G(n, k; A) = ∑_{(j_{1},...,j_{r−1})} \binom{k}{j_{1}}\binom{j_{1}}{j_{2}} ⋯ \binom{j_{r−2}}{j_{r−1}},  (5)

where the sum is over all non-increasing sequences of non-negative integers (j_{1}, …, j_{r−1}), such that

n = ka_{1} + j_{1}(a_{2} − a_{1}) + ⋯ + j_{r−2}(a_{r−1} − a_{r−2}) + j_{r−1}(a_{r} − a_{r−1}).  (6)

If Equation (6) does not hold, then G(n, k; A) = 0.

Proof. We write G(n, k; A) in the form G(n, k; a_{1}, a_{2}, …, a_{r}). According to (3), we have to solve the Diophantine equation

i_{1} + i_{2} + ⋯ + i_{k} = n,  (7)

where i_{t} are in A. Take s ∈ {0, 1, …, k}. If there is a solution of (7) in which a_{1} appears s times, then there are \binom{k}{s} such solutions. In particular, when k = s, there is only one solution. We now subtract a_{1} from each i_{t}, (t = 1, 2, …, k) in (7). For s < k, we obtain

j_{1} + ⋯ + j_{k−s} = n − ka_{1},  (8)

where j_{t} ∈ {a_{2} − a_{1}, …, a_{r} − a_{r−1}}. In the case s = k, Equation (7) has only one solution when n = ka_{1}. This is the case when in (5) we take j_{1} = ⋯ = j_{r−1} = 0. If n ≠ ka_{1}, then Equation (7) has no solution. It follows that

G(n, k; a_{1}, …, a_{r}) = ∑_{j_{1}=0}^{k} \binom{k}{j_{1}}G(n − ka_{1}, k − j_{1}; a_{2} − a_{1}, …, a_{r} − a_{r−1}),

where G(n − ka_{1}, 0; a_{2} − a_{1}, …, a_{r} − a_{r−1}) = 1 if n = ka_{1}, and G(n − ka_{1}, 0; a_{2} − p_{1}, …, a_{r} − a_{r−1}) = 0 otherwise. Repeating the same argument, we obtain

G(n, k; a_{1}, …, a_{r}) = ∑_{k≥j_{1}≥···≥j_{r−1}≥0} \binom{k}{j_{1}}\binom{j_{1}}{j_{2}} ⋯ \binom{j_{r−2}}{j_{r−1}} · X,

where

X = G(n − ka_{1} − j_{1}(a_{2} − a_{1}) − ⋯ − j_{r−2}(a_{r−1} − a_{r−2}), j_{r−1}; a_{r} − a_{r−1}).

The number X equals the number of compositions of n − k(a_{1} − 1) − j_{1}(a_{2} − a_{1}) − ⋯ − j_{r−2}(a_{r−1} − a_{r−2}) into j_{r−1} parts, each part equals to a_{r} − a_{r−1}. As in the case k = s, we conclude that X = 1, if n = ka_{1} + j_{1}(a_{2} − a_{1}) + ⋯ + j_{r−2}(a_{r−1} − a_{r−2}) + j_{r−1}(a_{r} − a_{r−1}). If n ≠ ka_{1}, then X = 0.

Proposition 5 yields the following:

Identity 6. We have

B_{n,k}(0, …, 0, a_{1}!, 0 …, 0, a_{2}!, 0, …) = \frac{n!}{k!} ∑ \binom{k}{j_{1}}\binom{j_{1}}{j_{2}} ⋯ \binom{j_{r−2}}{j_{r−1}},

where the sum is over all j_{1} ≥ j_{2} ≥ ⋯ ≥ j_{r−1} ≥ 0 such that

n = ka_{1} + j_{1}(a_{2} − a_{1}) + ⋯ + j_{r−2}(a_{r−1} − a_{r−2}) + j_{r−1}(a_{r} − a_{r−1}).

Note 7. We point out that Identity 6, as well as the remaining identities of the partial Bell polynomials, may be proved directly from the properties of the partial Bell polynomials.

From Equation (4), we obtain the following:

Corollary 8. Let N be the number of words of length n − 1 over the alphabet {0, 1, …, m} such that 0 appears only in a run whose length belongs to the set {a_{1} − 1, a_{2} − 1, …, a_{r} − 1}. Then

N = ∑_{k=1}^{n} m^{k−1}G(n, k; a_{1}, …, a_{r}).

We now consider some special cases.

Corollary 9. Let A = {1, p} for (p > 1). Then

G(n, n − ip + i; A) = \binom{n − ip + i}{i} for i = 0, … ⌊\frac{n}{p}⌋ ,  (9)

and

f_{1}(n; A) = \begin{matrix}⌊ & \frac{n}{p} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{n − ip + i}{i}.

Corollary 10. If A = {1, 2, …, r}, then

G(n, k; A) = ∑ \binom{k}{j_{1}}\binom{j_{1}}{j_{2}} ⋯ \binom{j_{r−2}}{j_{r−1}},  (10)

where the sum is over all partitions (j_{1}, j_{2}, ⋯, j_{r−1}) of n − k into at most r − 1 parts, each part having the size at most k.

Proof. Using Proposition 5, we have a_{1} = 1 and a_{i} − a_{i−1} = 1 for i = 2, 3, …, r. It follows that the sum is over all j_{1}, j_{2}, …, j_{r−1} such that

n = k + j_{1} + ⋯ + j_{r−1}.

Since k ≥ j_{1} ≥ ⋯ ≥ j_{r−1}, the sequences (j_{1}, j_{2}, …, j_{r−1}) are partitions of n − k.

We know that f_{1}(n; A) equals the number of all compositions of n with parts in {1, 2, …, r}. These compositions are counted by the r-step Fibonacci numbers F_{n}^{r}. Denoting k = j_{0} ≥ 1, we obtain a result connecting the partitions and the binomial coefficients with the r-step Fibonacci numbers.

Corollary 11. We have

F_{n+r−1}^{r} = ∑ \binom{j_{0}}{j_{1}}\binom{j_{1}}{j_{2}} ⋯ \binom{j_{r−2}}{j_{r−1}},

where the sum is over all partitions (j_{0}, j_{1}, j_{2}, …, j_{r−1}) of n into at most r parts.

Note that the terms of the partitions are written in a non-increasing order. We finish this section with the following particular case. Corollary 12. Consider the set A = {1, 3, 5}. If n − k ≡ 0 (mod 2), then

G(n, k; A) = ∑_{i=0}^{min \{k, \frac{n−k}{2} \}} \binom{k}{i}\binom{i}{\frac{n−k}{2} − i}.

Otherwise, G(n, k; 1, 3, 5) = 0. Proof. From Proposition 5, we conclude that

G(n, k; A) = ∑_{j_{1},j_{2}} \binom{k}{j_{1}}\binom{j_{1}}{j_{2}},

where n − k = 2j_{1} + 2j_{2}, and k ≥ j_{1} ≥ j_{2} ≥ 0. It follows that

n − k ≡ 0 (mod 2), j_{1} ≤ min \{k, \frac{n − k}{2} \} , j_{2} = \frac{n − k}{2} − j_{1}.

Some related sequences in Sloane [7] are \underline{A000930}, \underline{A000931}, \underline{A017817}, \underline{A052920}, \underline{A071675}, \underline{A079960}, \underline{A079976}, \underline{A117760}, \underline{A124304}, \underline{A191238}, \underline{A198295}, \underline{A253189}.

3 The case when B is finite

This section opens with a particular case. Proposition 13. Let p > 1 be an integer, and B = {1, 2, … p − 1}. Then

G(n + p, i + 1; B^{c}) = \binom{n − pi + i}{i}, for i = 0, …, ⌊\frac{n}{p}⌋ .  (11)

Proof. We write the formula (1) in the form

(x^{p} + x^{p+1} + …)^{k} = ∑_{n=0}^{∞} G(n + k, k; B^{c})x^{n+k}.

Since

(x^{p} + x^{p+1} + …)^{k} = ∑_{t=0}^{∞} \binom{t + k − 1}{k − 1}x^{t+kp},  (12)

we have

∑_{n=0}^{∞} G(n + k, k; B^{c})x^{n} = ∑_{t=0}^{∞} \binom{t + k − 1}{k − 1}x^{t+kp}.

It follows that

G(n + k, k; B^{c}) = \binom{t + k − 1}{k − 1},

for n + k = t + kp, that is, for t = n − k(p − 1) ≥ 0. When n < k(p − 1), we have G(n + k, k; B^{c}) = 0. If n ≥ k(p − 1), then G(n + k, k; B^{c}) = \binom{n−kp+2k−1}{k−1}. Taking n − k instead of n gives

G(n, k; B^{c}) = \binom{n − kp + k − 1}{k − 1}.  (13)

By denoting k = i + 1, and by replacing n by n + p, we obtain Equation (11).

Summing over all i in (11) yields

Corollary 14. The formula

f_{1}(n + p; B^{c}) = \begin{matrix}⌊ & \frac{n}{p} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{n − pi + i}{i} for n ≥ p

holds. Also, the number f_{m}(n + p; B^{c}) equals the number of words of length n + p over the alphabet {0, 1, …, m}, in which 0 appears only in a run of length ≤ p − 1.

Note 15. Using a different method, the same result is obtained in [1, Example 9].

Identity 16. We have

B_{n+p,i+1}(0, 0, …, p!, (p + 1)!, …) = \frac{(n + p)!}{(i + 1)!}\binom{n − pi + i}{i}, (0 ≤ i ≤ ⌊\frac{n}{p}⌋) .

For p = 2, we obtain the well-known formula

F_{n+1} = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{n − i}{i} for n ≥ 1,  (14)

where F_{n+1} is a Fibonacci number.

Assume that B ≠ ∅ is finite, and let p − 1 be the greatest element of B. If f_{0}(i) = 0 for each i ≤ p − 1, then we find g(n, k, B^{c}), as in Proposition 13. This also includes the case p = 2. So, we may assume that p > 2. Take A_{1} = {a_{1}, …, a_{r}} ⊂ {1, 2, …, p − 2}, which consists of all i ∈ {1, 2, …, p − 2}, such that f_{0}(i) = 1. We may assume that A_{1} ≠ ∅. It follows that B^{c} = A_{1} ∪ {p, p + 1, …}.

Proposition 17. The following equation holds:

G(n, k; B^{c}) = ∑_{i=0}^{min\{k,⌊\frac{n−k}{p−1}⌋\}} ∑_{t=0}^{n−k+i−ip} \binom{k}{i}\binom{t + i − 1}{i − 1}G(n − ip − t, k − i; A_{1}).

Proof. We have

g(x, k; B^{c}) = [(x^{a_{1}} + ⋯ + x^{a_{r}}) + (x^{p} + x^{p+1} + ⋯)]^{k} .

The binomial theorem implies

g(x, k; B^{c}) = ∑_{i=0}^{k} \binom{k}{i}(x^{a_{1}} + ⋯ + x^{a_{r}})^{k−i}(x^{p} + x^{p+1} + ⋯)^{i}.

Let X = (x^{a_{1}} + ⋯ + x^{a_{r}})^{k−i}(x^{p} + x^{p+1} + ⋯)^{i}. Proposition 5 yields

[(x^{a_{1}} + ⋯ + x^{a_{r}})^{k−i} = ∑_{s=0}^{∞} G(s + k − i, k − i; A_{1}) · x^{s+k−i}.

Note that this equation is also true for i = k, since G(s, 0; A_{1}) = 1 if and only if s = 0. Otherwise, G(s, 0; A_{1}) = 0, by the definition of G(s, k; A_{1}).

We also have

(x^{p} + x^{p+1} + ⋯)^{i} = ∑_{s=0}^{∞} \binom{s + i − 1}{i − 1}x^{s+ip}.

This equation also holds for i = 0, since \binom{s+i−1}{i−1} = \binom{s−1}{s}, which equals 0 if s ≠ 0. If s = 0, from \binom{−1}{0} = 1, we see that the right-hand side equals 1. We thus obtain

X = ∑_{s=0}^{∞} G(s + k − i, k − i; A_{1})x^{s+k−i} · ∑_{s=0}^{∞} \binom{s + i − 1}{i − 1}x^{s+ip}.

Multiplying the series on the right-hand side yields

X = ∑_{s=0}^{∞} [∑_{t=0}^{s} \binom{t + i − 1}{i − 1}G(s − t + k − i, k − i; A_{1})] x^{s+k−i+ip}.

Hence,

g(x, k; B^{c}) = ∑_{s=0}^{∞} ∑_{t=0}^{s} ∑_{i=0}^{k} \binom{k}{i}\binom{t + i − 1}{i − 1}G(s − t + k − i, k − i; A_{1}) · x^{s+k−i+ip}. (15)

If we write (1) in the form

g(x, k; B^{c}) = ∑_{n=0}^{∞} G(n + k, k; B^{c})x^{n+k},

then, by comparing the coefficients of the same powers of x, we conclude that n = s − i + ip. Hence, in Equation (15), the sum over s has only one term, obtained for s = n − ip + i. If s ≥ 0, then i ≤ ⌊\frac{n}{p−1}⌋, which implies that

0 ≤ i ≤ min \{k, ⌊\frac{n}{p − 1}⌋\} .

We conclude that

G(n + k, k; B^{c}) = ∑_{i=0}^{min\{k,⌊\frac{n}{p−1}⌋\}} ∑_{t=0}^{n+i−ip} \binom{k}{i}\binom{t + i − 1}{t}G(n − ip − t + k, k − i; A_{1}).

Replacing n by n − k proves our statement.

In particular, if A_{1} = {1}, then G(n−ip−t, k −i; A_{1}) = 1 if n−ip−t = k −i. Otherwise, G(n − ip − t, k − i; A_{1}) = 0. We thus obtain

Corollary 18. If B = {2, 3, …, p − 1}, then

G(n, k; B^{c}) = ∑_{i=0}^{min\{k,⌊\frac{n−k}{p−1}⌋\}} \binom{k}{i}\binom{n − k − (p − 2)i − 1}{i − 1}.

An immediate consequence is

Identity 19. The following identity is true

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

As a consequence of Corollary 18, we prove that the following well-known classes of integers count some restricted compositions.

Corollary 20.

1. The positive integer k gives the number of compositions of k + 2 into k parts, none of which is equal to 2. \underline{A000027}

2. The triangular number \frac{k(k+1)}{2} gives the number of compositions of k+4 into k parts, none of which is equal to 2. \underline{A000217}

3. The square k^{2} gives the number of compositions of k + 5 into k parts, none of which is equal to 2. \underline{A000290} 4. The number of k-dimensional partitions of 4 \frac{k(k^{2}+6k−1)}{6} gives the number of com-

positions of k + 6 into k parts, none of which is equal to 2. \underline{A008778}

5. The pentagonal pyramidal number \frac{k^{2}(k+1)}{2} gives the number of compositions of k + 7 into k parts, none of which is equal to 2. \underline{A002411}

6. Number of k-dimensional partition of 5 \frac{k(k^{3}+18k^{2}−k+6)}{24} gives the number of compositions of k + 8 into k parts, none of which is equal to 2. \underline{A008779}

7. The pentagonal number \frac{k(3k−1)}{2} gives the number of compositions of k + 8 into k parts, none of which is equal either 2 or 3.\underline{A000326}

8. The cube k^{3} gives the number of compositions of k + 11 into k parts, none of which is equal either 2 or 3. \underline{A000578}

9. The hexagonal number k(2k − 1) gives the number of compositions of k + 11 into k parts, none of which belongs to \{2, 3, 4\}. \underline{A000384}

10. The octagonal pyramidal number \frac{k(k+1)(2k−1)}{2} gives the number of compositions of k + 14 into k parts, none of which belongs to \{2, 3, 4\}. \underline{A002414}

11. The Cupolar number \frac{k(5k^{2}−3k+1)}{3} gives the number of compositions of k + 15 into k parts, none of which belongs to \{2, 3, 4\}. \underline{A096000}

12. Heptagonal number \frac{k(5k−3)}{2} give the number of compositions of k + 14 into k parts, none of which belongs to \{2, 3, 4, 5\}. \underline{A000566} (This example is suggested by the referee).

Proof. The above statements are an immediate consequence of Proposition 18. As an illustration, we prove items 3, 8 and 11.

3. We have p = 3, n = 5, so that Proposition 18 reduces to the identity

k^{2} = ∑_{i=1}^{2} \binom{k}{i}\binom{5 − i − 1}{i − 1}, (k ≥ 2),

which is easy to prove.

8. In this case, we have p = 4, n = 11. Denoting a_{k} = G(11 + k, k; f), we obtain

a_{1} = 1, a_{2} = ∑_{i=1}^{2} \binom{2}{i}\binom{11 − 2i − 1}{i − 1} = 8.

If k ≥ 3, then

a_{k} = ∑_{i=1}^{3} \binom{k}{i}\binom{11 − 2i − 1}{i − 1} = \binom{k}{1} + 6\binom{k}{2} + 6\binom{k}{3} = k^{3}.

11. This case reduces to the identity

\frac{k(5k^{2} − 3k + 1)}{3} = ∑_{i=1}^{4} \binom{k}{i}\binom{15 − 3i − 1}{i − 1},

which is easy to prove.

In some cases, we can obtain a simpler formula for G(n, k; B). We illustrate this by Proposition 21. If B = {p} for p > 1, then

1.

G(pk, k; B^{c}) = (−1)^{k} + ∑_{i=1}^{k}(−1)^{k−i}\binom{k}{i}\binom{pi − 1}{i − 1}.

2. If n > pk, then

G(n, k; B^{c}) = ∑_{i=1}^{k}(−1)^{k−i}\binom{k}{i}\binom{n − pk + pi − 1}{i − 1}.

3. If n < pk, then

G(n, k; B^{c}) = ∑_{i=⌈ \frac{pk−n}{p−1} ⌉}^{k}(−1)^{k−i}\binom{k}{i}\binom{n − pk + pi − 1}{i − 1}.

Proof. In this case, (1) has the form

g(x, k; B^{c}) = [(x + x^{2} + ⋯) − x^{p}]^{k}.

Using the binomial theorem yields

g(x, k; B^{c}) = ∑_{i=0}^{k} \binom{k}{i}(−x^{p})^{k−i}(x + x^{2} + ⋯)^{i}

= (−1)^{k}x^{pk} + ∑_{i=1}^{k} \binom{k}{i}(−x^{p})^{k−i}(x + x^{2} + ⋯)^{i}.

For i ≥ 1, applying equation (x + x^{2} + ⋯)^{k} = ∑_{j=0}^{∞} \binom{j+i−1}{j}x^{i+j}, we obtain

g(x, k; B^{c}) = (−1)^{k}x^{pk} + ∑_{i=1}^{k} ∑_{j=0}^{∞}(−1)^{k−i}\binom{k}{i}\binom{j + i − 1}{j}x^{j+i+p(k−i)}.

It follows that

∑_{n=0}^{∞} G(n, k; B^{c})x^{n} = (−1)^{k}x^{pk} + ∑_{i=1}^{k} ∑_{j=0}^{∞}(−1)^{k−i}\binom{k}{i}\binom{j + i − 1}{j}x^{j+i+p(k−i)}.

We consider three cases:

1. n = pk. In this case, pk = j + i + p(k − i), which yields j = pi − i, and the statement holds.

2. n > pk. In this case, j = n − pk + pi − i > 0, and the statement holds.

3. n < pk. The equation j = n − pk + pi − i > 0 yields pk − n + j = (p − 1)i, that is, pk − n ≤ (p − 1)i. It follows that i ≥ \frac{pk−n}{p−1}, which proves the statement.

Note 22. These formulas are simpler than the formula derived from Example 11 in [1], but are essentially the same.

The referee suggested the following direct proof of 1.

Proof. If n = pk and l = p − 1, then [1, Identity 3] implies

G(pk, k; B^{c}) = \frac{k!}{(pk)!}B_{pk,k}(1!, …, (p − 1)!, 0, (p + 1)!, …)

= (−1)^{k} + ∑_{l=0}^{k−1}(−1)^{l}\binom{k}{l}\binom{p(k − l) − 1}{k − l − 1} = (−1)^{k} + ∑_{i=1}^{k}(−1)^{k−i}\binom{k}{i}\binom{pi − 1}{i − 1},

with the simple change of variables i = k − l.

The remaining two cases can be verified similarly.

Note 23. It is easy to obtain the appropriate formulas for f_{m}(n; B^{c}), and their interpretations in terms of restricted words.

Some related sequences in Sloane [7] are \underline{A005251}, \underline{A005252}, \underline{A005253}, \underline{A049856}, \underline{A051937}, \underline{A108758}, \underline{A180177}, and \underline{A205553}.

4 The case when f_{0} is periodic

We first consider the case when 1 appears periodically in the sequence f_{0}(1), f_{0}(2), . . ..

Proposition 24. Let p be a positive integer, and let q be a nonnegative integer. If A = {i : i ≡ q (mod p)}, then

G(n, k; A) = \binom{\frac{n−qk}{p} + k − 1}{k − 1},

for n − kq ≡ 0 (mod p). Otherwise, G(n, k; A) = 0.

Proof. In this case, we use formula (3). Each term of the sum in (3) is either 0 or 1. For the terms equal 1, each i_{t} must be of the form i_{t} = (j_{t} − 1)p + q, (j_{t} > 0). It follows that p(j_{1} + j_{2} + ⋯ + j_{k}) = n + (p − q)k. We conclude that G(n, k; A) = 0, if n − kq ≢ 0 (mod p).

Otherwise, we have

G(n, k; A) = ∑_{j_{1}+j_{2}+···+j_{k}= \frac{n+(p−q)k}{p}} 1,

which implies that

G(n, k; A) = \binom{\frac{n−qk}{p} + k − 1}{k − 1}.

Applying (2) in the case n = kq + rp, we obtain

Identity 25.

B_{kq+rp,k}(…, 0, q!, 0, …, 0, (q + p)!, 0 …) = \frac{(kq + rp)!}{k!}\binom{r + k − 1}{k − 1}

.

In particular, for q = 1, we replace n by n − k to obtain G(n, k; A) = \binom{\frac{n−k}{p} +k−1}{k−1}, if n − k ≡ 0 (mod p). Denoting \frac{n−k}{p} by i implies G(n, n − ip; A) = \binom{i+n−ip−1}{i}. Replacing n by n + 1 yields

Corollary 26.

G(n + 1, n + 1 − ip; A) = \binom{n − ip + i}{i}, for i = 0, …, ⌊\frac{n}{p}⌋ .  (16)

Summing over all i we obtain

f_{1}(n + 1; A) = ∑_{i=0}^{⌊ \frac{n}{p} ⌋} \binom{n − ip + i}{i}.

Remark 27. Note that f_{1}(n + 1; A) equals the number of compositions of n + 1 into parts congruent 1 mod p.

We state two particular cases. Remark 28. In the case p = 2, we obtain Equation (14) once again. For p = 3, the sequence \{f_{1}(n + 1, A) : n = 0, 1, …\} is Narayana’s cows sequence \underline{A000930}.

Let q > 1 be a positive integer, and let P = {p_{1}, p_{2}, …, p_{r}} be a set of positive integers. Define f_{0} in the following way:

f_{0}(n) = \begin{cases}1, & if n ≡ p (mod q), for some p ∈ P; \\ 0, & otherwise. \end{cases}

Proposition 29. The following formula holds

G(n, k; A) = ∑_{i=0}^{⌊ \frac{n−k}{q} ⌋} G(n − qi, k; P) · \binom{i + k − 1}{k − 1},

where G(n − qi, k; P) can be calculated as in Proposition 5. Proof. The function g(x, k; A) has the form

g(x, k; A) = (x^{p_{1}} + ⋯ + x^{p_{r}})^{k}(1 + x^{q} + x^{2q} + ⋯)^{k}.

It follows that

g(x, k; A) = ∑_{i=0}^{∞} G(i + k, k; P)x^{i+k} · ∑_{i=0}^{∞} \binom{i + k − 1}{k − 1}x^{iq}.

We conclude that

g(x, k; A) = ∑_{u=0}^{∞} ∑_{v=0}^{u} G(u − v + k, k; P) · \binom{v + k − 1}{k − 1}x^{u−v+k+vq}.  (17)

Comparing this equation with the expansion (1), we obtain that

n = u + (q − 1)v.

This implies that 0 ≤ u ≤ n so that (17) yields

G(n + k, k; A) = ∑_{u=0}^{n} ∑_{v=0}^{u} G(u − v + k, k; P) · \binom{v + k − 1}{k − 1}.

Changing the order of summation implies

G(n + k, k; A) = ∑_{v=0}^{n} ∑_{u=v}^{n} G(u − v + k, k; P) · \binom{v + k − 1}{k − 1}.

Since n = u + (q − 1)v, we obtain u − v = n − (q − 1)v − v = n − qv. The condition u ≥ v yields v ≤ \frac{n}{q}. Denoting v = i and taking n − k instead of n proves our statements. Note 30. It is easy to obtain the appropriate formula for f_{m}(n; A) and its interpretation in terms of restricted words.

We finish this section with a particular case. Corollary 31. Assume that f_{0} consists of the repeating string 110. Then

G(n, k; A) = ∑_{i=0}^{⌊ \frac{n−k}{3} ⌋} \binom{k}{n − k − 3i}\binom{i + k − 1}{k − 1}.

Proof. In this case q = 3, P = \{1, 2\} so that we have G(n − 3i, k; P) = \binom{k}{n−k−3i}, and the the statement is true. Corollary 32.

1. The array {G(n, k; A) : n = 1, 2, …; k = 1, 2, …, n} is the Riordan array of the pair (1, \frac{x(1+x)}{1−x^{3}}) , without the first column. \underline{A198295}

2. In particular, the cake number \binom{k}{3} + k gives the number of compositions of k + 3 into k parts, none of which is divided by 3. \underline{A000125}

Some other related sequences in Sloane [7] are \underline{A001590}, \underline{A003269}, \underline{A008998}, \underline{A008999}, \underline{A017898}, \underline{A052541}, \underline{A052917}, \underline{A052927}, \underline{A099524}, \underline{A126030}, and \underline{A159284}.

5 Some Euler-type identities

In this section, we derive some identities connecting different kinds of compositions. As a particular case, we obtain an Euler-type identity proved in Munagi [6].

By comparing equations (9), (11), and (16), we obtain

G(n, n − ip + i; 1, p) = G(n + p, i + 1; p, p + 1, …)

= G(n + 1, n + 1 − ip; 1, 1 + p, 1 + 2p, …) = \binom{n − ip + i}{i}, (i = 0, …, ⌊\frac{n}{p}⌋) .

In other words, we have Corollary 33. Let n, p be positive integers, and 0 ≤ i ≤ ⌊\frac{n}{p}⌋. The following sets have \binom{n−ip+i}{i} elements:

1. The set of compositions of n into n − ip + i parts in {1, p}.

2. The set of compositions of n + p into i + 1 parts in {p, p + 1, …}.

3. The set of compositions of n + 1 into n + 1 − ip parts in {1, 1 + p, 1 + 2p, …}. Since the numbers of all composition of n equals the sum of the numbers of compositions into 1, 2, …, n parts, we obtain Corollary 34. The following sets have the same number of elements:

1. The set of compositions of n + 1 into parts ≡ 1 (mod p).

2. The set of compositions of n into parts in {1, p}.

3. The set of compositions of n + p into parts greater than p − 1.

Note 35. Note that this corollary is the assertion of Theorem 1.2 in Munagi [6], where the bijections are obtained by using properties of zig-zag graphs. We also note that if N is the number of elements in the above sets, then

N = \begin{matrix}⌊ & \frac{n}{p} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{n − ip + i}{i}.

We finish the paper with the following Euler-type identities for the partial Bell polynomials.

Identity 36.

\frac{(n − ip + i)!}{n!}B_{n,n−ip+i}(1, 0, …, 0, p, 0, …) = \frac{(i + 1)!}{(n + p)!}B_{n+p,i+1}(0, … 0, p, p + 1, …)

= \frac{(n + 1 − ip)!}{(n + 1)!}B_{n+1,n+1−ip}(1, 0, …, 0, 1 + p, 0 …, 0, 1 + 2p, 0, …).

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] S. Eger, Restricted weighted integer compositions and extended binomial coefficients, J. Integer Seq. 16 (2013), Article 13.1.3.

[3] S. Eger, Some elementary congruences for the number of weighted integer compositions, J. Integer Seq. 18 (2015), Article 15.4.1.

[4] S. Eger, Identities for partial Bell polynomials derived from identities for weighted integer compositions, Aequat. Math. 90 (2016), 299–306.

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

[6] A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Article 60.

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

2000 Mathematics Subject Classification: Primary 05A10; Secondary 11B39. Keywords: binary word, integer composition, restricted word, enumeration.

(Concerned with sequences \underline{A000027}, \underline{A000125}, \underline{A000217}, \underline{A000270}, \underline{A000290}, \underline{A000326}, \underline{A000384}, \underline{A000566}, \underline{A000578}, \underline{A000930}, \underline{A000931}, \underline{A001590}, \underline{A002411}, \underline{A002414}, \underline{A003269}, \underline{A005251}, \underline{A005252}, \underline{A005253}, \underline{A008778}, \underline{A008779}, \underline{A008998}, \underline{A008999}, \underline{A017817}, \underline{A017898}, \underline{A049856}, \underline{A051937}, \underline{A052541}, \underline{A052917}, \underline{A052920}, \underline{A052927}, \underline{A071675}, \underline{A079960}, \underline{A079976}, \underline{A096000}, \underline{A099524}, \underline{A108750}, \underline{A108758}, \underline{A117760}, \underline{A124304}, \underline{A126030}, \underline{A159284}, \underline{A180177}, \underline{A191238}, \underline{A198295}, \underline{A205553}, and \underline{A253189}.)

Received January 7 2016; revised versions received June 13 2016; June 28 2016; July 10 2016. Published in Journal of Integer Sequences, August 29 2016.

Return to Journal of Integer Sequences home page.