On Binomial Identities in Arbitrary Bases

Lin Jiu^{1}

Department of Mathematics Tulane University New Orleans, LA 70118 USA

                    ljiu@tulane.edu

Christophe Vignat Department of Mathematics Tulane University New Orleans, LA 70118 USA and Department of Physics Université Orsay Paris Sud 91405 Orsay Cedex France

                  cvignat@tulane.edu

Abstract

We first extend the digital binomial identity as given by Nguyen et al. to an identity in an arbitrary base b, by introducing the b-ary binomial coefficients. Then, we study the properties of these coefficients such as their orthogonality, their link with Lucas’ theorem and their extension to multinomial coefficients. Finally, we analyze the structure of the corresponding b-ary Pascal-like triangles.

1Author’s current address: Research Institute for Symbolic Computation, Johannes Kepler University, Linz, A-4040 Linz, Austria; ljiu@risc.uni-linz.ac.at .

1 Introduction

In a series of recent articles, Nguyen [9, 10], and then Nguyen and Mansour [7, 8], have introduced different versions of the binomial identity, in which the usual integer powers are replaced by arithmetical functions that count the digits of these powers in their representation in base b. Allouche and Shallit [1, Chap. 3], for example, provide a variety of properties of these arithmetical functions.

Given a positive integer n, let S_{b}^{(k)} (n) denote the number of k’s in the b-ary expansion of n:

n = ∑_{i} n_{i}b^{i}.  (1)

Also let S_{b} (n) denote the sum of all the digits, namely

S_{b} (n) = ∑_{i} n_{i} = ∑_{k=0}^{b−1} kS_{b}^{(k)} (n) .  (2)

The main extension of the binomial identity is

(X + Y)^{S_{2}(n)} = ∑_{0≤k≤n (k,n−k) carry-free} X^{S_{2}(k)}Y^{S_{2}(n−k)},  (3)

which was originally given by Callan [3] and also by Nguyen [9, 10] in the case b = 2. Here, the sum on the right-hand side is over all values of k such that the addition of k and n − k in base 2 is carry-free. Note that, in the general case of base b, this carry-free condition is equivalent to S_{b} (k) + S_{b} (n − k) = S_{b} (n). Thus, identity (3) can be restated equivalently in the beautifully symmetric form

(X + Y)^{S_{2}(n)} = ∑_{S_{2}(k)+S_{2}(n−k)=S_{2}(n)} X^{S_{2}(k)}Y^{S_{2}(n−k)}.

Nguyen [9] proved identity (3) by using a polynomial generalization of the Sierpinski triangle, which is the Pascal triangle modulo 2.

Nguyen [10, Thm. 2] also gives an extension of (3) to an arbitrary base b, in the form

∏_{i=0}^{N−1} \binom{x + y + n_{i} − 1}{n_{i}} = ∑_{0≤k≲_{b}n} ∏_{i=0}^{N−1} \binom{x + k_{i} − 1}{k_{i}}\binom{x + n_{i} − k_{i} − 1}{n_{i} − k_{i}}.  (4)

Here, suppose k and n have the following expansions in base b:

n = ∑^{N−1} ; l=0n_{l}b^{l} and k = ∑^{N−1} ; l=0k_{l}b^{l}.  (5)

Then, the summation range 0 ≤ k ≲_{b} n means that the sum is over all positive integers k such that k_{i} ≤ n_{i}, for all i ∈ {0, …, N − 1}. This summation range is also equivalent to summing over all values of k such that the addition of k and n − k is carry free.

The aim of this paper is to show that these results are a consequence of an elementary identity stated in the next section. This approach gives a more accessible form to Nguyen’s results and provides a number of generalizations. The paper is organized as follows.

In Section 2, we state a general formula on the sum over all the digits of an integer number. It is an identity involving sequences of binomial type, which lays the foundation for the remaining sections. In Section 3, we provide a new version of the binomial identity in base b that involves newly defined b-ary binomial coefficients. Then, some of the properties of these coefficients, such as their role in Lucas’ theorem and an orthogonality property, are presented in Section 4. Section 5 exhibits the construction rules for a Pascal-type triangle built from these coefficients. Finally, Section 6 presents, besides an historical approach, some open questions.

2 A general formula

Nguyen proves (4) by using a polynomial extension of Sierpinski’s matrices. We introduce here a more elementary approach. First, we remark that (4) can be restated equivalently as

∏_{i=0}^{N−1} \frac{(x + y)_{n_{i}}}{n_{i}!} = ∏_{i=0}^{N−1} ∑_{0≤k_{i}≤n_{i}} \frac{(x)_{k_{i}}}{k_{i}!} \frac{(y)_{n_{i}−k_{i}}}{(n_{i} − k_{i})!},  (6)

