Digit Sums Generalizing Binomial Coefficients

Ji Young Choi Department of Mathematics Shippensburg University of Pennsylvania 1871 Old Main Drive Shippensburg, PA 17257 USA

                    jychoi@ship.edu

Abstract

We define four different generalizations of binomial coefficients, using the digit sum of a string with digits in {0, 1, 2, …, g}, for positive integers g. We identify one generalization with the extended binomial coefficients, and we express every other generalization in terms of the extended binomial coefficients. We also express every generalization in terms of the binomial coefficients and find the explicit formula for each generalization.

1 Introduction

For nonnegative integers n and k, the (n, k)-th binomial coefficient, denoted by \binom{n}{k}, is the coefficient of x^{k} in the expansion of (x + 1)^{n}, i.e.,

(x + 1)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k},

and it satisfies the following recurrence relation:

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

Using the recurrence relation, we construct Pascal’s triangle (\underline{A007318}) as follows:

\binom{n}{k} k = 0 1 2 3 4 5
n = 0  1
1  1 1
2  1 2 1
3  1 3 3 1
4  1 4 6 4 1
5  1 5 10 10 5 1

To generalize the binomial coefficients, we let b be an integer greater than 1 and g = b−1 throughout this paper. Then we can express the extended binomial coefficients or polynomial coefficients as follows.

Definition 1. [5] For nonnegative integers n and integers k, the (n, k)-th b-nomial coefficient (or b-nomial number of type 1) is denoted by \binom{n}{k}_{b} and satisfies

(x^{g} + x^{g−1} + ⋯ + x + 1)^{n} = ∑_{k} \binom{n}{k}_{b}x^{k}.  (2)

Then the b-nomial coefficients satisfy the following recurrence relation [3]:

\binom{n}{k}_{b} = ∑_{i=0}^{g} \binom{n − 1}{k − i}_{b}.  (3)

Using this recurrence relation, we construct a triangle and call it the b-nomial triangle. Then the 2-nomial triangle is Pascal’s triangle, and b-nomial triangles for b = 3 and 4 (\underline{A027907} and \underline{A008287}, respectively) are as follows [4]:

\begin{matrix}^{\binom{n}{k}}3 & k = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ n = 0 & 1 \\ 1 & 1 & 1 & 1 \\ 2 & 1 & 2 & 3 & 2 & 1 \\ 3 & 1 & 3 & 6 & 7 & 6 & 3 & 1 \\ 4 & 1 & 4 & 10 & 16 & 19 & 16 & 10 & 4 & 1 \\ 5 & 1 & 5 & 15 & 30 & 45 & 51 & 45 & 30 & 15 & 5 & 1 \end{matrix} ; \begin{matrix}^{\binom{n}{k}}4 & k = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ n = 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 2 & 3 & 4 & 3 & 2 & 1 \\ 3 & 1 & 3 & 6 & 10 & 12 & 12 & 10 & 6 & 3 & 1 \\ 4 & 1 & 4 & 10 & 20 & 31 & 40 & 44 & 40 & 31 & 20 & 10 & 4 & 1 \\ 5 & 1 & 5 & 15 & 35 & 65 & 101 & 135 & 155 & 155 & 135 & 101 & 65 & 35 & 15 & 5 & 1 \end{matrix}

Notice that Pascal’s triangle is a lower triangular matrix but the b-nomial triangle for b > 2 is not. In this paper, we find two new generalizations of binomial coefficients, whose corresponding matrix is a lower triangular matrix. Out of these two matrices, one is symmetric just like Pascal’s triangle, and the other is not.

To simplify the discussion below, we denote l_{b}(m) and s_{b}(m) as the length and the digit sum of the base-b representation of a nonnegative integer m, respectively. Since s_{b}(m) ≡ m (mod g) for all integers m [11], there exists an integer k satisfying

s_{b}(g · m) = g · k.

Hence, we can ask the following questions for positive integers n and k:

Question 1: How many nonnegative integers m satisfy l_{b}(m) ≤ n and s_{b}(m) = k?

Question 2: How many nonnegative integers m satisfy l_{b}(m) = n and s_{b}(m) = k?

Question 3: How many nonnegative integers m satisfy l_{b}(m) ≤ n and s_{b}(g · m) = g · k?

Question 4: How many nonnegative integers m satisfy l_{b}(m) = n and s_{b}(g · m) = g · k?

When b = 2, the answer to Questions 1 and 3 is the (n, k)-th binomial coefficient \binom{n}{k} and the answer to Questions 2 and 4 is the (n − 1, k − 1)-th binomial coefficient \binom{n−1}{k−1}. Hence, by answering all these questions for integers b ≥ 2 and modifying the indices n and k, we can find four different generalizations of the binomial coefficients. Two of the generalizations are completely new, and both construct a lower triangular matrix for all b.

In Section 2, we clarify notation for this paper. Section 3 answers Questions 1 and 2, and Section 4 answers Questions 3 and 4 by defining new generalizations of binomial coefficients. In Section 5, we express each generalization in terms of the extended binomial coefficients. In Section 6, we express each generalization in terms of the binomial coefficients, and find the explicit formulas. In Section 7, we discuss the symmetry in each generalization and the sequences closely related to the generalizations.

2 Notation

We let Σ_{b} be the set {0, 1, 2, …, g} and Σ_{b}^{∗} be the set of all finite strings consisting of digits in Σ_{b}. Every base-b representation of an integer is a finite string in Σ_{b}^{∗}, and the set Σ_{b}^{∗} also includes the empty string, which contains no digits, denoted by ϵ [9].

The notation for the number of digits in a string is as follows.

Notation 2. [9] For finite strings x and a digit a, let |x| denote the number of digits in x, and |x|_{a} denote the number of occurrences of digit a in x.

Lemma 3. For x ∈ Σ_{b}^{∗}, we have

|x| = ∑_{i=0}^{g} |x|_{i}.

For example, |01011| = 5, |01011|_{0} = 2, |01011|_{1} = 3, and 5 = 2 + 3. We consider |ϵ| = 0. The following operation shows how to create a new string from given ones [9].

Definition 4. For strings x and y and positive integers n, the concatenation of x and y, denoted by xy, is the string obtained by joining x and y end-to-end, and x^{n} denotes the concatenation of n copies of x. That is, if x = a_{1}a_{2} ⋯ a_{|x|} and y = b_{1}b_{2} ⋯ b_{|y|} for some a_{i}, b_{i} ∈ Σ_{b},

xy = a_{1}a_{2} ⋯ a_{|x|}b_{1}b_{2} ⋯ b_{|y|}, and x^{n} = xx ⋯ x (n times).

By convention, x^{0} is defined to be ϵ.

Lemma 5. For strings x and y and nonnegative integers n, we have |xy| = |x| + |y| and |x^{n}| = n|x|.

For example, 101 00 = 10100, (10)^{3} = 101010, and 1 = 1 (10)^{0}. Then |101 00| = |101| + |00| = 3 + 2 = 5, |(10)^{3}| = 3|10| = 3 · 2 = 6, and |ϵ| = |(10)^{0}| = 0.

Since the base-b representation of an integer is a string in {0, 1, 2, …, g}^{∗}, we call the base-b representation of an integer as a b-ary string throughout this paper. When we have to distinguish an integer and its b-ary string, we use the following notation.

Notation 6. For integers m with base-b representation x, we write m = [x]_{b} or (m)_{b} = x.

For example, 5 = [12]_{3} and (5)_{3} = 12. Then ([x]_{b})_{b} = x for all b-ary strings x and [(m)_{b}]_{b} = m for all integers m. Throughout this paper, we use the convention that m is an integer and x is its b-ary string.

Notation 7. For nonempty strings x with x = a_{n}a_{n−1} ⋯ a_{2}a_{1} for some digits a_{i}, and all nonnegative integers m, let s(x) and s_{b}(m) denote the digit sum of x and the digit sum of the b-ary string (m)_{b}, respectively, i.e.,

s(x) = ∑_{i=1}^{n} a_{i}  and  s_{b}(m) = s ((m)_{b}) .

By convention, we define s(ϵ) = 0.

For example, s(16) = 1 + 6 = 7 and s_{3}(16) = s(121) = 4.

Definition 8. [2] For strings x with x = a_{n}a_{n−1} ⋯ a_{1} for some digits a_{i}, the digit a_{i} is called indispensable in x if a_{i} = a_{i−1} = a_{i−2} = ⋯ = a_{i−k+1} > a_{i−k} for some positive integer k ≤ i + 1, considering a_{0} = 0, and dispensable, otherwise. We will follow this convention of dotting indispensable digits.