where (x)_{k} = \frac{Γ(x+k)}{Γ(x)} is the Pochhammer symbol. Next we realize that (6) holds in fact component-wise, i.e., for all i ∈ {0, …, N − 1} and arbitrary positive integers n_{i}, we have

\frac{(x + y)_{n_{i}}}{n_{i}!} = ∑_{k_{i}=0}^{n_{i}} \frac{(x)_{k_{i}}}{k_{i}!} \frac{(y)_{n_{i}−k_{i}}}{(n_{i} − k_{i})!},  (7)

which is actually the Chu-Vandermonde identity. Since (7) is a consequence of the fact that the Pochhammer sequence ((x)_{k})_{k≥0} is of binomial type^{2}, we therefore have the following result.

Proposition 1. Assume that (a_{n})_{n≥0}, (b_{n})_{n≥0}, and (c_{n})_{n≥0} are three sequences related as

c_{n} = ∑_{k=0}^{n} \binom{n}{k}a_{k}b_{n−k}.  (8)

p_{n} (x + y) = ∑_{k=0}^{n} \binom{n}{k}p_{k} (x) p_{n−k} (y) .

2A sequence of polynomials p_{n} (x) is of binomial type [11, Thm. 2.4.7, p. 26] if it satisfies the convolution identity

Using notation from (5), we have

∏_{i=0}^{N−1} \frac{c_{n_{i}}}{n_{i}!} = ∑_{0≤k≲_{b}n} ∏_{i=0}^{N−1} \frac{a_{k_{i}}}{k_{i}!} \frac{b_{n_{i}−k_{i}}}{(n_{i} − k_{i})!},  (9)

where the sum on the right-hand side is over all values of k such that 0 ≤ k ≲_{b} n, or equivalently such that the addition of k and n − k is carry-free in base b.

We now apply formula (9) to obtain a generalization of the binomial identity in an arbitrary base b.

3 A generalized binomial identity

Theorem 2. With the notation (1), (2), and (5), the identity

(X + Y)^{S_{b}(n)} = ∑_{k=0}^{n} \binom{n}{k}_{b}X^{S_{b}(k)}Y^{S_{b}(n−k)}  (10)

holds for all X, Y ∈ ℂ, where the b-ary binomial coefficients \binom{n}{k}_{b} are given by

\binom{n}{k}_{b} = N−1 ; ∏_{l=0}\binom{n_{l}}{k_{l}}.  (11)

Proof. By (11), we have \binom{n}{k}_{b} = 0 if k_{l} > n_{l} holds for at least one value of l. Therefore, it suffices to assume 0 ≤ k_{l} ≤ n_{l} for all l ∈ {0, …, N − 1}. As a result, we have

n − k = ∑_{l=0}^{N−1} (n_{l} − k_{l}) b^{l},

which is equivalent to

S_{b} (k) + S_{b} (n − k) = S_{b} (n) ,

i.e., to the assumption that the addition of k and n − k is carry-free in base b, as already mentioned.

We apply the identity (9) in Proposition 1 to obtain

∏_{l=0}^{N−1} c_{n_{l}} = ∏_{l=0}^{N−1} n_{l}! ∑_{k_{l}=0}^{n_{l}} \frac{a_{k_{l}}}{k_{l}!} · \frac{b_{n_{l}−k_{l}}}{(n_{l} − k_{l})!} = ∑_{S_{b}(k)+S_{b}(n−k)=S_{b}(n)} ( ∏_{l=0}^{N−1} \binom{n_{l}}{k_{l}}a_{k_{l}}b_{n_{l}−k_{l}}) .  (12)

The choice

c_{n_{l}} = (X + Y)^{n_{l}} , a_{k_{l}} = X^{k_{l}}, and b_{k_{l}} = Y^{k_{l}},

which satisfies the convolution identity (8), leads to

∏_{l=0}^{N−1} (X + Y)^{n_{l}} = ∑_{S_{b}(k)+S_{b}(n−k)=S_{b}(n)} ( ∏_{l=0}^{N−1} \binom{n_{l}}{k_{l}}X^{k_{l}}Y^{n_{l}−k_{l}}) .

Notice that the left-hand side reads

∏_{l=0}^{N−1} (X + Y)^{n_{l}} = (X + Y)^{N−1 ; ∑_{l=0}n_{l}} = (X + Y)^{S_{b}(n)} ,

while the right-hand side can be written as

∏_{l=0}^{N−1} ∑_{k_{l}=0}^{n_{l}} \binom{n_{l}}{k_{l}}X^{k_{l}}Y^{n_{l}−k_{l}} = ∑_{k=0}^{n} ( ∏_{l=0}^{N−1} \binom{n_{l}}{k_{l}}) X^{S_{b}(k)}Y^{S_{b}(n−k)}.

This completes the proof.

Remark 3. When n < b, the b-ary expansion of n consists of only one digit, i.e., n = n_{0}. And since k ≤ n < b, we also have n − k < b. Thus,

S_{b} (n) = n_{0} = n, S_{b} (k) = k, S_{b} (n − k) = n − k, and \binom{n}{k}_{b} = \binom{n}{k},

so that (10) reduces to the usual binomial identity

(X + Y)^{n} = ∑_{k=0}^{n} \binom{n}{k}X^{k}Y^{n−k}.

Corollary 4. (I) In the binary case b = 2, we recover the identity by Callan and Nguyen:

(X + Y)^{S_{2}(n)} = ∑_{S_{2}(k)+S_{2}(n−k)=S_{2}(n)} X^{S_{2}(k)}Y^{S_{2}(n−k)},

by noticing that the coefficients \binom{n_{l}}{k_{l}} take the only values \binom{0}{0} = \binom{1}{0} = \binom{1}{1} = 1 and \binom{0}{1} = 0.

(II) In the case b = 3, \binom{n}{k}_{3} = 0 if S_{3} (k) + S_{3} (n − k) ≠ S_{3} (n). Otherwise, all \binom{n_{l}}{k_{l}} = 1 except for the case n_{l} = 2 and k_{l} = 1 such that \binom{n_{l}}{k_{l}} = 2. Therefore, we have the equivalent expression

(X + Y)^{S_{3}(n)} = ∑_{S_{3}(k)+S_{3}(n−k)=S_{3}(n)} (2^{S_{3}^{(2)}(n)−S_{3}^{(2)}(k)−S_{3}^{(2)}(n−k)}) X^{S_{3}(k)}Y^{S_{3}(n−k)}.

Remark 5. Different choices of the sequences (a_{n})_{n≥0}, (b_{n})_{n≥0}, and (c_{n})_{n≥0} lead to different identities. For instance, another choice is the Pochhammer coefficients

c_{n} = (X + Y)_{n} , a_{n} = (X)_{n} , and b_{n} = (Y)_{n} .

The generating function

∑_{n≥0} \frac{(X)_{n}}{n!} z^{n} = (1 − z)^{−X}

shows that the convolution property (8) holds. Then from (12), we deduce

∏_{l=0}^{N−1} \frac{(X + Y)_{n_{l}}}{n_{l}!} = ∑_{S_{b}(k)+S_{b}(n−k)=S_{b}(n)} ( ∏_{l=0}^{N−1} \frac{X_{k_{l}}}{k_{l}!} · \frac{Y_{n_{l}−k_{l}}}{(n_{l} − k_{l})!}) ,

or equivalently, we recover the result [10, Thm. 2]

∏_{l=0}^{N−1} \binom{X + Y + n_{l} − 1}{n_{l}} = ∑_{0≤k≲_{b}n} ( ∏_{l=0}^{N−1} \binom{X + k_{l} − 1}{k_{l}}\binom{Y + n_{l} − k_{l} − 1}{n_{l} − k_{l}}) .

Then, for the binary case b = 2, n_{l} ∈ {0, 1} yields that for all l ∈ {0, …, N − 1},

(X + Y)_{n_{l}} = \begin{cases}X + Y, & if n_{l} = 1; \\ 0, & if n_{l} = 0. \end{cases}

Again, we recover

(X + Y)^{S_{2}(n)} = ∑_{S_{2}(k)+S_{2}(n−k)=S_{2}(n)} X^{S_{2}(k)}Y^{S_{2}(n−k)}.

4 Properties of the b-ary binomial coefficients

We study in this section some properties of the b-ary binomial coefficients defined by (11).

4.1 Generating function

Theorem 6. A generating function for the b-ary binomial coefficients \binom{n}{k}_{b} is

∑_{k=0}^{n} \binom{n}{k}_{b}x^{k} = ∏_{l=0}^{N−1} (1 + x^{b^{l}})^{n_{l}} .  (13)

Proof. Define the right-hand side of (13) as P (x), a polynomial of degree

deg P = N−1 ; ∑_{l=0}n_{l}b^{l} = n.