We let ι(x) denote the number of indispensable digits in x, and we let ι_{b}(m) = ι((m)_{b}) for nonnegative integers m. By convention, we define ι(ϵ) = 0.

For example, if x = ˙213345˙7˙7˙4, the digits 2, 7, 7, and 4 are indispensable in x and the digits 1, 3, 3, 4. and 5 are dispensable in x. Hence, ι(x) = 4. If m = 16, the ternary string (m)_{3} = 121 so ι_{3}(16) = ι(1˙2˙1) = 2.

To simplify arguments, we use the following notation as well.

Notation 9. For positive integers n, we let Σ_{b}^{n} and σ_{b}^{n} denote as follows:

Σ_{b}^{n} = {x ∈ Σ_{b}^{∗} : |x| = n} and σ_{b}^{n} = {x ∈ Σ_{b}^{n} : x ≠ 0y for strings y}.

By convention, we let Σ_{b}^{0} = σ_{b}^{0} = {ϵ}.

For example, Σ_{3}^{2} = {00, 01, 02, 10, 11, 12, 20, 21, 22} and σ_{3}^{2} = {10, 11, 12, 20, 21, 22}.

Notation 10. For a set X of strings, and nonnegative integers k, we have

X[k] = {x ∈ X : s(x) = k} and X⟨k⟩ = {x ∈ X : ι(x) = k}.

For example, Σ_{3}^{2}[2] = {02, 11, 20} and Σ_{3}^{2}⟨1⟩ = {0˙1, 0˙2, ˙10, 1˙2, ˙20}.

3 Addressing Questions 1 and 2

First, we find a combinatorial interpretations for the extended binomial coefficients as follows.

Theorem 11. For nonnegative integers n and integers k, the number of b-ary strings of length n with digit sum k is the (n, k)-th b-nomial coefficient \binom{n}{k}_{b}, i.e.,

\binom{n}{k}_{b} = |Σ_{b}^{n}[k]| = |\{x ∈ Σ_{b}^{n} : s(x) = k\}|.  (4)

Proof. Since the empty string ϵ is the only string of length 0 and s(ϵ) = 0,

|Σ_{b}^{0}[0]| = |{ϵ}| = 1 and |Σ_{b}^{0}[k]| = |ϕ| = 0 for nonzero k.

Since the string 0^{n} is the only string of length n with digit sum 0,

|Σ_{b}^{n}[0]| = |{0^{n}}| = 1 for nonzero n.

Hence, the sequence (|Σ_{b}^{n}[k]|)_{n,k≥0} has the same initial conditions as the b-nomial coefficients. We just need to show the sequences (|Σ_{b}^{n}[k]|)_{n,k≥0} has the same recurrence relation as (3). For all digits a ∈ {0, 1, 2, …, g}, we let

B_{a} = {x ∈ Σ_{b}^{n}[k] : x = ya for strings y}.

Then the set Σ_{b}^{n}[k] is partitioned by the B_{a}, i.e.,

Σ_{b}^{n}[k] = ⋃_{a=0}^{g} B_{a} and B_{a} ∩ B_{a′} = ϕ for a ≠ a′.  (5)

Consider a function f_{a} : B_{a} → Σ_{b}^{n−1}[k − a] with f_{a}(ya) = y for y ∈ Σ_{b}^{n−1}. Since s(ya) = k iff s(y) = k−a, and y_{1}a = y_{2}a iff y_{1} = y_{2}, the function f_{a} is bijective. Hence, |B_{a}| = |Σ_{b}^{n−1}[k−a]| so by (5),

|Σ_{b}^{n}[k]| = ∑_{a=0}^{g} |B_{a}| = ∑_{a=0}^{g} |Σ_{b}^{n−1}[k − a]|.

Therefore, the sequence (|Σ_{b}^{n}[k]|)_{n,k≥0} has the same recurrence relation as (3).

Hence, the (n, k)-th b-nomial coefficient is the answer to Question 1.

Lemma 12. For positive integers n and k,

\binom{n}{k}_{b} = |\{m ∈ ℕ : l_{b}(m) ≤ n and s_{b}(m) = k\}|.

Using the combinatorial interpretation, we can also generalize the hockey stick identity for the binomial coefficients[6]:

\binom{n}{k} = ∑_{i=1}^{n} \binom{n − i}{k − 1}.  (6)

Theorem 13. For positive integers n and k,

\binom{n}{k}_{b} = ∑_{j=1}^{g} ∑_{i=1}^{n} \binom{n − i}{k − j}_{b}.

Proof. For nonzero digits a ∈ Σ_{b} and nonnegative integers i < n, we let

B_{a0^{i}} = {x ∈ Σ_{b}^{n}[k] : x = ya0^{i} for strings y} = {ya0^{i} : y ∈ Σ_{b}^{n−i−1}[k − a]}.

Since k > 0, the string 0^{n} ∉ Σ_{b}^{n}[k]. Thus, the set Σ_{b}^{n}[k] is partitioned by the set B_{a0^{i}}. That is,

Σ_{b}^{n}[k] = ⋃_{a=1}^{g} ⋃_{i=0}^{n−1} B_{a0^{i}}, and B_{a0^{i}} ∩ B_{a′0^{i′}} = ϕ for a ≠ a′ or i ≠ i′.

Hence,

\binom{n}{k}_{b} = |Σ_{b}^{n}[k]| = ∑_{a=1}^{g} ∑_{i=0}^{n−1} |B_{a0^{i}}|.

Since |\{ya0^{i} : y ∈ Σ_{b}^{n−i−1}[k−a]\}| = |Σ_{b}^{n−i−1}[k−a]|, the size |B_{a0^{i}}| = |Σ_{b}^{n−i−1}[k−a]| = \binom{n−i−1}{k−a}_{b}. By adjusting indices i and a, we have the relation.

Now we consider strings with a nonzero leading digit. For positive integers n and integers k, we consider

|σ_{b}^{n}[k]| = |{x ∈ σ_{b}^{n} : s(x) = k}|.

Since σ_{b}^{0} = {ϵ} and s(ϵ) = 0, we have |σ_{b}^{o}[k]| = 1 if k = 0 and |σ_{b}^{o}[k]| = 0 otherwise. Then it is obvious that the size |σ_{b}^{n}[k]| is the answer to Question 2.

Lemma 14. For positive integers n and k,

|σ_{b}^{n}[k]| = |{m ∈ ℕ : l_{b}(m) = n and s_{b}(m) = k}|.

When b = 2, since digit 1 is the only nonzero digit, the leading digit for every string in σ_{2}^{n} is 1, and the digit sum is the same as the number of 1 digits. Thus,

\begin{aligned}|σ_{2}^{n}[k]| = |\{1x ∈ σ_{2}^{n} : s(1x) = k\}| & = |\{x ∈ Σ_{2}^{n−1} : s(x) = k − 1\}| \\ & = |\{x ∈ Σ_{2}^{n−1} : |x|_{1} = k − 1\}| = \binom{n − 1}{k − 1}. \end{aligned}

When b > 2, we sort the strings in σ_{b}^{n} according to digit sums to calculate the number |σ_{b}^{n}[k]|. For example, since σ_{3}^{2} = {10} ∪ {11, 20} ∪ {12, 21} ∪ {22},

\begin{matrix}|σ_{3}^{2}[1]| = |\{10\}| = 1; & |σ_{3}^{2}[2]| = |\{11, 20\}| = 2; \\ |σ_{3}^{2}[3]| = |\{12, 21\}| = 2; & |σ_{3}^{2}[4]| = |\{22\}| = 1. \end{matrix}

Then the first few numbers for |σ_{b}^{n}[k]| when b = 2, 3, and 4 are as follows:

|σ_{2}^{n}[k]| k = 0 1 2 3 4 5 6
n = 0  1
1  1
2  1 1
3  1 2 1
4  1 3 3 1
5  1 4 6 4 1
|σ_{3}^{n}[k]| k = 0 1 2 3 4 5 6 7 8 9 10
n = 0  1
1  1 1
2  1 2 2 1
3  1 3 5 5 3 1
4  1 4 9 13 13 9 4 1
5  1 5 14 26 35 35 26 14 5 1
|σ_{4}^{n}[k]| k = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
n = 0  1
1  1 1 1
2  1 2 3 3 2 1
3  1 3 6 9 10 9 6 3 1
4  1 4 10 19 28 34 34 28 19 10 4 1
5  1 5 15 34 61 91 115 124 115 91 61 34 15 5 1

The sequences (|σ_{b}^{n}[k]|)_{n,k≥0} for b = 3 and 10 are identified with \underline{A005773} and \underline{A071976}, respectively, but in general, the numbers are not studied much. In this paper, we adjust the indices n and k to study the numbers as a new generalization of the binomial coefficients as follows.

Definition 15. For nonnegative integers n and integers k, the (n, k)-th b-nomial number of type 2, denoted by \binom{n}{k}_{b2}, is defined as

\binom{n}{k}_{b2} = |σ_{b}^{n+1}[k + 1]| = |\{x ∈ σ_{b}^{n+1} : s(x) = k + 1\}|.

By convention, we define \binom{−1}{k} = 1 if k = −1 and \binom{−1}{k} = 0 otherwise.

Then the number \binom{n}{k}_{22} = \binom{n}{k}, and the first few numbers for \binom{n}{k}_{b2} for nonnegative integers n and k when b = 3 and 4 are as follows:

\begin{matrix}^{\binom{n}{k}}32 & k = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ n = 0 & 1 & 1 \\ 1 & 1 & 2 & 2 & 1 \\ 2 & 1 & 3 & 5 & 5 & 3 & 1 \\ 3 & 1 & 4 & 9 & 13 & 13 & 9 & 4 & 1 \\ 4 & 1 & 5 & 14 & 26 & 35 & 35 & 26 & 14 & 5 & 1 \\ 5 & 1 & 6 & 20 & 45 & 75 & 96 & 96 & 75 & 45 & 20 & 6 & 1 \end{matrix} ; \begin{matrix}^{\binom{n}{k}}42 & k = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ n = 0 & 1 & 1 & 1 \\ 1 & 1 & 2 & 3 & 3 & 2 & 1 \\ 2 & 1 & 3 & 6 & 9 & 10 & 9 & 6 & 3 & 1 \\ 3 & 1 & 4 & 10 & 19 & 28 & 34 & 34 & 28 & 19 & 10 & 4 & 1 \\ 4 & 1 & 5 & 15 & 34 & 61 & 91 & 115 & 124 & 115 & 91 & 61 & 34 & 15 & 5 & 1 \\ 5 & 1 & 6 & 21 & 55 & 115 & 201 & 301 & 391 & 445 & 445 & 391 & 301 & 201 & 115 & 55 & 21 \end{matrix}

By the definitions, we find the following basic properties for the b-nomial numbers of type 1 and 2.

Lemma 16. For nonnegative integers n and k:

(i) \binom{n}{k}_{b} = ∑_{i=0}^{n} \binom{i−1}{k−1}_{b2};

(ii) \binom{n}{k}_{b2} = \binom{n+1}{k+1}_{b} − \binom{n}{k+1}_{b};

(iii) \binom{n}{k}_{b2} ≠ 0 iff 0 ≤ k < g(n + 1);

(iv) ∑_{k≥0} \binom{n}{k}_{b} = b^{n} and ∑_{k≥0} \binom{n}{k}_{b2} = g · b^{n};

(v) \binom{n}{k}_{b} = \binom{n−1}{k}_{b2} if k = 0, 1, 2, …, g − 1;

(vi) \binom{0}{k}_{b2} = 1 if k = 0, 1, 2, …, g − 1 and \binom{0}{k}_{b2} = 0 otherwise.

Proof. Since σ_{b}^{0} = {ϵ}, the set Σ_{b}^{n}[k] can be partitioned as follows:

Σ_{b}^{n}[k] = ⋃_{i=0}^{n}{0^{n−i}x : x ∈ σ_{b}^{i}[k]}.

Since \binom{i−1}{k−1}_{b2} = |σ_{b}^{i}[k]| = |\{0^{n−i}x : x ∈ σ_{b}^{i}[k]\}|, we have (i) by Theorem 11 and Definition 15. Then (i) provides (ii). For strings x in σ_{b}^{n+1}, 1 ≤ s(x) ≤ g(n + 1), so we have (iii). Since Σ_{b}^{n} = ⋃_{k≥0} Σ_{b}^{n}[k] and σ_{b}^{n} = ⋃_{k≥0} σ_{b}^{n}[k], we have (iv). For (v), we consider f : Σ_{b}^{n}[k] → σ_{b}^{n}[k + 1] by f(a_{1}a_{2} … a_{n}) = (a_{1} + 1)a_{2} … a_{n} for digits a_{i} in Σ_{b}. Since k ≤ g − 1, the digit a_{1} ≤ g − 1 so a_{1} + 1 is a nonzero leading digit. Then f is a well-defined one-to-one mapping, so |Σ_{b}^{n}[k]| = |σ_{b}^{n}[k + 1]|. Hence, (v) holds. Since σ_{b}^{1} = {1, 2, …, g} and s(a) = a for a = 1, 2, …, g, (vi) holds.

Even if the b-nomial numbers of type 1 and 2 have different initial conditions, they have the same recurrence relations. We can also find a generalization of the hockey stick identity for the b-nomial numbers of type 2.

Corollary 17. For positive integers n and integers k,

\binom{n}{k}_{b2} = ∑_{i=0}^{g} \binom{n − 1}{k − i}_{b2} = ∑_{j=1}^{g} ∑_{i=1}^{n+1} \binom{n − i}{k − j}_{b2}.

Proof. By Lemma 16 (ii) and the recurrence relation (3), we have the first recurrence relation for the b-nomial numbers of type 2:

\begin{aligned}\binom{n}{k}_{b2} = \binom{n + 1}{k + 1}_{b} − \binom{n}{k + 1}_{b} & = ∑_{i=0}^{g} \binom{n}{k + 1 − i}_{b} − ∑_{i=0}^{g} \binom{n − 1}{k + 1 − i}_{b} \\ & = ∑_{i=0}^{g} (\binom{n}{k + 1 − i}_{b} − \binom{n − 1}{k + 1 − i}_{b}) = ∑_{i=0}^{g} \binom{n − 1}{k − i}_{b2}. \end{aligned}

By Lemma 16 (ii) and Theorem 13, we have the second relation for the b-nomial numbers of type 2.

\binom{n}{k}_{b2} = \binom{n + 1}{k + 1}_{b} − \binom{n}{k + 1}_{b}

= ∑_{j=1}^{g} ∑_{i=1}^{n+1} \binom{n + 1 − i}{k + 1 − j}_{b} − ∑_{j=1}^{g} ∑_{i=1}^{n} \binom{n − i}{k + 1 − j}_{b}

= ∑_{i=1}^{g} \binom{0}{k + 1 − j}_{b} + ∑_{j=1}^{g} ∑_{i=1}^{n} (\binom{n + 1 − i}{k + 1 − j}_{b} − \binom{n − i}{k + 1 − j}_{b})

= ∑_{i=1}^{g} \binom{−1}{k − j}_{b2} + ∑_{j=1}^{g} ∑_{i=1}^{n} \binom{n − i}{k − j}_{b2} = ∑_{j=1}^{g} ∑_{i=1}^{n+1} \binom{n − i}{k − j}_{b2},

since

\binom{0}{k}_{b} = \begin{cases}1, & if k = 0; \\ 0, & otherwise, \end{cases} and \binom{−1}{k}_{b2} = \begin{cases}1, & if k = −1; \\ 0, & otherwise. \end{cases}

4 Addressing Questions 3 and 4

First, we define a new sequence to answer Question 3.

Definition 18. For positive integers n and integers k, the (n, k)-th b-nomial number of type 3, denoted by \binom{n}{k}_{b3}, is the number of b-ary strings of length n with k indispensable digits, i.e.,

\binom{n}{k}_{b3} = |Σ_{b}^{n}⟨k⟩| = |\{x ∈ Σ_{b}^{n} : ι(x) = k\}|.

By convention, we define \binom{0}{k}_{b3} = 1 if k = 0 and \binom{0}{k}_{b3} = 0 otherwise.

When b = 2, digit 1 is the only nonzero digit, so every digit 1 in a binary string is indispensable. Thus,

|Σ_{2}^{n}⟨k⟩| = |\{x ∈ Σ_{2}^{n} : |x|_{1} = k\}| = \binom{n}{k}.

Hence, the number \binom{n}{k}_{23} = \binom{n}{k}. When b > 2, we can sort the strings in Σ_{b}^{n} to calculate \binom{n}{k}_{b3}. For example, since

Σ_{3}^{2} = {00} ⋃{0˙1, 0˙2, ˙10, 1˙2, ˙20} ⋃{˙1˙1, ˙2˙1, ˙2˙2},

we have \binom{2}{k}_{33} = 0 for k ≠ 0, 1, 2, and