Let p_{k}^{(n)} denote the coefficient of x^{k} in P (x) and remark that p_{k}^{(n)} = 0 if and only if there is a carry in the addition of k and n − k in base b. An elementary enumeration shows

p_{k}^{(n)} = \binom{n_{N−1}}{k_{N−1}}\binom{n_{N−2}}{k_{N−2}} ⋯ \binom{n_{0}}{k_{0}},

which gives the desired result.

4.2 Multinomial version

The next property is the extension of (10) to the multinomial case.

Theorem 7. Define the b-ary multinomial coefficient by

\binom{n}{k_{1}, …, k_{m}}_{b} = ∏_{l=0}^{N−1} \binom{n_{l}}{(k_{1})_{l} , …, (k_{m})_{l}},

where (k_{i})_{l} denotes the rank-l digit in the expansion k_{i} = ∑_{l} (k_{i})_{l} b^{l} of k_{i} in base b. Then

(X_{1} + ⋯ + X_{m})^{S_{b}(n)} = ∑_{k_{1},...,k_{m}} \binom{n}{k_{1}, …, k_{m}}_{b}X_{1}^{S_{b}(k_{1})} ⋯ X_{m}^{S_{b}(k_{m})}.

Proof. The proof is straightforward and follows by induction on the value of m, using the binomial expansion (10) and the definition (11) of the b-ary binomial coefficients.

4.3 Chu-Vandermonde identity

This section provides an extension to an arbitrary base b of the Chu-Vandermonde identity [12, eq. (3), p. 8].

Theorem 8. Suppose that the addition of m and n is carry-free in base b, then

\binom{m + n}{r}_{b} = ∑_{k=0}^{r} \binom{m}{k}_{b}\binom{n}{r − k}_{b}.  (14)

Proof. Let N be the maximum number of digits among the numbers m, n, and r. Also let

m = ∑^{N−1} ; l=0m_{l}b^{l}, n = ∑^{N−1} ; l=0n_{l}b^{l}, and r = ∑^{N−1} ; l=0r_{l}b^{l}.

Since the addition of m and n is carry-free, we have for all l ∈ {0, …, N − 1},

m_{l} + n_{l} < b and m + n = ∑^{N−1} ; l=0 (m_{l} + n_{l}) b^{l}.

Thus, we first apply the ordinary Chu-Vandermonde identity digit-wise to get, for all l ∈ {0, …, N − 1},

\binom{m_{l} + n_{l}}{r_{l}} = ∑_{k_{l}=0}^{r_{l}} \binom{m_{l}}{k_{l}}\binom{n_{l}}{r_{l} − k_{l}}.

Then we take the product over l of both sides to obtain

\binom{m + n}{r}_{b} = ∏_{l=0}^{N−1} \binom{m_{l} + n_{l}}{r_{l}} = ∏_{l=0}^{N−1} ∑_{k_{l}=0}^{r_{l}} \binom{m_{l}}{k_{l}}\binom{n_{l}}{r_{l} − k_{l}} = ∑_{0≤k≲_{b}r} \binom{m}{k}_{b}\binom{n}{r − k}_{b}.

Note that the summation condition 0 ≤ k ≲_{b} r can be replaced by 0 ≤ k ≤ r, since when k + (r − k) is not carry-free, it means that k_{j} > r_{j} for some j ∈ {0, …, N − 1}. In this case,

\binom{n}{r − k}_{b} = (∏_{l=0}^{j−1} \binom{n_{l}}{r_{l} − k_{l}}) \binom{n_{j}}{r_{j} − k_{j}} ( ∏_{l=j+1}^{N−1} \binom{n_{l}}{r_{l} − k_{l}}) = 0,

and the corresponding term has no contribution to the sum.

Remark 9. (I) Another proof could be obtained by considering generating functions. It suffices to notice that if the addition m + n is carry-free,

( ∏_{l=0}^{N−1} (1 + x^{b^{l}})^{n_{l}}) ( ∏_{l=0}^{N−1} (1 + x^{b^{l}})^{m_{l}}) = ∏_{l=0}^{N−1} (1 + x^{b^{l}})^{m_{l}+n_{l}} .

(II) In the case when the addition m + n is not carry-free, the identity fails. Take, for example, b = 2 and

m = n = r = 1 ⇒ m + n = 2 = 1 · 2^{1} + 0 · 2^{0}.

Then,

\binom{m + n}{r}_{b} = \binom{2}{1}_{2} = \binom{1 · 2^{1} + 0 · 2^{0}}{0 · 2^{1} + 1 · 2^{0}}_{2} = \binom{1}{0}\binom{0}{1} = 0.