\binom{2}{0}_{33} = |\{00\}| = 1; \binom{2}{1}_{33} = |\{0˙1, 0˙2, ˙10, ˙20, 1˙2\}| = 5; \binom{2}{2}_{33} = |\{˙1˙1, ˙2˙1, ˙2˙2\}| = 3.

Then the first few numbers for \binom{n}{k}_{b3} when b = 3 and 4 are as follows:

\begin{matrix}\binom{n}{k}33 & k = 0 & 1 & 2 & 3 & 4 & 5 \\ n = 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 2 & 0 & 0 & 0 & 0 \\ 2 & 1 & 5 & 3 & 0 & 0 & 0 \\ 3 & 1 & 9 & 13 & 4 & 0 & 0 \\ 4 & 1 & 14 & 35 & 26 & 5 & 0 \\ 5 & 1 & 20 & 75 & 96 & 45 & 6 \end{matrix}  \begin{matrix}\binom{n}{k}43 & k = 0 & 1 & 2 & 3 & 4 & 5 \\ n = 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 3 & 0 & 0 & 0 & 0 \\ 2 & 1 & 9 & 6 & 0 & 0 & 0 \\ 3 & 1 & 19 & 34 & 10 & 0 & 0 \\ 4 & 1 & 34 & 115 & 91 & 15 & 0 \\ 5 & 1 & 55 & 301 & 445 & 201 & 21 \end{matrix}

Since s_{b}(g · m) = g · ι_{b}(m) [2], the number \binom{n}{k}_{b3} is the answer to Question 3.

Lemma 19. For positive integers n and k,

\binom{n}{k}_{b3} = |\{m ∈ ℕ : l_{b}(m) ≤ n and s_{b}(g · m) = g · k\}|.

Now, we consider strings with a nonzero leading digit to answer Question 4. For positive integers n and integers k, we consider the number of strings in the set σ_{b}^{n} with k indispensable digits, i.e.,

|σ_{b}^{n}⟨k⟩| = |{x ∈ σ_{b}^{n} : ι(x) = k}|.

Since σ_{b}^{0} = {ϵ} and ι(ϵ) = 0, we have

|σ_{b}^{0}⟨k⟩| = \begin{cases}1, & if k = 0; \\ 0, & otherwise. \end{cases}

Since s_{b}(g · m) = g · ι_{b}(m) [2], the number |σ_{b}^{n}⟨k⟩| is the answer to Question 3.

Lemma 20. For positive integers n and k, we have

|σ_{b}^{n}⟨k⟩| = |{m ∈ ℕ : l_{b}(m) = n and s_{b}(g · m) = g · k}|.

When b = 2, since digit 1 is the only nonzero digit, the leading digit for every string in σ_{2}^{n} is 1 and every digit 1 is indispensable. Thus, for positive integers n and k, we have

|σ_{2}^{n}⟨k⟩| = |\{1x ∈ σ_{2}^{n} : ι(1x) = k\}| = |\{x ∈ Σ_{2}^{n−1} : ι(x) = k − 1\} = \binom{n − 1}{k − 1}.

When b > 2, we can sort the strings in σ_{b}^{n} to calculate the number |σ_{b}^{n}⟨k⟩|. For example, since

σ_{3}^{2} = {˙10, ˙20, 1˙2} ⋃{˙1˙1, ˙2˙1, ˙2˙2},

we have |σ_{3}^{2}⟨k⟩| = 0 for k ≠ 1, 2, and

|σ_{3}^{2}⟨1⟩| = |{˙10, ˙20, 1˙2}| = 3; |σ_{3}^{2}⟨2⟩| = |{˙1˙1, ˙2˙1, ˙2˙2}| = 3.

Hence, the first few numbers for |σ_{b}^{n}⟨k⟩| when b = 2 and 3 are as follows:

\begin{matrix}|σ_{2}^{n}⟨k⟩| & k = 0 & 1 & 2 & 3 & 4 & 5 \\ n = 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 1 & 0 & 0 & 0 \\ 3 & 0 & 1 & 2 & 1 & 0 & 0 \\ 4 & 0 & 1 & 3 & 3 & 1 & 0 \\ 5 & 0 & 1 & 4 & 6 & 4 & 1 \end{matrix}  \begin{matrix}|σ_{3}^{n}⟨k⟩| & k = 0 & 1 & 2 & 3 & 4 & 5 \\ n = 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 2 & 0 & 0 & 0 & 0 \\ 2 & 0 & 3 & 3 & 0 & 0 & 0 \\ 3 & 0 & 4 & 10 & 4 & 0 & 0 \\ 4 & 0 & 5 & 22 & 22 & 5 & 0 \\ 5 & 0 & 6 & 40 & 70 & 40 & 6 \end{matrix}

Since |σ_{b}^{n+1}⟨k + 1⟩| = \binom{n}{k} for nonnegative integers n and k, we modify the indices n and k to find another generalization of the binomial coefficients.

Definition 21. For nonnegative integers n and integers k, the (n, k)-th b-nomial number of type 4, denoted by \binom{n}{k}_{b4}, satisfies

\binom{n}{k}_{b4} = |σ_{b}^{n+1}⟨k + 1⟩| = |\{x ∈ σ_{b}^{n+1} : ι(x) = k + 1\}|.

By convention, we define \binom{−1}{k}_{4b} = 1 if k = −1 and \binom{−1}{k}_{4b} = 0 otherwise.

Obviously, the number \binom{n}{k}_{24} = \binom{n}{k}, and the first few b-nomial numbers of type 4 for nonnegative integers n and k when b = 3 and 4 are as follows:

\begin{matrix}\binom{n}{k}34 & k = 0 & 1 & 2 & 3 & 4 & 5 \\ n = 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 3 & 0 & 0 & 0 & 0 \\ 2 & 4 & 10 & 4 & 0 & 0 & 0 \\ 3 & 5 & 22 & 22 & 5 & 0 & 0 \\ 4 & 6 & 40 & 70 & 40 & 6 & 0 \\ 5 & 7 & 65 & 171 & 171 & 65 & 7 \end{matrix}  \begin{matrix}\binom{n}{k}44 & k = 0 & 1 & 2 & 3 & 4 & 5 \\ n = 0 & 3 & 0 & 0 & 0 & 0 & 0 \\ 1 & 6 & 6 & 0 & 0 & 0 & 0 \\ 2 & 10 & 28 & 10 & 0 & 0 & 0 \\ 3 & 15 & 81 & 81 & 15 & 0 & 0 \\ 4 & 21 & 186 & 354 & 186 & 21 & 0 \\ 5 & 28 & 371 & 1137 & 1137 & 371 & 28 \end{matrix}

By the definitions, we find the following basic properties for the b-nomial numbers of type 3 and type 4.

Lemma 22. For nonnegative integers n and k:

(i) \binom{n}{k}_{b3} = ∑_{i=0}^{n} \binom{i−1}{k−1}_{b4};

(ii) \binom{n}{k}_{b4} = \binom{n+1}{k+1}_{b3} − \binom{n}{k+1}_{b3};

(iii) \binom{n}{k}_{b3} = 0 = \binom{n}{k}_{b4} if k > n;

(iv) ∑_{k≥0} \binom{n}{k}_{b3} = b^{n} and ∑_{k≥0} \binom{n}{k}_{b4} = g · b^{n};

(v) \binom{n}{n}_{b3} = \binom{n−1}{n−1}_{b4};

(vi) \binom{1}{1}_{b3} = g = \binom{0}{0}_{b4}.

Proof. Equations (i) and (ii) are obtained by Definitions 18 and 21. (iii) holds, because there cannot be more indispensable digits than the total number of digits. (iv) holds, because the sum of \binom{n}{k}_{b3} for fixed n is the total number of b-ary strings of length n, and the sum of \binom{n}{k}_{b4} for fixed n is the total number of b-ary strings of length n + 1 with a nonzero leading digit.

(v) holds, because \binom{n−1}{n−1}_{b4} = \binom{n}{n}_{b3} − \binom{n−1}{n}_{b3} = \binom{n}{n}_{b3} by (ii) and \binom{n−1}{n}_{b3} = 0 by (iii). (vi) is obtained by |Σ_{b}^{1}⟨1⟩| = |{1, 2, …, g}| = |σ_{b}^{1}⟨1⟩|.

5 In terms of extended binomial coefficients

Section 3 shows that the b-nomial numbers of type 2 are expressed in terms of the extended binomial coefficients. In this section, we express the b-nomial numbers of type 3 and type 4 in terms of the extended binomial coefficients as well.

First, we define the following sequence to help the further calculations.

Definition 23. For digits a ∈ {0, 1, 2, …, g − 1}, a positive integer n, and an integer k, we let Z_{ba}^{n} denote the set of b-ary strings of length n+1 with a dispensable leading digit a. That is,

Z_{ba}^{n} = \begin{cases}\{x ∈ Σ_{b}^{n+1} : [0^{n+1}]_{b} ≤ [x]_{b} ≤ [0g^{n}]_{b}\}, & if a = 0; \\ \{x ∈ Σ_{b}^{n+1} : [a^{n}(a + 1)]_{b} ≤ [x]_{b} ≤ [ag^{n}]_{b}\}, & if a = 1, 2, …, g − 1. \end{cases}

We let C_{ba}(n, k) denote the number of strings in Z_{ba}^{n} with k indispensable digits, i.e.,

C_{ba}(n, k) = |Z_{ba}^{n}⟨k⟩|.

For example, since

Z_{41}^{2} = {11˙2, 11˙3, 1˙20, 12˙3, 1˙30} ∪ {1˙2˙1, 1˙2˙2, 1˙3˙1, 1˙3˙2, 1˙3˙3}; Z_{42}^{2} = {22˙3, 2˙30} ∪ {2˙3˙1, 2˙3˙2, 2˙3˙3},

we have

C_{41}(2, 1) = 5 = C_{41}(2, 2); C_{42}(2, 1) = 2; C_{42}(2, 2) = 3.

The following shows the first few numbers for C_{41}(n, k) and C_{42}(n, k):

\begin{matrix}C_{41}(n, k) & 1 & 2 & 3 & 4 & 5 \\ n = 1 & 2 & 0 & 0 & 0 & 0 \\ 2 & 5 & 5 & 0 & 0 & 0 \\ 3 & 9 & 24 & 9 & 0 & 0 \\ 4 & 14 & 71 & 71 & 14 & 0 \\ 5 & 20 & 166 & 310 & 166 & 20 \end{matrix}  \begin{matrix}C_{42}(n, k) & 1 & 2 & 3 & 4 & 5 \\ n = 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 3 & 0 & 0 & 0 \\ 3 & 3 & 12 & 6 & 0 & 0 \\ 4 & 4 & 31 & 40 & 10 & 0 \\ 5 & 5 & 65 & 155 & 101 & 15 \end{matrix}

Since Z_{b0}^{n} = {0x : x ∈ Σ_{b}^{n}} and digit 0 is always dispensable,

|Z_{b0}^{n}⟨k⟩| = |{0x : x ∈ Σ_{b}^{n} and ι(0x) = k}| = |{x ∈ Σ_{b}^{n} : ι(x) = k}| = |Σ_{b}^{n}⟨k⟩|.

Hence, we identify the number C_{b0}(n, k) with the (n, k)-th b-nomial number of type 3.

Lemma 24. For positive n and k, we have

C_{b0}(n, k) = \binom{n}{k}_{b3}.

To calculate C_{ba}(n, k) for digits a ∈ {0, 1, 2, …, g − 1}, we define a set Y_{a} as follows:

Y_{a} = \begin{cases}\{x ∈ Σ_{b}^{m} : [0^{n}]_{b} ≤ [x]_{b} ≤ [1^{n}]_{b}\}, & if a = 0; \\ \{x ∈ Σ_{b}^{n} : [a^{n−1}(a + 1)]_{b} ≤ [x]_{b} ≤ [(a + 1)^{n}]_{b}\} , & if a = 1, 2, …, g − 1. \end{cases}  (7)

Then the set Σ_{b}^{n} is partitioned by the Y_{a}, i.e.,

Σ_{b}^{n} = ⋃_{a=0}^{g−1} Y_{a} and Y_{a} ∩ Y_{a′} = ϕ.  (8)

We identify the size |Y_{a}⟨k⟩| as the (n, gk − a)-th b-nomial coefficient as follows. Lemma 25. For digits a ∈ {0, 1, 2, …, g − 1} and positive integers n and k, we have

|Y_{a}⟨k⟩| = \binom{n}{gk − a}_{b}.

Proof. We define a function

f : Y_{a}⟨k⟩ → Σ_{b}^{n}[gk − a] with f(x) = (g · [x]_{b} − [a0^{n}]_{b})_{b} ,

for all x ∈ Y_{a}⟨k⟩. If a = 1, 2, …, g − 1, we have

g · a = [a − 1, b − a]_{b} and g · (a + 1) = [a, g − a]_{b}.  (9)

Hence, we can calculate the bounds of the products of g by the numbers represented by the strings in Y_{a} as follows:

\begin{matrix}if x ∈ Y_{0}, & [00^{n}]_{b} = [0^{n}]_{b} ≤ g · [x]_{b} ≤ [g^{n}]_{b} = [0g^{n}]_{b}; \\ if x ∈ Y_{a}(a ≠ 0), & [a0^{n−1}(g − a)]_{b} ≤ g · [x]_{b} ≤ [ag^{n−1}(g − a)]_{b}. \end{matrix}

Thus, there exists y ∈ Σ_{b}^{n} such that g · [x]_{b} = [ay]_{b} for every a = 0, 1, 2, …, g − 1, so

g · [x]_{b} − [a0^{n}]_{b} = [0y]_{b} = [y]_{b} for some string y ∈ Σ_{b}^{n}.

Since ι(x) = k, s_{b}(g · [x]_{b}) = g · ι(x) = g · k, so

s_{b}(g · [x]_{b} − [a0^{n}]_{b}) = s_{b}([y]_{b}) = s_{b}([ay]_{b}) − a = s_{b}(g · [x]_{b}) − a = g · k − a.

Thus, f is well-defined. We just need to show f is bijective so that

|Y_{a}⟨k⟩| = |Σ_{b}^{n}[gk − a]| = \binom{n}{gk − a}_{b}.

It is obvious that f is injective, since if f(x_{1}) = f(x_{2}), g · [x_{1}]_{b} = g · [x_{2}]_{b} so x_{1} = x_{2}. To prove f is surjective, we consider a string y ∈ Σ_{b}^{n}[gk − a]. Then s(y) = g · k − a so s(ay) = s(y) + a = g · k. Thus, the number [ay]_{b} is divisible by g, so

g · ι_{b} (\frac{[ay]_{b}}{g} ) = s_{b} (g · \frac{[ay]_{b}}{g} ) = s_{b}([ay]_{b}) = g · k, so ι_{b} (\frac{[ay]_{b}}{g} ) = k.

Since [0^{n}]_{b} ≤ [y]_{b} ≤ [g^{n}]_{b},

[a0^{n}]_{b} ≤ [ay]_{b} ≤ [ag^{n}]_{b}.  (10)

If a ≠ 0, the number [a0^{n−1}(g −1)]_{b} is the least multiple of g, and the number [ag^{n−1}(g −a)]_{b} is the greatest multiple of g in the interval (10). Since the number [ay]_{b} is a multiple of g,

\begin{matrix}if a = 0, & [0^{n}]_{b} = [00^{n}]_{b} ≤ [ay]_{b} ≤ [0g^{n}]_{b} = [g^{n}]_{b}; \\ if a ≠ 0, & [a0^{n−1}(g − a)]_{b} ≤ [ay]_{b} ≤ [ag^{n−1}(g − a)]_{b}. \end{matrix}

Hence, by (9), we have

\begin{matrix}if a = 0, & [0^{n}]_{b} ≤ \frac{[ay]_{b}}{g} ≤ [1^{n}]_{b}; \\ if a ≠ 0, & [a^{n−1}(a + 1)] ≤ \frac{[ay]_{b}}{g} ≤ [(a + 1)^{n}]_{b}. \end{matrix}

Therefore, (\frac{[ay]_{b}}{g} )_{b} ∈ Y_{a}⟨k⟩ and

f ((\frac{[ay]_{b}}{g} )_{b}) = (g · \frac{[ay]_{b}}{g} − [a0^{n}]_{b})_{b} = ([0y]_{b})_{b} = y.

Now we express C_{ba}(n, k) in terms of extended binomial coefficients.

Lemma 26. For digits a ∈ {0, 1, 2, …, g − 1} and positive integers n and k,

C_{ba}(n, k) = ∑_{i=a}^{g−1} \binom{n}{gk − i}_{b}.  (11)

Proof. We define

f : Z_{ba}^{n}⟨k⟩ → ⋃_{i=a}^{g−1} Y_{i}⟨k⟩ with f(ax) = x.