On the other hand,

∑_{0≤k≲_{b}r} \binom{m}{k}_{b}\binom{n}{r − k}_{b} = ∑_{k=0}^{1} \binom{1}{k}_{2}\binom{1}{1 − k}_{2} = \binom{1}{0}_{2}\binom{1}{1 − 0}_{2} + \binom{1}{1}_{2}\binom{1}{1 − 1}_{2} = 2.

4.4 Symmetry and recurrence

Theorem 10. The b-ary binomial coefficients satisfy

1. the symmetry property

\binom{n}{k}_{b} = \binom{n}{n − k}_{b},

2. when \binom{n}{k}_{b} ≠ 0, the recurrence

\binom{n}{k}_{b} = \binom{n − 1}{k − 1}_{b} + \binom{n − 1}{k}_{b},  (15)

Proof. The symmetry property is easily deduced from definition (11) and the invariance of each \binom{n_{l}}{k_{l}} under the exchange k_{l} ↔ n_{l} − k_{l} for each digit. For the recurrence property, assume that both k and n have a non-zero lowest rank digit, i.e., k_{0} > 0 and n_{0} > 0. Then, (n − 1)_{0} = n_{0} − 1, (k − 1)_{0} = k_{0} − 1,

\binom{n − 1}{k − 1}_{b} = \binom{n_{N−1}}{k_{N−1}} ⋯ \binom{n_{1}}{k_{1}}\binom{n_{0} − 1}{k_{0} − 1}, and \binom{n − 1}{k}_{b} = \binom{n_{N−1}}{k_{N−1}} ⋯ \binom{n_{1}}{k_{1}}\binom{n_{0} − 1}{k_{0}}.

We deduce that

\binom{n − 1}{k − 1}_{b} + \binom{n − 1}{k}_{b} = \binom{n_{N−1}}{k_{N−1}} ⋯ \binom{n_{1}}{k_{1}} (\binom{n_{0} − 1}{k_{0} − 1} + \binom{n_{0} − 1}{k_{0}}) = \binom{n}{k}_{b}.

This argument extends easily to the case where zero components appear in the pair (k_{0}, n_{0}).

Remark 11. As suggested by the referee, the recurrence (15) can also be extended to higher digits, which leads to

\binom{n}{k}_{b} = \binom{n − b^{j}}{k − b^{j}}_{b} + \binom{n − b^{j}}{k}_{b},

for all j ∈ {0, …, N − 1}, by a similar proof.

4.5 Link with Lucas’ theorem

The definition (11) will look familiar to those readers who have already met Lucas’ famous theorem [5], which we restate here.

Theorem 12. [Lucas] For a prime number p, the binomial coefficient \binom{n}{k} satisfies the congruence

\binom{n}{k} ≡ \binom{n_{N−1}}{k_{N−1}} ⋯ \binom{n_{0}}{k_{0}} (mod p).

Remark 13. (I) Note that, under the same condition, Lucas’ theorem is concisely rephrased in our notation as

\binom{n}{k} ≡ \binom{n}{k}_{p} (mod p).

Lucas’ theorem becomes obvious by considering the generating function (13) and noting an elementary congruence:

∑_{k=0}^{n} \binom{n}{k}_{p}x^{k} = ∏_{l=0}^{N−1} (1 + x^{p^{l}})^{n_{l}} ≡ (1 + x)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k} (mod p).

(II) The Sierpinski matrix, which Nguyen et al. use to prove their results, contains the entries \binom{n}{k} mod p. These coefficients do not coincide with \binom{n}{k}_{p} studied here, but are congruent to them.

4.6 Orthogonality relations

There are many elementary identities involving the usual binomial coefficients that can be extended to the case of the b-ary binomial coefficients. Here, we show one example.

Example 14. Assume, ∀n ∈ ℕ, two sequences (a_{n})_{n≥0} and (c_{n})_{n≥0} are related by

a_{n} = n ; ∑_{k=0} (−1)^{k} \binom{n}{k}c_{k}.

Then,

c_{n} = n ; ∑_{k=0} (−1)^{k} \binom{n}{k}a_{k},

which is known as an inverse relation [12, ex. 2, p. 4]. Note that this inverse relation is equivalent to the orthogonality conditions

∑_{k=j}^{n} \binom{n}{k}\binom{k}{j} (−1)^{k+j} = δ_{n,j} = \begin{cases}1, & if j = n; \\ 0, & otherwise. \end{cases}

The generalization to the b-ary case is as follows.

Theorem 15. The b-ary binomial coefficients satisfy the orthogonality relations

∑_{k=0}^{n} \binom{n}{k}_{b}\binom{k}{j}_{b} (−1)^{S_{b}(k)+S_{b}(j)} = δ_{n,j}.

As a consequence, if two sequences (a_{n})_{n≥0} and (c_{n})_{n≥0} satisfy

a_{S_{b}(n)} = n ; ∑_{k=0} (−1)^{S_{b}(k)} \binom{n}{k}_{b}c_{S_{b}(k)},

then

c_{S_{b}(n)} = n ; ∑_{k=0} (−1)^{S_{b}(k)} \binom{n}{k}_{b}a_{S_{b}(k)}.

Proof. Since

\binom{n}{k}_{b} = ∏_{l=1}^{N−1} \binom{n_{j}}{k_{l}}, \binom{k}{j}_{b} = ∏_{l=1}^{N−1} \binom{k_{l}}{j_{l}}, S_{b} (k) = ∑_{l=0}^{N−1} k_{l}, and S_{b} (j) = ∑_{l=0}^{N−1} j_{l},

we deduce

∑_{k=j}^{n} \binom{n}{k}_{b}\binom{k}{j}_{b} (−1)^{S_{b}(k)+S_{b}(j)} = ∏_{l=1}^{N−1} ∑_{k_{l}=j_{l}}^{n_{l}} \binom{n_{j}}{k_{l}}\binom{k_{l}}{j_{l}} (−1)^{k_{l}+j_{l}} = ∏_{l=1}^{N−1} δ_{n_{l},j_{l}} = δ_{n,j}.

5 Pascal-like triangles

In this section, we study the structure of Pascal-like triangles built from the b-ary binomial coefficients \binom{n}{k}_{b}. Let us start with two examples, where we systematically replace each null binomial entry with a dot “.” symbol in order to make the structure of the triangle more visible. Here we underline the fact that these null entries correspond exactly to the pairs (n, k) for which the addition of k and n − k is not carry-free in base b.

Example 16. In base b = 3, the top 9 rows of the Pascal-like triangle for the ternary binomial coefficients are

T_{2}^{(3)} = \begin{aligned}& & & & & & & & 1 \\ & & & & & & & 1 & & 1 \\ & & & & & & 1 & & 2 & & 1 \\ & & & & & 1 & & . & & . & & 1 \\ & & & & 1 & & 1 & & . & & 1 & & 1 \\ & & & 1 & & 2 & & 1 & & 1 & & 2 & & 1 \\ & & 1 & & . & & . & & 2 & & . & & . & & 1 \\ & 1 & & 1 & & . & & 2 & & 2 & & . & & 1 & & 1 \\ 1 & & 2 & & 1 & & 2 & & 4 & & 2 & & 1 & & 2 & & 1 \end{aligned}

Now, let

T_{1}^{(3)} = 1 1  1 1  2  1

denote the top 3 rows of T_{2}^{(3)} and also let

∗ = \begin{aligned}. & & . \\ & . \end{aligned} = 0 0 0

be the elementary reverse triangle containing only zero entries. Then, we remark that

T_{2}^{(3)} = \begin{aligned}& & T_{1}^{(3)} \\ & T_{1}^{(3)} & ∗ & T_{1}^{(3)} \\ T_{1}^{(3)} & ∗ & 2T_{1}^{(3)} & ∗ & T_{1}^{(3)} \end{aligned}

and furthermore, introducing the notation

T_{2}^{(3)} = T_{1}^{(3)} ⊗ T_{1}^{(3)},

we deduce, for all m ∈ ℕ,

T_{m}^{(3)} = (T_{1}^{(3)})^{⊗m} .

Here, the Kronecker product ⊗ will be defined and discussed in Proposition 18 below. Example 17. In base 4, the first 16 rows of the Pascal-like triangle are as follows.