Since the leading digit a is always dispensable, ι(ax) = ι(x). Hence, f is a well-defined one-to-one mapping, so |Z_{ba}^{n}⟨k⟩| = | ∪_{i=a}^{g−1} Y_{i}⟨k⟩|. By (8),

|Z_{ba}^{n}⟨k⟩| = ∑_{i=a}^{g−1} |Y_{i}⟨k⟩|.

By Definition 23 and Lemma 25, we obtain (11).

Therefore, we can express the b-nomial numbers of type 3 and 4 in terms of the b-nomial numbers of type 1 and 2, respectively, as follows.

Theorem 27. For positive integers n and k we have

\begin{matrix}(i) \binom{n}{k}_{b3} = ∑_{i=0}^{g−1} \binom{n}{gk − i}_{b} = \binom{n + 1}{gk + 1}_{b} − \binom{n}{gk + 1}_{b} = \binom{n + 1}{gk}_{b} − \binom{n}{gk − g}_{b}; \\ (ii) \binom{n}{k}_{b4} = ∑_{i=1}^{g} \binom{n}{gk + i}_{b2} = \binom{n + 1}{gk + g}_{b2} − \binom{n}{gk + g}_{b2} = \binom{n + 1}{gk + g − 1}_{b2} − \binom{n}{gk − 1}_{b2}. \end{matrix}

Proof. By Lemma 24 and 26, we have the first expression for \binom{n}{k}_{b3} in (i). By (3), we have the last two expressions in (i).

Since \binom{n}{k}_{b4} = \binom{n+1}{k+1}_{b3} − \binom{n}{k+1}_{b3} and \binom{n}{k}_{b2} = \binom{n+1}{k+1}_{b} − \binom{n}{k+1}_{b} by Lemma 22 (ii) and Lemma 16 (ii), we apply the first expression for \binom{n}{k}_{b3} in (i) to have

\begin{aligned}\binom{n + 1}{k + 1}_{b3} − \binom{n}{k + 1}_{b3} & = ∑_{i=0}^{g−1} \binom{n + 1}{g(k + 1) − i}_{b} − ∑_{i=0}^{g−1} \binom{n}{g(k + 1) − i}_{b} \\ & = ∑_{i=1}^{g} \binom{n}{g(k + 1) − i}_{b2}, \end{aligned}  (12)

which provides the first expression for \binom{n}{k}_{b4} in (ii). Similarly, we apply the second expression for \binom{n}{k}_{b3} in (i). Since g(k + 1) + 1 = gk + b, we have

\begin{aligned}\binom{n + 1}{k + 1}_{b3} − \binom{n}{k + 1}_{b3} & = (\binom{n + 2}{gk + b}_{b} − \binom{n + 1}{gk + b}_{b}) − (\binom{n + 1}{gk + b}_{b} − \binom{n}{gk + b}_{b}) \\ & = \binom{n + 1}{gk + b − 1}_{b2} − \binom{n}{gk + b − 1}_{b2}, \end{aligned} (13)

which provides the second expression for \binom{n}{k}_{b4} in (ii). Similarly, we apply the last expression for \binom{n}{k}_{b3} in (i). Since g(k + 1) − g = gk, we have

\begin{aligned}\binom{n + 1}{k + 1}_{b3} − \binom{n}{k + 1}_{b3} & = (\binom{n + 2}{gk + g}_{b} − \binom{n + 1}{gk}_{b}) − (\binom{n + 1}{gk + g}_{b} − \binom{n}{gk}_{b}) \\ & = (\binom{n + 2}{gk + g}_{b} − \binom{n + 1}{gk + g}_{b}) − (\binom{n + 1}{gk}_{b} − \binom{n}{gk}_{b}) \\ & = \binom{n + 1}{gk + g − 1}_{b2} − \binom{n}{gk − 1}_{b2}, \end{aligned} (14)

which provides the last expression in (ii).

Applying Theorem 27 (i) to Lemma 22 (ii), we express the b-nomial numbers of type 4 in terms of the extended binomial coefficients as follows.

Corollary 28. For positive n and k we have

\binom{n}{k}_{b4} = \binom{n + 2}{gk + b}_{b} − 2\binom{n + 1}{gk + b}_{b} + \binom{n}{gk + b}_{b}

= \binom{n}{gk}_{b} + ∑_{i=1}^{g−1} \binom{n + 1}{gk + i}_{b}

= g · \binom{n}{gk}_{b} + ∑_{i=1}^{g−1}(g − i) · (\binom{n}{gk + i}_{b} + \binom{n}{gk − i}_{b}) .

Proof. Since \binom{n}{k}_{b4} = \binom{n+1}{k+1}_{b3} − \binom{n}{k+1}_{b3}, the first identity in (13) provides the first expression. By the first identity in (14), we have

\binom{n}{k}_{b4} = (\binom{n + 2}{gk + g}_{b} − \binom{n + 1}{gk}_{b} − \binom{n + 1}{gk + g}_{b}) + \binom{n}{gk}_{b}.

Since \binom{n+2}{gk+g}_{b} = ∑_{i=0}^{g} \binom{n+1}{gk+i}_{b} by (3), we have the second expression. By the first identity in (12) and (3), we have

\binom{n}{k}_{b4} = ∑_{i=1}^{g} (\binom{n + 1}{gk + i}_{b} − \binom{n}{gk + i}_{b}) = ∑_{i=1}^{g} ∑_{j=1}^{g} \binom{n}{gk + i − j}_{b}.

The number i − j for 1 ≤ i, j ≤ g is as follows:

i − j j = 1 2  3 ⋯ g − 2 g − 1 g
i = 1  0 −1 −2 ⋯ 3 − g 2 − g 1 − g
2  1 0  −1 ⋯ 4 − g 3 − g 2 − g
3  2 1  0 ⋯ 5 − g 4 − g 3 − g
⋮  ...
g − 2 g − 3 g − 4 g − 5 ⋯ 0  −1 −2
g − 1 g − 2 g − 3 g − 4 ⋯ 1  0  −1
g g − 1 g − 2 g − 3 ⋯ 2  1  0

Hence, we have

\binom{n}{k}_{b4} = g · \binom{n}{gk}_{b}

+ (g − 1) · \binom{n}{gk + 1}_{b} + (g − 2) · \binom{n}{gk + 2}_{b} + ⋯ + 1 · \binom{n}{gk + g − 1}_{b}

+ (g − 1) · \binom{n}{gk − 1}_{b} + (g − 2) · \binom{n}{gk − 2}_{b} + ⋯ + 1 · \binom{n}{gk − (g − 1)}_{b}.

Therefore, we have the last expression for \binom{n}{k}_{b4}.

6 Explicit formulas

Neuschel showed that the extended binomial coefficients can be expressed as a sum of Hermite polynomials and Bernoulli numbers [7]. In this section, we express the b-nomial numbers of each type, including extended binomial coefficients, in terms of the binomial coefficients.

Theorem 29. For nonnegative integers n and k we have

(i)  \binom{n}{k}_{b} = ∑_{i_{1}+i_{2}+···+i_{g}=k}  \binom{n}{i_{1}}\binom{i_{1}}{i_{2}}\binom{i_{2}}{i_{3}} ⋯ \binom{i_{g−1}}{i_{g}};

(ii)  \binom{n}{k}_{b2} = ∑_{i_{1}+i_{2}+···+i_{g}=k+1} \binom{n}{i_{1} − 1}\binom{i_{1}}{i_{2}}\binom{i_{2}}{i_{3}} ⋯ \binom{i_{g−1}}{i_{g}};

(iii) \binom{n}{k}_{b3} = ∑_{i_{1}+i_{2}+···+i_{g}=gk+1} \binom{n}{i_{1} − 1}\binom{i_{1}}{i_{2}}\binom{i_{2}}{i_{3}} ⋯ \binom{i_{g−1}}{i_{g}};

(iv) \binom{n}{k}_{b4} = ∑_{i_{1}+i_{2}+···+i_{g}=gk+b} \binom{n}{i_{1} − 2}\binom{i_{1}}{i_{2}}\binom{i_{2}}{i_{3}} ⋯ \binom{i_{g−1}}{i_{g}}.

Proof. (i) For strings x = a_{1}a_{2} ⋯ a_{n} with a digit a_{i} ∈ Σ_{b}, we can find the unique string x_{j} for each j = 0, 1, 2, …, g as follows:

x_{j} = a′_{1}a′_{2} ⋯ a′_{n}, where a′_{i} = \{ \begin{matrix}a_{i}, & if a_{i} < j; \\ j, & if a_{i} ≥ j. \end{matrix}

Hence, every string in Σ_{b}^{n}[k] can be uniquely constructed as follows: For positive integers i_{j} satisfying ∑_{j=1}^{g} i_{j} = k we have

• Let x_{0} = 0^{n};

• For j = 1, 2, …, g, construct string x_{j}, by choosing i_{j} digits (j − 1) in the string x_{j−1} and replacing each chosen digit j − 1 with digit j;

• Let x = x_{g}.

Then each string x_{j} ∈ {0, 1, 2, …, j}^{n} for all j = 0, 1, 2, …, g, so the string x ∈ Σ_{b}^{n}. Since there is no change in the occurrences of digit j after constructing the string x_{j+1},

|x|_{j} = |x_{j+1}|_{j} = i_{j} − i_{j+1} for all j = 1, 2, …, g − 1, and |x|_{g} = |x_{g}|_{g} = i_{g}.

Hence, the digit sum of the string x is

s(x) = ∑_{j=1}^{g} j · |x|_{j} = ∑_{j=1}^{g−1} j · (i_{j} − i_{j+1}) + g · i_{g} = ∑_{j=1}^{g} i_{j} = k.

Since the string x ∈ Σ_{b}^{n}, the string x ∈ Σ_{b}^{n}[k].

Since there are \binom{n}{i_{1}} ways to construct x_{1} from x_{0} and \binom{i_{j−1}}{i_{j}} ways to construct x_{j} from x_{j−1} for each j = 2, 3, …, g, there are \binom{n}{i_{1}}\binom{i_{1}}{i_{2}}\binom{i_{2}}{i_{3}} ⋯ \binom{i_{g−1}}{i_{g}} distinct strings in Σ_{b}^{n}[k]. Therefore, the right-hand side of the equation (i) counts the number of strings in Σ_{b}^{n}[k]. Since the size |Σ_{b}^{n}[k]| = \binom{n}{k}_{b}, the equation (i) holds.

(ii) To construct a string in σ_{b}^{n+1}[k + 1], we start with the string x_{0} = 10^{n} and we construct x_{1} by choosing i_{1} − 1 copies of the digit 0 in x_{0} and replacing each chosen digit 0 with the digit 1. Then the string x_{1} has i_{1} digits 1 because of the leading digit. After that, we have the same procedures to construct x_{j} for all j = 2, 3, …, g as (i). Since we want the digit sum to be k + 1, the sum ∑ i_{j} = k + 1. Therefore, we have the equation (ii).

(iii) By (i) and Theorem 27 (i), we have

\begin{aligned}\binom{n}{k}_{b3} & = \binom{n + 1}{gk + 1}_{b} − \binom{n}{gk + 1}_{b} \\ & = ∑ ; ∑ i_{j}=gk+1 \binom{n + 1}{i_{1}}\binom{i_{1}}{i_{2}} ⋯ \binom{i_{g−1}}{i_{g}} − ∑ ; ∑ i′_{j}=gk+1 \binom{n}{i′_{1}}\binom{i′_{1}}{i′_{2}} ⋯ \binom{i′_{g−1}}{i′_{g}}. \end{aligned}

We assume i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n + 1 and i′_{g} ≤ i′_{g−1} ≤ ⋯ ≤ i′_{2} ≤ i′_{1} ≤ n. However, since \binom{n}{n+1} = 0, we can let i′_{1} ≤ n + 1 so we set i_{j} = i′_{j}. Hence,

\binom{n}{k}_{b3} = ∑ \binom{n + 1}{i_{1}}\binom{i_{1}}{i_{2}} ⋯ \binom{i_{g−1}}{i_{g}} − ∑ \binom{n}{i_{1}}\binom{i_{1}}{i_{2}} ⋯ \binom{i_{g−1}}{i_{g}},

where ∑_{j=1}^{g} i_{j} = gk + 1. Since \binom{n+1}{i_{1}} − \binom{n}{i_{1}} = \binom{n}{i_{1}−1}, we have the equation (iii).

(iv) Similarly, by (ii) and Theorem 27 (ii), we have

\begin{aligned}\binom{n}{k}_{b4} & = \binom{n + 1}{gk + g}_{b2} − \binom{n}{gk + g}_{b2} \\ & = ∑ \binom{n + 1}{i_{1} − 1}\binom{i_{1}}{i_{2}} ⋯ \binom{i_{g−1}}{i_{g}} − ∑ \binom{n}{i_{1} − 1}\binom{i_{1}}{i_{2}} ⋯ \binom{i_{g−1}}{i_{g}} \end{aligned}

where ∑_{j=1}^{g} i_{j} = gk + g + 1 = gk + b. Since \binom{n+1}{i_{1}−1} − \binom{n}{i_{1}−1} = \binom{n}{i_{1}−2}, we have (iv).

Note that we can assume the indices i_{j} in Theorem 29 satisfy the following:

(i) i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n;
(ii) i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n + 1;
(iii) i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n + 1;
(iv) i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n + 2,

because otherwise, we have \binom{i_{1}}{i_{2}}\binom{i_{2}}{i_{3}} ⋯ \binom{i_{g−1}}{i_{g}} = 0, \binom{n}{i_{1}} = 0, \binom{n}{i_{1}−1} = 0, or \binom{n}{i_{1}−2} = 0.

Using the explicit formula for the binomial coefficients:

\binom{n}{k} = \frac{n!}{k!(n − k)!},

we find the following explicit formulas for the b-nomial numbers of each type.

Theorem 30. For nonnegative integers n and k we have

\begin{matrix}(i)  \binom{n}{k}_{b} = ∑_{i_{1}+i_{2}+···+i_{g}=k} & \frac{n!}{(n − i_{1})!(i_{1} − i_{2})!(i_{2} − i_{3})! ⋯ (i_{g−1} − i_{g})!i_{g}!}; \\ (ii)  \binom{n}{k}_{b2} = ∑_{i_{1}+i_{2}+···+i_{g}=k+1} & \frac{i_{1} · n!}{(1 + n − i_{1})!(i_{1} − i_{2})!(i_{2} − i_{3})! ⋯ (i_{g−1} − i_{g})!i_{g}!}; \\ (iii) \binom{n}{k}_{b3} = ∑_{i_{1}+i_{2}+···+i_{g}=gk+1} & \frac{i_{1} · n!}{(1 + n − i_{1})!(i_{1} − i_{2})!(i_{2} − i_{3})! ⋯ (i_{g−1} − i_{g})!i_{g}!}; \\ (iv) \binom{n}{k}_{b4} = ∑_{i_{1}+i_{2}+···+i_{g}=gk+b} & \frac{i_{1}(i_{1} − 1) · n!}{(2 + n − i_{1})!(i_{1} − i_{2})!(i_{2} − i_{3})! ⋯ (i_{g−1} − i_{g})!i_{g}!}, \end{matrix}

where the indices i_{j} satisfy

0 ≤ i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n  for (i);
0 ≤ i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n + 1 for (ii);
0 ≤ i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n + 1 for (iii);
0 ≤ i_{g} ≤ i_{g−1} ≤ ⋯ ≤ i_{2} ≤ i_{1} ≤ n + 2 for (iv).

7 Symmetry

In this section, we discuss symmetry of the sequences defined in Sections 3, 4, and 5. By the definitions, the binomial coefficients and extended binomial coefficients have symmetry: for nonnegative integers n,

\binom{n}{k} = \binom{n}{n − k} and \binom{n}{k}_{b} = \binom{n}{gn − k}_{b}.  (15)

The b-nomial numbers of type 2 and 4 and the sequence (C_{b1}(n, k))_{n,k>0} also have symmetry as follows.

Lemma 31. For nonnegative integers n and k we have

(i) \binom{n}{k}_{b2} = \binom{n}{g(n + 1) − (k + 1)}_{b2};

(ii) \binom{n}{k}_{b4} = \binom{n}{n − k}_{b4};

(iii) C_{b1}(n, k) = C_{b1}(n, n − k + 1).

Proof. (i) Let x be a string in σ_{b}^{n+1}[k + 1]. Then there exist digits a_{i} ∈ Σ_{b} satisfying x = a_{1}a_{2} ⋯ a_{n}a_{n+1} with a_{1} ≠ 0 and ∑ a_{i} = k + 1. Then we define a string x′ such that

x′ = a′_{1}a′_{2} ⋯ a′_{n}a′_{n+1}, where a′_{i} = \begin{cases}b − a_{i}, & if i = 1; \\ g − a_{i}, & otherwise. \end{cases}

Since a_{1} ≠ 0, the digit a′_{1} ∈ Σ_{b} so every digit a′_{i} ∈ Σ_{b} for all i. Since a_{1} ≠ b, the digit a_{1} ≠ 0. Since the sum ∑ a_{i} = k + 1,

s(x′) = gn + b − ∑ a_{i} = gn + g + 1 − (k + 1) = g(n + 1) − k.

Thus, the string x′ ∈ σ_{b}^{n+1}[g(n + 1) − k]. Hence, the function

f : σ_{b}^{n+1}[k + 1] → σ_{b}^{n+1}[g(n + 1) − k] with f(x) = f(x′)

is well-defined. Since a_{i} ≠ c_{i} iff a′_{i} ≠ c′_{i}, the function f is injective.

To prove f is surjective, we consider a string y ∈ σ_{b}^{n+1}[g(n + 1) − k] with digits c_{i} such that y = c_{1}c_{2} ⋯ c_{n}c_{n+1}. Then the string

y′ = c′_{1}c′_{2} ⋯ c′_{n}c′_{n+1}, where c_{i′} = \begin{cases}b − c_{i}, & if i = 1; \\ g − c_{i}, & otherwise, \end{cases}

satisfies f(y′) = y and y′ ∈ σ_{b}^{n+1}[k+1], since s(y′) = gn+b−∑ c_{i} = gn+b−(gn+g−k) = k+1. Therefore, f is bijective, so |σ_{b}^{n+1}[k + 1]| = |σ_{b}^{n+1}[g(n + 1) − k]|. (ii) Applying (15) to the second identity in Corollary 28,

\binom{n}{k}_{b4} = \binom{n}{gk}_{b} + ∑_{i=1}^{g−1} \binom{n + 1}{gk + i}_{b}

= \binom{n}{gn − gk}_{b} + ∑_{i=1}^{g−1} \binom{n + 1}{g(n + 1) − gk − i}_{b}

= \binom{n}{g(n − k)}_{b} + ∑_{i=1}^{g−1} \binom{n + 1}{g(n − k) + g − i}_{b}

= \binom{n}{g(n − k)}_{b} + ∑_{i=1}^{g−1} \binom{n + 1}{g(n − k) + i}_{b} = \binom{n}{n − k}_{b4}.

(iii) Similarly, by Lemma 26 and (15),

\begin{aligned}C_{b1}(n, k) & = ∑_{i=1}^{g−1} \binom{n}{gk − i}_{b} = ∑_{i=1}^{g−1} \binom{n}{gn − gk + i}_{b} \\ & = ∑_{i=1}^{g−1} \binom{n}{gn − gk + g − i}_{b} = ∑_{i=1}^{g−1} \binom{n}{g(n − k + 1) − i}_{b} = C_{b1}(n, n − k + 1). \end{aligned}

Even if \binom{n}{k}_{23} = \binom{n}{n−k}_{23} and C_{b1}(n, k) = C_{b1}(n, n − k + 1), the b-nomial numbers of type 3 and the sequence [C_{ba}(n, k)]_{n,k≥0} are not symmetric in general. That is,

\binom{n}{k}_{b3} ≠ \binom{n}{n − k}_{b3} for all b > 2 and C_{ba}(n, k) ≠ C_{ba}(n, n − k + 1) for all a > 1.

However, we can find the following relations for symmetric entries.

Lemma 32. For all positive integers n, integer k, and digits a = 2, 3, …, g − 1:

\begin{matrix}(i) \binom{n}{n − k + 1}_{b3} − \binom{n}{k}_{b3} = \binom{n − 1}{n − k + 1}_{b3} − \binom{n − 1}{k}_{b3}; \\ (ii) C_{ba}(n, n − k + 1) − C_{ba}(n, k) = C_{b,b−a}(n, n − k + 1) − C_{b,b−a}(n, k). \end{matrix}

Proof. (i) By (15) and Theorem 27 (i),

\begin{aligned}\binom{n}{n − k + 1}_{b3} & = ∑_{i=0}^{g−1} \binom{n}{g(n − k + 1) − i}_{b} = ∑_{i=0}^{g−1} \binom{n}{gn − (gk − g + i)}_{b} \\ & = ∑_{i=0}^{g−1} \binom{n}{gk − (g − i)}_{b} = ∑_{i=1}^{g} \binom{n}{gk − i}_{b} \\ & = ∑_{i=0}^{g−1} \binom{n}{gk − i}_{b} − \binom{n}{gk}_{b} + \binom{n}{g(k − 1)}_{b} \\ & = \binom{n}{k}_{b3} − \binom{n}{gk}_{b} + \binom{n}{g(k − 1)}_{b}. \end{aligned}  (16)

By adjusting the indices n and k in (16), we have

\binom{n − 1}{n − k + 1}_{b3} = \binom{n − 1}{n − 1 − (k − 1) + 1}_{b3} = \binom{n − 1}{k − 1}_{b3}−\binom{n − 1}{g(k − 1)}_{b}+\binom{n − 1}{g(k − 2)}_{b}. (17)

By subtracting (17) from (16) and applying Theorem 27 (i), we have

\binom{n}{n − k + 1}_{b3} − \binom{n − 1}{n − k + 1}_{b3}

= \binom{n}{k}_{b3} − \binom{n − 1}{k − 1}_{b3} − (\binom{n}{gk}_{b} − \binom{n − 1}{g(k − 1)}_{b}) + (\binom{n}{g(k − 1)}_{b} − \binom{n − 1}{g(k − 2)}_{b})

= \binom{n}{k}_{b3} − \binom{n − 1}{k − 1}_{b3} − \binom{n − 1}{k}_{b3} + \binom{n − 1}{k − 1}_{b3} = \binom{n}{k}_{b3} − \binom{n − 1}{k}_{b3},

which provides the relation in (i).

(ii) By (15) and Lemma 26, we have

\begin{aligned}C_{ba}(n, n − k + 1) & = ∑_{i=a}^{g−1} \binom{n}{gn − gk + g − i}_{b} = ∑_{i=a}^{g−1} \binom{n}{gk − g + i}_{b} = ∑_{i=1}^{g−a} \binom{n}{gk − i}_{b} \\ & = ∑_{i=1}^{g−1} \binom{n}{gk − i}_{b} − ∑_{i=g−a+1}^{g−1} \binom{n}{gk − i}_{b} = C_{b1}(n, k) − C_{b,g−a+1}(n, k). \end{aligned} (18)

By adjusting the index k, we have

C_{ba}(n, k) = C_{b1}(n, n − k + 1) − C_{b,g−a+1}(n, n − k + 1).  (19)

By subtracting (19) from (18) and applying Lemma 31 (iii), we have

C_{ba}(n, n − k + 1) − C_{ba}(n, k) = C_{b,g−a+1}(n, n − k + 1) − C_{b,g−a+1}(n, k).

Since g − a + 1 = b − a, we have the relation in (ii).

8 Acknowledgments

I would like to thank the reviewer for his/her suggestions and references, which helped to improve this paper and expand my understanding.

References

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

[2] J. Choi, Indispensable digits for digit sums, Notes Number Theory Discrete Math. 25 (2019) 40–48.

[3] J. E. Freund, Restricted occupancy theory — a generalization of Pascal’s triangle, Amer. Math. Monthly 63 (1956) 20–27.

[4] D. C. Fielder and C. O. Alford, Pascal’s triangle: top gun or just one of the gang?, Applications of Fibonacci Numbers 4 (1991) 77–90.

[5] S. Eger, Restricted weighted integer compositions and extended binomial coefficients, J. Integer Sequences 16 (2013) Article 13.1.3.

[6] C. H. Jones, Generalized hockey stick identities and n-dimensional block walking, Fibonacci Quart. 34 (1996), 280–288.

[7] T. Neuschel, A note on extended binomial coefficients, J. Integer Sequences 17 (2014) Article 14.10.4.

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

[9] J. Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2009.

[10] N. J. A. Sloane et al., On-line Encyclopedia of Integer Sequences, https://oeis.org, 2019.

[11] E. W. Weisstein, MathWorld-A Wolfram Web Resource, http://mathworld.wolfram.

    com/Concatenation.html.

2010 Mathematics Subject Classification: Primary 11A63; Secondary 05A10. Keywords: digit sum, indispensable digit, binomial coefficient, extended binomial coefficient, polynomial coefficient, generation of binomial coefficient.

(Concerned with sequences \underline{A005773}, \underline{A007318}, \underline{A008287}, \underline{A027907}, and \underline{A071976}.)

Received July 7 2019; revised version received December 9 2019. Published in Journal of Integer Sequences, December 11 2019.

Return to Journal of Integer Sequences home page.