T_{2}^{(4)} = \begin{aligned}& & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & 1 & & 1 \\ & & & & & & & & & & & & & 1 & & 2 & & 1 \\ & & & & & & & & & & & & 1 & & 3 & & 3 & & 1 \\ & & & & & & & & & & & 1 & & . & & . & & . & & 1 \\ & & & & & & & & & & 1 & & 1 & & . & & . & & 1 & & 1 \\ & & & & & & & & & 1 & & 2 & & 1 & & . & & 1 & & 2 & & 1 \\ & & & & & & & & 1 & & 3 & & 3 & & 1 & & 1 & & 3 & & 3 & & 1 \\ & & & & & & & 1 & & . & & . & & . & & 2 & & . & & . & & . & & 1 \\ & & & & & & 1 & & 1 & & . & & . & & 2 & & 2 & & . & & . & & 1 & & 1 \\ & & & & & 1 & & 2 & & 1 & & . & & 2 & & 4 & & 2 & & . & & 1 & & 2 & & 1 \\ & & & & 1 & & 3 & & 3 & & 1 & & 2 & & 6 & & 6 & & 2 & & 1 & & 3 & & 3 & & 1 \\ & & & 1 & & . & & . & & . & & 3 & & . & & . & & . & & 3 & & . & & . & & . & & 1 \\ & & 1 & & 1 & & . & & . & & 3 & & 3 & & . & & . & & 3 & & 3 & & . & & . & & 1 & & 1 \\ & 1 & & 2 & & 1 & & . & & 3 & & 6 & & 3 & & . & & 3 & & 6 & & 3 & & . & & 1 & & 2 & & 1 \\ 1 & & 3 & & 3 & & 1 & & 3 & & 9 & & 9 & & 3 & & 3 & & 9 & & 9 & & 3 & & 1 & & 3 & & 3 & & 1 \end{aligned} .

Starting from the elementary triangles:

T_{1}^{(4)} = 1 1  1 1  2  1 1  3  3  1 and ∗ = \begin{aligned}. & & . & & . \\ & . & & . \\ & & . \end{aligned} = 0  0  0 0  0 0 ,

we similarly obtain that

T_{2}^{(4)} = \begin{aligned}& & & T_{1}^{(4)} \\ & & T_{1}^{(4)} & ∗ & T_{1}^{(4)} \\ & T_{1}^{(4)} & ∗ & 2T_{1}^{(4)} & ∗ & T_{1}^{(4)} \\ T_{1}^{(4)} & ∗ & 3T_{1}^{(4)} & ∗ & 3T_{1}^{(4)} & ∗ & T_{1}^{(4)} \end{aligned}

and more generally

T_{m}^{(4)} = (T_{1}^{(4)})^{⊗m} .

These observations are now extended to an arbitrary base b.

Proposition 18. The structure of the triangle built from the coefficients \binom{n}{k}_{b} satisfies

1. the top b rows, denoted by T_{1}^{(b)}, coincide with the top b rows of the usual Pascal triangle;

2. for all m > 1, T_{m}^{(b)} is obtained from T_{m−1}^{(b)} by the Kronecker product

T_{m}^{(b)} = T_{1}^{(b)} ⊗ T_{m−1}^{(b)}

defined by

T_{m}^{(b)} = \begin{aligned}& & & \binom{0}{0}T_{m−1}^{(b)} \\ & & \binom{1}{0}T_{m−1}^{(b)} & & \binom{1}{1}T_{m−1}^{(b)} \\ & ... & & & & ... \\ \binom{b−1}{0}T_{m−1}^{(b)} & & … & \binom{b−1}{j}T_{m−1}^{(b)} & … & & \binom{b−1}{b−1}T_{m−1}^{(b)} \end{aligned}

so that

T_{m}^{(b)} = T_{1}^{(b)} ⊗ ⋯ ⊗ T_{1}^{(b)} = (T_{1}^{(b)})^{⊗m};

3. since

#rows (T_{m}^{(b)}) = b × #rows (T_{m−1}^{(b)}) ,

the triangle T_{m}^{(b)} has b^{m} rows;

4. the bottom row of the triangle T_{m}^{(b)} has b^{m} entries.

Proof. These properties are a direct consequence of (11). Since properties 3 and 4 are elementary, only properties 1 and 2 need to be verified. Here, we prove them by induction.

(i) For m = 1, T_{1}^{(b)} consists of the first b rows of the triangle made of the b-ary binomial coefficients \binom{n}{k}_{b} where

0 ≤ k ≤ n ≤ b − 1,

so that the b-ary expression of n consists of a single digit: n = n_{0}. In this case, \binom{n}{k}_{b} coincides with the usual binomial coefficients \binom{n}{k}. Thus, the first b rows coincide with those of the Pascal triangle (see also Remark 3).

(ii) Consider T_{m}^{(b)} by assuming that properties 1 and 2 hold for T_{1}^{(b)}, …, T_{m−1}^{(b)}. Then, the b^{m} elements of T_{m}^{(b)} correspond exactly to the case

0 ≤ n ≤ b + ⋯ + b^{m} − 1,

which implies that n has at most m digits, namely

n = n_{m−1}b^{m−1} + ⋯ + n_{0}.

Thus,

\binom{n}{k}_{b} = \binom{n_{m−1}}{k_{m−1}} \underbrace{m−2 ; ∏_{l=0}\binom{n_{l}}{k_{l}}}_{copy of T_{m−1}^{(b)}}.

Since 0 ≤ n_{m−1} ≤ b − 1, the first factor \binom{n_{m−1}}{k_{m−1}} gives a copy of T_{1}^{(b)} while the rest of the

product gives a copy of T_{m−1}^{(b)}. Hence, by induction,

T_{m}^{(b)} = (T_{1}^{(b)})^{⊗m} .

6 Historical perspective and conclusion

Generalizations of the usual binomial coefficients have been extensively studied in many different ways. In particular, Knuth and Wilf [6] define the generalized binomial coefficients associated with a sequence of numbers (C_{n})_{n≥0} by

\binom{m}{n}_{C} = \frac{C_{m}C_{m−1} ⋯ C_{n+1}}{C_{m−n}C_{m−n−1} ⋯ C_{1}} ,

and study their divisibility by powers of a prime p. Ball et al. [2] introduce the b-ary binomial coefficients as those of Knuth and Wilf built from a sequence (C_{n})_{n≥0} defined by

C_{n} = b^{ν_{b}(n)},

i.e., the highest power of b that divides n, and study the arithmetic properties of these coefficients.

In quantum physics, Gazeau et al. [4] introduce the same generalized binomial coefficients as Knuth and Wilf to model the influence of correlations between the states of quantum systems.

We note that the b-ary binomial coefficients defined by (11) and studied here, look similar to the ones of Knuth and Wilf. However, we failed to find a sequence (C_{k})_{k≥0} such that

\binom{n}{k}_{b} = \binom{n}{k}_{C}.

This may explain why we were unable to find a reference where these b-ary binomial coefficients appear explicitly.

Nguyen [10] has shown how the digital binomial identity can be generalized to sequences of the Sheffer type such as the Bernoulli or Hermite polynomials. An important question that remains about these b-ary binomial coefficients is to know if they satisfy identities which are not of the Sheffer type. The example of the Chu-Vandermonde identity (14) already shows that even simple linear identities do not extend automatically to the case of b-ary binomial coefficients, indicating that extension to more difficult cases may be even trickier. This will be the subject of future work.

7 Acknowledgments

The work of the second author was partially supported by the iCODE Institute, Research Project of the Idex Paris-Saclay. The authors wish to thank Victor Hugo Moll for his support and discussions. The authors also thank Hong Diep Nguyen for his valuable comments and the anonymous reviewer for the careful analysis of the manuscript. Finally, the authors thank Tanay Wakhare for his extension of the Chu-Vandermonde identity.

References

[1] J. P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2009.

[2] T. Ball, T. Edgar, and D. Juda, Dominance orders, generalized binomial coefficients, and Kummer’s theorems, Math. Mag. 87 (2014), 135–143.

[3] D. Callan, Sierpinski’s triangle and the Prouhet-Thue-Morse word, preprint, 2006,

    http://arxiv.org/abs/math/0610932.

[4] E. M. F. Curado, J. P. Gazeau, and L. M. C. S. Rodrigues, On a generalization of the binomial distribution and its Poisson-like limit, J. Stat. Phys. 146 (2012), 264–280.

[5] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589–592.

[6] D. E. Knuth and H. S. Wilf, The power of a prime that divides a generalized binomial coefficient, J. Reine Angew. Math. 396 (1989), 212–219.

[7] T. Mansour and H. D. Nguyen, A q-digital binomial theorem, preprint, 2015,

    http://arxiv.org/abs/1506.07945.

[8] T. Mansour and H. D. Nguyen, A digital binomial theorem for Sheffer sequences,

    preprint, 2015, http://arxiv.org/abs/1510.08529.

[9] H. D. Nguyen, A digital binomial theorem, preprint, 2014,

    http://arxiv.org/abs/1412.3181.

[10] H. D. Nguyen, A generalization of the digital binomial theorem, J. Integer Sequences 18 (2015), Article 15.5.7.

[11] S. Roman, The Umbral Calculus, Dover Publications, 2005.

[12] J. Riordan, Combinatorial Identities, R. E. Krieger Pub. Co., 1979.

2010 Mathematics Subject Classification: Primary 05C30; Secondary 05C78. Keywords: b-ary expansion, b-ary binomial coefficient, Lucas’ theorem.

Received February 12 2016; revised versions received April 15 2016; May 15 2016. Published in Journal of Integer Sequences, June 2 2016. Minor revision, November 13 2016.

This is the corrected version of the paper, published September 25 2019.

Return to Journal of Integer Sequences home page.