Some Combinatorics of Factorial Base Representations

Tyler Ball Clover Park High School Lakewood, WA 98499 USA

     t.ball.6174@gmail.com

Paul Dalenberg Department of Mathematics Oregon State University Corvallis, OR 97331 USA

    dalenbep@oregonstate.edu

Joanne Beckford University of Pennsylvania Philadelphia, PA 19104 USA

                                         joannemb@sas.upenn.edu

Tom Edgar Department of Mathematics Pacific Lutheran University Tacoma, WA 98447 USA

                                            edgartj@plu.edu

Tina Rajabi University of Washington Seattle, WA 98195 USA

                          rajabit@uw.edu

Abstract

Every non-negative integer can be written using the factorial base representation. We explore certain combinatorial structures arising from the arithmetic of these representations. In particular, we investigate the sum-of-digits function, carry sequences, and a partial order referred to as digital dominance. Finally, we describe an analog of a classical theorem due to Kummer that relates the combinatorial objects of interest by constructing a variety of new integer sequences.

1 Introduction

Kummer’s theorem famously draws a connection between the traditional addition algorithm of base-p representations of integers and the prime factorization of binomial coefficients.

Theorem 1 (Kummer). Let n, m, and p all be natural numbers with p prime. Then the exponent of the largest power of p dividing \binom{n+m}{n} is the sum of the carries when adding the base-p representations of n and m.

Ball et al. [2] define a new class of generalized binomial coefficients that allow them to extend Kummer’s theorem to base-b representations when b is not prime, and they discuss connections between base-b representations and a certain partial order, known as the base-b (digital) dominance order. Furthermore, when p is prime, de Castro et al. [3] show that this partial order encodes more information about the exponents of the corresponding binomial coefficients, adding to investigations of Pascal’s triangle modulo prime powers and related Sierpiński-like triangles arising from generalized binomial coefficients.

Edgar et al. [5] use similar techniques with rational base representations to describe families of generalized binomial coefficients with Kummer’s theorem analogs for the corresponding representations. In the present work, we investigate the representation of integers as sums of factorials, which have been well-studied [7, 8, 13, 14]. We use these representations to define a new family of integer partitions, some new families of generalized binomial coefficients, and the corresponding digital dominance order yielding analogs of Kummer’s theorem for these representations. The paper is organized as follows. In Section 2, we discuss known results about factorial base representations, the factorial base sum-of-digits function, and the arithmetic arising from these representations. In Section 3, we investigate the set of carry sequences coming from factorial base arithmetic and explain how these sequences are connected to a new family of integer partitions, which we call hyperfactorial partitions; in particular, we describe how to construct, and how to count, hyperfactorial partitions. In Section 4, we introduce the notion of generalized binomial coefficients and describe three different families of generalized binomial coefficients. We show that all of these generalized binomial coefficients are integral by producing three different analogs of Kummer’s theorem for factorial base representations. Finally, in Section 5, we demonstrate how the results of de Castro et al. [3] basically extend to factorial base representations and describe the connections between the factorial base sum-of-digits function, hyperfactorial partitions, one family of generalized binomial coefficients, and the digital dominance order defined in terms of factorial base representations.

2 Factorial base representations and the sum-of-digits function

Figure 1 [4] provides a visual demonstration (in the case when ℓ = 4) of the fact that

∑_{i=1}^{ℓ} i · i! = (ℓ + 1)! − 1  (1)

for all positive integers ℓ, which can be proved in general by induction; this formula provides the well-known fact that every natural number n can be written uniquely as

n = n_{1} · 1! + n_{2} · 2! + n_{3} · 3! + ⋯ + n_{k} · k! = ∑_{i=1}^{k} n_{i} · i!

where 0 ≤ n_{i} ≤ i for all i and n_{k} ≠ 0. We call the finite list n = (n_{1}, n_{2}, n_{3}, …, n_{k})_{!} the factorial base representation for n. We note that we have written the factorial base in order from the least significant to most significant digit, which is nonstandard. Also, we mention that it is often convenient to append 0’s to a representation to change the length of the corresponding list. Factorial base representations have been well-studied and provide a standard way of enumerating and ranking permutations [7, 8, 9, 10, 12, 13].

For example 17 = 1·1!+2·2!+2·3! so 17 = (1, 2, 2)_{!} and 705 = 1·1!+1·2!+1·3!+4·4!+5·5! so that 705 = (1, 1, 1, 4, 5)_{!}. We also define the factorial base sum-of-digits function s_{!} by s_{!}(n) = ∑_{i=1}^{k} n_{i} where n = (n_{1}, n_{2}, …, n_{k})_{!}, so that s_{!}(17) = 1 + 2 + 2 = 5 and s_{!}(705) = 1 + 1 + 1 + 4 + 5 = 12.

Fraenkel [8] shows how to construct factorial base representations using the repeated division algorithm; one consequence of his construction is the following factorial base digit formula, which can also be proved using equation 1.

Theorem 2. Let n be a natural number with n = (n_{1}, n_{2}, …, n_{k})_{!}. Then for all 0 ≤ i ≤ k,

\begin{aligned}n_{i} & = ⌊(i + 1) · \{\frac{n}{(i + 1)!}\}⌋ \\ & = ⌊\frac{n}{i!}⌋ mod (i + 1), \end{aligned}

where {x} = x − ⌊x⌋ represents the fractional part of x.

The following corollary seems to be well known.

Corollary 3. For all n ∈ ℕ, s_{!}(n) = n − ∑_{i=1}^{k} i · ⌊\frac{n}{(i+1)!}⌋.

Proof. Let n = (n_{1}, n_{2}, …, n_{k})_{!}. Then by Theorem 2,

{2! \atop 3} =

{4 \atop 3!} =

{5 \atop 4!}

Figure 1: A proof without words about the factorial sum in equation (1).

\begin{aligned}s_{!}(n) = ∑_{i=1}^{k} n_{i} = ∑_{i=1}^{k} ⌊(i + 1) · \{\frac{n}{(i + 1)!}\}⌋ & = ∑_{i=1}^{k} ⌊(i + 1) (\frac{n}{(i + 1)!} − ⌊\frac{n}{(i + 1)}!⌋)⌋ \\ & = ∑_{i=1}^{k} ⌊\frac{n}{i!} − (i + 1) ⌊\frac{n}{(i + 1)!}⌋⌋ . \end{aligned}

Note that ⌊x − m⌋ = ⌊x⌋ − m when m is an integer with m ≤ x, and that (i + 1) ⌊\frac{n}{(i+1)!}⌋ is an integer so that we now have

s!(n) = ∑_{i=1}^{k} ⌊\frac{n}{i!}⌋ − ∑_{i=1}^{k}(i + 1) ⌊\frac{n}{(i + 1)!}⌋ = ∑_{i=1}^{k} ⌊\frac{n}{i!}⌋ − ∑_{i=2}^{k+1} i ⌊\frac{n}{i!}⌋

= ⌊\frac{n}{1!}⌋ + ∑_{i=2}^{k+1} ⌊\frac{n}{i!}⌋ − ⌊\frac{n}{(k + 1)!}⌋ − ∑_{i=2}^{k+1} i ⌊\frac{n}{i!}⌋

= n − ⌊\frac{n}{(k + 1)!}⌋ + ∑_{i=2}^{k+1} ⌊\frac{n}{i!}⌋ − ∑_{i=2}^{k+1} i ⌊\frac{n}{i!}⌋

= n − ⌊\frac{n}{(k + 1)!}⌋ − ∑_{i=2}^{k+1}(i − 1) ⌊\frac{n}{i!}⌋

= n − ⌊\frac{n}{(k + 1)!}⌋ − ∑_{i=1}^{k} i ⌊\frac{n}{(i + 1)!}⌋ .

However, since n < (k +1)!, we have ⌊\frac{n}{(k+1)!}⌋ = 0; therefore, s_{!}(n) = n−∑_{i=1}^{k} i · ⌊\frac{n}{(i+1)!}⌋.

The OEIS [18] lists the factorial base sum-of-digits sequence in \underline{A034968}; the first few terms of this sequence are

0, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, ….

Figure 1 inspires us to write this sequence in an irregular table in Figure 2; each of the rows T_{n−1} + 1 through T_{n} have n! entries where T_{ℓ} = ∑_{i=1}^{ℓ} i represents the triangular number.

row 0 0
row 1 1
row 2 1 2
row 3 2 3
row 4 1 2 2 3 3 4
row 5 2 3 3 4 4 5
row 6 3 4 4 5 5 6
row 7 1 2 2 3 3 4 2 3 3 4 4 5 3 4 4 5 5 6 4 5 5 6 6 7
row 8 2 3 3 4 4 5 3 4 4 5 5 6 4 5 5 6 6 7 5 6 6 7 7 8
row 9 3 4 4 5 5 6 4 5 5 6 6 7 5 6 6 7 7 8 6 7 7 8 8 9
row 10 4 5 5 6 6 7 5 6 6 7 7 8 6 7 7 8 8 9 7 8 8 9 9 10

Figure 2: The factorial base sum-of-digits sequence arranged in an irregular table inspired by Figure 1.

Notice that row T_{n} + 1 (highlighted in red) can be obtained by re-listing all of the entries from rows T_{n−1} + 1 to T_{n} followed by the entries of row T_{n} each incremented by 1. For instance, row 11 (not pictured) would contain 120 entries: the first 24 would be the same as row 7, the second 24 the same as row 8, the third 24 the same as row 9, the fourth 24 the same as row 10, and the last 24 would be obtained by incrementing each entry of row 10 by 1:

row 10 5 6 6 7 7 8 6 7 7 8 8 9 7 8 8 9 9 10 8 9 9 10 10 11 +1

Furthermore, notice that row T_{n} + 1 always begins with 1 since this entry corresponds to the sum of digits of n!. By equation (1), we see that the last entry in row T_{n} is T_{n} since this entry corresponds to the sum of digits of n! − 1 = (1, 2, 3, …, n − 1)_{!}. There are many other interesting patterns to find in this table; for instance, if we fix a row, say r, with ℓ! entries, then the sum of entries s and ℓ! − s in row r will be the same no matter what s we choose.

We finish this section by describing the arithmetic of factorial base representations. Lenstra [14] states how to determine the factorial base representation of a sum if we know the factorial base representations of the two summands. We make the process more formal in order to define a combinatorial object of interest. Given two positive integers n and m, we define the factorial carry sequence for n and m, denoted ϵ_{!}^{n,m} = (ϵ_{0}, ϵ_{1}, ϵ_{2}, …, ϵ_{k}), by

\begin{matrix}ϵ_{0} = 0; \\ ϵ_{i} = \begin{cases}0, & if n_{i} + m_{i} + ϵ_{i−1} ≤ i; \\ 1, & if n_{i} + m_{i} + ϵ_{i−1} > i. \end{cases} \end{matrix}

We will leave off the subscript, !, and when there is no confusion about n and m, we will simply write ϵ := ϵ_{!}^{n,m}. An alternate characterization of each entry in ϵ^{n,m} is given by the following proposition.

Proposition 4. Let ϵ be the factorial carry sequence for two natural numbers n and m. Then ϵ_{i} = ⌊\frac{ϵ_{i−1}+n_{i}+m_{i}}{i+1} ⌋ for i > 0.

Proof. Let 1 ≤ i ≤ k.

Case 1. If ϵ_{i−1} + m_{i} + n_{i} ≤ i, then ϵ_{i} = 0 and

0 = ⌊\frac{0 + 0 + 0}{i + 1}⌋ ≤ ⌊\frac{m_{i} + n_{i} + ϵ_{i−1}}{i + 1} ⌋ ≤ ⌊\frac{i}{i + 1}⌋ = 0.

Therefore, ⌊\frac{m_{i}+n_{i}+ϵ_{i−1}}{i+1} ⌋ = 0.

Case 2. If ϵ_{i−1} + m_{i} + n_{i} ≥ i + 1, then ϵ_{i} = 1 and

1 = ⌊\frac{i + 1}{i + 1}⌋ ≤ ⌊\frac{m_{i} + n_{i} + ϵ_{i−1}}{i + 1} ⌋ ≤ ⌊\frac{i + i + 1}{i + 1}⌋ = ⌊\frac{2i + 1}{i + 1}⌋ = 1

Therefore, ⌊\frac{m_{i}+n_{i}+ϵ_{i−1}}{i+1} ⌋ = 1.

Since in each case the equality holds, ϵ_{i} = ⌊\frac{ϵ_{i−1}+n_{i}+m_{i}}{i+1} ⌋.

The carry sequence allows us to construct the factorial base representation of the sum of two integers.

Theorem 5. Let n = (n_{1}, n_{2}, …, n_{k})_{!}, m = (m_{1}, m_{2}, …, m_{k})_{!}, and n + m = ((n + m)_{1}, (n + m)_{2}, …, (n + m)_{k}))_{!} where we append zeroes to ensure all three representations are the same length. If ϵ = (ϵ_{0}, ϵ_{1}, …, ϵ_{k}) is the factorial carry sequence for n and m, then (n + m)_{i} = n_{i} + m_{i} + ϵ_{i−1} − ϵ_{i} · (i + 1) for all i.

Proof. For each i ≤ k, we define a_{i} = n_{i} + m_{i} + ϵ_{i−1} − ϵ_{i} · (i + 1). Note that if i + 1 ≤ n_{i} + m_{i} + ϵ_{i−1} ≤ 2i + 1, then by definition ϵ_{i} = 1. Subtracting i + 1 from the inequality yields 0 ≤ n_{i} + m_{i} + ϵ_{i−1} − (1)(i + 1) = n_{i} + m_{i} + ϵ_{i−1} − ϵ_{i}(i + 1) = a_{i} < i. On the other hand, if 0 ≤ n_{i} + m_{i} + ϵ_{i−1} ≤ i, then by definition ϵ_{i} = 0. Therefore 0 ≤ n_{i} + m_{i} + ϵ_{i−1} − 0 = n_{i} + m_{i} + ϵ_{i−1} − ϵ_{i}(i + 1) = a_{i} ≤ i. In either case, 0 ≤ a_{i} ≤ i, and so (a_{1}, a_{2}, …, a_{k})_{!} is a factorial base representation of some number a.

Now, we see that

∑_{i=1}^{k} a_{i} · i! = ∑_{i=1}^{k} (n_{i} + m_{i} + ϵ_{(i−1)} − ϵ_{i} · (i + 1)) · i!

= ∑_{i=1}^{k} n_{i} · i! + ∑_{i=1}^{k} m_{i} · i! + ∑_{i=1}^{k} ϵ_{i−1} · i! − ∑_{i=1}^{k} ϵ_{i} · (i + 1)!

= n + m + ∑_{i=0}^{k−1} ϵ_{i} · (i + 1)! − ∑_{i=1}^{k+1} ϵ_{i} · (i + 1)!

= n + m + ϵ_{0} · 1 − ϵ_{k} · (k + 2)

= n + m,

where the last equality follows since ϵ_{0} = 0 = ϵ_{k}. Indeed, if ϵ_{k} = 1, then (n + m)_{k+1} ≠ 0 contradicting the form for the representation of n + m. Therefore, n + m = ∑_{i=1}^{k+1} a_{!} · i!.

For instance, when adding 705 = (1, 1, 1, 4, 5)_{!} and 133 = (1, 0, 2, 0, 1)_{!}, we compute the carry sequence to be (0, 1, 0, 0, 0, 1, 0). Then the addition can be obtained by using the following diagram adding columns from left to right in a similar fashion to the standard algorithm for adding base-b representations, where we “carry a one” if the sum of the digits exceeds the place value.

(0, 1, 0, 0, 0, 1, 0) ϵ: (1, 1, 1, 4, 5, 0)_{!} 705: (1, 0, 2, 0, 1, 0)_{!} 133: + (0, 2, 3, 4, 0, 1)_{!} 838:

It turns out that the carry sequence has a relationship to the subadditivity of the sumof-digits function, and the following theorem will be useful for later results.

Theorem 6. Let n and m be natural numbers and ϵ = (ϵ_{0}, ϵ_{1}, …, ϵ_{k}) be the factorial carry sequence for n and m. Then

s_{!}(n) + s_{!}(m) − s_{!}(n + m) = ∑_{i=1}^{k} ϵ_{i} · i.

Proof. Let n = (n_{1}, n_{2}, …, n_{k})_{!} and m = (m_{1}, m_{2}, …, m_{k})_{!}, and m + n = ((m + n)_{1}, (m + n)_{2}, …, (m + n)_{k}), where k is the index of the largest non-zero digit of (m + n) (again we append zeroes to the representations of n and m for ease of notation). Note that n_{k+1} = m_{k+1} = (n + m)_{k+1} = 0 by assumption. Theorem 5 also implies that n_{i} + m_{i} − (n + m)_{i} = ϵ_{i} · (i + 1) − ϵ_{i−1} for each i.

Now, we see that

s_{!}(n) + s_{!}(m) − s_{!}(m + n) = ∑_{i=1}^{k} n_{i} + ∑_{i=1}^{k} m_{i} − ∑_{i=1}^{k}(m + n)_{i} = ∑_{i=1}^{k}(n_{i} + m_{i} − (n + m)_{i})

= ∑_{i=1}^{k}(ϵ_{i} · (i + 1) − ϵ_{i−1})

= ∑_{i=1}^{k} i · ϵ_{i} + ∑_{i=1}^{k} ϵ_{i} − ∑_{i=0}^{k−1} ϵ_{i}

= ∑_{i=1}^{k} i · ϵ_{i} + ϵ_{k} − ϵ_{0}

= ∑_{i=1}^{k} i · ϵ_{i},

where, as in the proof of Theorem 5, we note that ϵ_{k} = 0 = ϵ_{0}.

3 Carry sequences and hyperfactorial partitions

We now turn the idea of carry sequences upside down: we say a number n utilizes a carry sequence ϵ if there are numbers x and y such that x + y = n and ϵ is the carry sequence for x and y. Let C_{!}(n) be the number of distinct carry sequences utilized by n. The first 20 values of this integer sequence (see \underline{A331128}) are given below.

1, 1, 2, 1, 2, 1, 3, 2, 4, 2, 3, 1, 3, 2, 4, 2, 3, 1, 3, 2, …

As we did with the sum-of-digits function in Figure 2, Figure 3 arranges the sequence C_{!} in the irregular table of the form given by the visual proof in Figure 1.

It turns out that counting the number of carry sequences utilized by a positive integer n is a bit complicated, so we rephrase the problem. For any natural number n, we say the list [h_{1}, h_{2}, …, h_{k}]_{!} is a hyperfactorial partition of n if 0 ≤ h_{i} ≤ 2i for each i and n = h_{1} · 1! + h_{2} · 2! + ⋯ + h_{k} · k!. For instance, the six hyperfactorial partitions of 705 are listed below.

\begin{aligned}705 & = 1 · 1! + 1 · 2! + 1 · 3! + 4 · 4! + 5 · 5! = [1, 1, 1, 4, 5]_{!} \\ 705 & = 1 · 1! + 1 · 2! + 5 · 3! + 3 · 4! + 5 · 5! = [1, 1, 5, 3, 5]_{!} \\ 705 & = 1 · 1! + 4 · 2! + 4 · 3! + 3 · 4! + 5 · 5! = [1, 4, 4, 3, 5]_{!} \\ 705 & = 1 · 1! + 4 · 2! + 4 · 3! + 8 · 4! + 4 · 5! = [1, 4, 4, 8, 4]_{!} \\ 705 & = 1 · 1! + 1 · 2! + 5 · 3! + 8 · 4! + 4 · 5! = [1, 1, 5, 8, 4]_{!} \\ 705 & = 1 · 1! + 4 · 2! + 0 · 3! + 4 · 4! + 5 · 5! = [1, 4, 0, 4, 5]_{!}. \end{aligned}

Note that the factorial base representation always gives rise to a hyperfactorial partition.

Theorem 7. Let x = (x_{1}, x_{2}, …, x_{k})_{!}, y = (y_{1}, y_{2}, …, y_{k})_{!} and n = x+y. Then [x_{1}+y_{1}, x_{2}+ y_{2}, …, x_{k} + y_{k}]_{!} is a hyperfactorial partition of n.

row 0 1
row 1 1
row 2 2 1
row 3 2 1
row 4 3 2 4 2 3 1
row 5 3 2 4 2 3 1
row 6 3 2 4 2 3 1
row 7 4 3 6 3 5 2 6 4 8 4 6 2 6 4 8 4 6 2 5 3 6 3 4 1
row 8 4 3 6 3 5 2 6 4 8 4 6 2 6 4 8 4 6 2 5 3 6 3 4 1
row 9 4 3 6 3 5 2 6 4 8 4 6 2 6 4 8 4 6 2 5 3 6 3 4 1
row 10 4 3 6 3 5 2 6 4 8 4 6 2 6 4 8 4 6 2 5 3 6 3 4 1

Figure 3: The number of carry sequences sequence arranged in an irregular array. By Corollary 10 this also shows the hyperfactorial sequence arranged in this array.

Proof. Let 1 ≤ i ≤ k. Since 0 ≤ x_{i} ≤ i and 0 ≤ y_{i} ≤ i, we conclude 0 ≤ x_{i} + y_{i} ≤ 2i. Further, n = x + y = ∑_{i=1}^{k} x_{i} · i! + ∑_{i=1}^{k} y_{i} · i! = ∑_{i=1}^{k}(x_{i} + y_{i}) · i. Therefore, by definition, [x_{1} + y_{1}, x_{2} + y_{2}, …, x_{k} + y_{k}]_{!} is a hyperfactorial partition of n.

Given positive integers x = (x_{1}, x_{2}, …, x_{k})_{!} and y = (y_{1}, y_{2}, …, y_{k})_{!}, we let x ⊞_{!} y = [x_{1} + y_{1}, x_{2} + y_{2}, …, x_{k} + y_{k}]_{!} be the hyperfactorial partition guaranteed by Theorem 7. We will utilize this notion further in Section 5.

Theorem 8. Let n = (n_{1}, n_{2}, …, n_{k})_{!}, x = (x_{1}, x_{2}, …, x_{k})_{!}, y = (y_{1}, y_{2}, …, y_{k})_{!}, w = (w_{1}, w_{2}, …, w_{k})_{!}, and z = (z_{1}, z_{2}, …, z_{k})_{!}. Moreover assume that x + y = n and w + z = n and ϵ^{x,y} = ϵ^{w,z}. Then x_{i} + y_{i} = w_{i} + z_{i} for all i.

Proof. Let 1 ≤ i ≤ k. By Theorem 5, n_{i} = ϵ_{i−1} + x_{i} + y_{i} − (i + 1) · ϵ_{i}, and n_{i} = ϵ_{i−1} + w_{i} + z_{i} − (i + 1) · ϵ_{i}. Equating these two shows that x_{i} + y_{i} = w_{i} + z_{i} as required.

Theorem 9. Let x = (x_{1}, x_{2}, …, x_{k})_{!}, y = (y_{1}, y_{2}, …, y_{k})_{!}, w = (w_{1}, w_{2}, …, w_{k})_{!}, and z = (z_{1}, z_{2}, …, z_{k})_{!}. Assume that x_{i} + y_{i} = w_{i} + z_{i} for all i. Then x + y = w + z and ϵ^{x,y} = ϵ^{w,z}.

Proof. It is clear that x + y = w + z, so let n = x + y = w + z. By assumption, we know that x_{i} + y_{i} = w_{i} + z_{i} for all i. We proceed by induction.

Base Case. By definition ϵ_{0}^{x,y} = 0 = ϵ_{0}^{w,z}.

Inductive Step. Let i ≥ 0 and assume ϵ_{i}^{x,y} = ϵ_{i}^{w,z}. By Proposition 4

ϵ_{i+1}^{x,y} = ⌊\frac{x_{i+1} + y_{i+1} + ϵ_{i}^{x,y}}{i + 2} ⌋ and ϵ_{i+1}^{w,z} = ⌊\frac{w_{i+1} + z_{i+1} + ϵ_{i}^{w,z}}{i + 2} ⌋

However, by assumption x_{i+1} + y_{i+1} = w_{i+1} + z_{i+1}; thus

ϵ_{i+1}^{x,y} = ⌊\frac{x_{i+1} + y_{i+1} + ϵ_{i}^{x,y}}{i + 2} ⌋ = ⌊\frac{w_{i+1} + z_{i+1} + ϵ_{i}^{w,z}}{i + 2} ⌋ = ϵ_{i+1}^{w,z}.

Therefore ϵ_{i}^{x,y} = ϵ_{i}^{w,z} for all i so that ϵ^{x,y} = ϵ^{w,z}.

Thus x⊞_{!} y = w ⊞_{!} z if and only if x+y = w +z and ϵ^{x,y} = ϵ^{w,z} and we have the following corollary.

Corollary 10. The set of hyperfactorial partitions of n is in one-to-one correspondence with the set of carry sequences utilized by n.

Proof. The previous three theorems demonstrate how to create a hyperfactorial partition from a carry sequence and how to create a carry sequence from a hyperfactorial partition. Moreover, closer investigation of the proofs show that these two processes are inverses to one another.

Thus, the problem of determining the number of unique carry sequences utilized by an integer is equivalent to determining the number of hyperfactorial partitions that integer has. We provide a recursive formula for the sequence C_{!} pictured in Figure 3.

Theorem 11. Let n = (n_{1}, n_{2}, …, n_{k})_{!} be a natural number and C_{!}(n) be the number of hyperfactorial partitions of n. Then

C_{!}(n) = \begin{cases}0, & n < 0; \\ 1, & n = 0; \\ C_{!}(n − n_{k} · k!) + C_{!}((n_{k} + 1)k! − n − 2), & otherwise. \end{cases}

Proof. First, note that n_{k} · k! ≤ n < n_{k+1} · k!. Let [h_{1}, h_{2}, …, h_{k}]_{!} be a hyperfactorial partition of n so that n = ∑_{i=1}^{k} h_{i} · i!. Note that h_{k} ≤ n_{k} since otherwise we would have n = ∑_{i=1}^{k} h_{i} · i! ≥ h_{k} · k! ≥ (n_{k} + 1) · k! > n. Likewise h_{k} > n_{k} − 2 since otherwise we would have

n = ∑_{i=1}^{k} h_{i} · i! = h_{k} + ∑_{i=1}^{k−1} h_{i} · i!

≤ (n_{k} − 2)k! + ∑_{i=1}^{k−1} 2i · i!

= n_{k} · k! − 2 < n

where we note that ∑_{i=1}^{k−1} 2i · i! = 2(k! − 1) by equation (1). Therefore, h_{k} = n_{k} or n_{k} − 1.

Case 1. Let h_{k} = n_{k}. Let n′ be the positive integer n′ = n − n_{k} · k!. Then n′ = h_{1} · 1! + h_{2} · 2! + … + h_{k−1} · (k − 1)! so that [h_{1}, h_{2}, …, h_{k−1}]_{!} is a hyperfactorial partition of n′.

Furthermore, note that n′ = n − n_{k} · k! < (n_{k} + 1)k! − n_{k} · k! = k!. Therefore, in any hyperfactorial partition [h′_{1}, h′_{2}, …, h′_{k−1}, h′_{k}]_{!} of n′, h′_{k} = 0, and so [h′_{1}, h′_{2}, …, h′_{k−1}, n_{k}]_{!} is a hyperfactorial partition of n − (n_{k} · k!) + n_{k} · k! = n. Thus every hyperfactorial partition of n′ gives rise to a hyperfactorial partition of n with h_{k} = n_{k}.

Case 2. Let h_{k} = n_{k} − 1, and let n′′ = (n_{k} + 1)k! − n − 2. Then

n′′ = (n_{k} + 1)k! − (∑_{i=1}^{k} h_{i} · i!) − 2 = (n_{k} + 1)k! − (n_{k} − 1) · k! − (∑_{i=1}^{k−1} h_{i} · i!) − 2

= 2k! − 2 − (∑_{i=1}^{k−1} h_{i} · i!)

= 2 · ∑_{i=1}^{k−1} i · i! − (∑_{i=1}^{k−1} h_{i} · i!)

= ∑_{i=1}^{k−1}(2i − h_{i}) · i!.

Note, that since 0 ≤ 2i−h_{i} ≤ 2i for all i, we see that [2−h_{1}, 4−h_{2}, …, 2(k−1)−h_{k−1}]_{!} is a hyperfactorial partition of n′′ = (n_{k} + 1)k! − n − 2.

Again, note that n′′ ≤ (n_{k} + 1)k! − n_{k} · k! − 2 = k! − 2 < k! so that given any hyperfactorial partition [h′_{1}, h′_{2}, …, h′_{k}]_{!} of n′′, we must have h′_{k} = 0 so that [2 − h′_{1}, 4 − h′_{2}, …, 2(k − 1) − h′_{k−1}, n_{k} − 1]_{!} = 2k! − 2 − [h′_{1}, h′_{2}, …, h′_{k−1}, 0]_{!} + (n_{k} − 1)k! = 2k! − 2 − ((n_{k} + 1)k! − n − 2) + (n_{k} − 1)k! = n. Thus, every hyperfactorial partition of n′′ yields to a hyperfactorial partition of n with h_{k} = n_{k} − 1.

The two cases above show that the set of hyperfactorial partitions of n correspond to the disjoint union of the sets of hyperfactorial partitions of the numbers n′ = n − n_{k} · k! and n′′ = (n_{k} + 1)k! − n − 2 so that C_{!}(n) = C_{!}(n − n_{k} · k!) + C_{!}((n_{k} + 1)k! − n − 2).

In relation to Figure 3, Theorem 11 shows that we can obtain the entries of row T_{n} + 1 from all of the previous rows in a straightforward fashion. We line up all the entries from row 0 to row T_{n} forming a single list with (n + 1)! numbers, where the final number is 1. We discard that final entry of 1 leaving us with a single list consisting of (n + 1)! − 1 numbers. Then entry i in row T_{n} + 1 can be obtained by adding the entry i to entry (n + 1)! − 1 − i from the newly created single array. The final entry of row T_{n} + 1 is set to 1.

We demonstrate the method from the previous paragraph with the example of finding row 7 (since 7 = T_{3} + 1). First, we line up all the entries from row 0 to row T_{3} = 6 in order, and we strike out the final 1 as below.

1 1 2 1 2 1 3 2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 \overline{1}

Notice that this new row of numbers has 23 = 4! − 1 entries. Then, entry i in row 7 of the array in Figure 3 can be obtained from this new 23-number array by adding entry i to entry 23 − i. For instance, we have the first few entries determined in the array below (color coded for adding).

1 1 2 1 2 1 3 2 4 2 3 1 3 2 4 2 3 1 3 2 4 2 3 \overline{1} 4 3 6 3 5 2 6 4 8 4 6 2 6 4 8 4 6 2 5 3 6 3 4 1

The final entry in row 7 = T_{3} + 1 is then 1. For instance, in blue we see that entry 0 plus entry 23 from our new single array gives a sum of 4, which we put as entry zero in row 7 in Figure 3.

This interpretation demonstrates that the first (n + 1)! − 1 entries of row T_{n} + 1 will have symmetry about the entry \frac{(n+1)!}{2}. Moreover, one can prove that this middle term of row T_{n} + 1 will always be a 2 or a 4.

Finally, we note that Theorem 11 shows that row T_{n} + i is equal to row T_{n} + 1 for 1 ≤ i ≤ (n + 1), thus allowing us to build the array in Figure 3 recursively. Remark 12. The proof of Theorem 11 demonstrates not only how to find the number of hyperfactorial partitions of a positive integer, but also how to recursively construct the family of hyperfactorial partitions of that integer.

4 Generalized binomial coefficients and analogues of Kummer’s theorem

As previously noted, Kummer’s theorem connects base-p arithmetic (in particular the number of carries) to the prime factorization of binomial coefficients. Moreover, this theorem provides a connection between Pascal’s triangle and various Sierpiński-like triangles. In this section, we construct three different integer sequences and their corresponding generalized binomial coefficients to show how each of these families is related to the carries arising from factorial base arithmetic. The triangular arrays arising from these generalized binomial coefficients also appear to be Sierpiński-like, which aligns them with recent families of exotic binomial coefficients of words introduced and studied by Leroy, Rigo, and Stipulanti [15, 16, 17]. It would be interesting to study our triangular arrays in their context. We investigate certain properties of these triangular arrays in the next section.

Given a sequence of positive integers a = (a_{1}, a_{2}, a_{3}, …), we define the a-factorial function by F_{a}(n) = a_{1} · a_{2} · . . . · a_{n} = ∏_{i=1}^{n} a_{i}. We then use the a-factorial to define the array of a-binomial coefficients

\binom{n}{ℓ}_{a} = \frac{F_{a}(n)}{F_{a}(ℓ)F_{a}(n − ℓ)}.

For an arbitrary integer sequence, a, we do not expect the a-binomial coefficients to be integers. However, Knuth and Wilf [11] show that if a is strongly divisible then \binom{n}{ℓ}_{a} will always be an integer, and Edgar and Spivey [6] show that if a is both divisible and multiplicative, then \binom{n}{ℓ}_{a} will always be an integer. Neither of these characterizations is necessary, and there are a variety of sequences, some coming from sum-of-digit functions, that yield integer generalized binomial coefficients yet do not satisfy nice divisibility properties [1, 2, 5].

For many of the proofs in this section, we rely on the following lemma, which is a consequence of equation (1).

Lemma 13. Let n = (n_{1}, n_{2}, …, n_{k})_{!} be a natural number. Then for all 1 ≤ i ≤ k

⌊\frac{n}{i!}⌋ = ∑_{j=i}^{k} (\frac{j!}{i!}) · n_{j}.

Proof. Note that

⌊\frac{n}{i!}⌋ = ⌊∑_{j=1}^{k} \frac{n_{j} · j!}{i!}⌋ = ⌊∑_{j=1}^{i−1} \frac{n_{j} · j!}{i!} + ∑_{j=i}^{k} \frac{n_{j} · j!}{i!}⌋ = ⌊∑_{j=1}^{i−1} \frac{n_{j} · j!}{i!}⌋ + ∑_{j=i}^{k} \frac{n_{j} · j!}{i!},

since ∑_{j=i}^{k} \frac{n_{j}·j!}{i!} is an integer. Then, by equation (1),

0 ≤ ⌊∑_{j=1}^{i−1} \frac{n_{j} · j!}{i!}⌋ ≤ ⌊∑_{j=1}^{i−1} \frac{j · j!}{i!}⌋ ≤ ⌊\frac{i! − 1}{i!}⌋ = 0,

so that ⌊\frac{n}{i!}⌋ = ∑_{j=i}^{k} \frac{n_{j}·j!}{i!}.

4.1 First analog of Kummer’s theorem

First, we define the function v to be the factorial base leading-zero counting function, so that v(n) gives the number of leading zeros in the factorial base representation of n (see A230403 in [18]). For example, v(24) = 3, v(25) = 0, and v(26) = 1, since 24 = (0, 0, 0, 1)_{!}, 25 = (1, 0, 0, 1)_{!}, and 26 = (0, 1, 0, 1)_{!} respectively.

Now, we define the associated sequence, V, by V (n) = 2^{v(n)}. The first 18 values of the sequences v, V, and F_{V} are listed in Table 1.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ v(n) & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 1 & 0 \\ V (n) & 1 & 2 & 1 & 2 & 1 & 4 & 1 & 2 & 1 & 2 & 1 \\ F_{V} (n) & 1 & 2 & 2 & 4 & 4 & 16 & 16 & 32 & 32 & 64 & 64 \end{matrix}

\begin{matrix}n & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ v(n) & 2 & 0 & 1 & 0 & 1 & 0 & 2 \\ V (n) & 4 & 1 & 2 & 1 & 2 & 1 & 4 \\ F_{V} (n) & 256 & 256 & 512 & 512 & 1024 & 1024 & 4096 \end{matrix}

Table 1: Sequences derived from v, the leading zero function.

The next two results show that the V -binomial coefficients are all integers and that these generalized binomial coefficients are related to factorial base arithmetic, providing our first analog of Kummer’s theorem.

Lemma 14. For any natural number n, we have

v(n) = ∑_{i≥2} ⌊\frac{n}{i!}⌋ − ∑_{i≥2} ⌊\frac{n − 1}{i!}⌋ and F_{V} (n) = 2∑^{j≥2}^{⌊^{\frac{n}{j!}}⌋}.

Proof. Let n ∈ ℕ and x = v(n) + 1. Then n = (0, 0, …, 0, n_{x}, n_{x+1}, n_{x+2}, …, n_{k})_{!} where n_{x} > 0. We can use the addition algorithm from Theorem 5 or equation (1) to see that n − 1 = (1, 2, …, x − 1, n_{x} − 1, n_{x+1}, n_{x+2}, …, n_{k})_{!}. Then Lemma 13 implies that

∑_{i≥2} ⌊\frac{n}{i!}⌋−∑_{i≥2} ⌊\frac{n − 1}{i!}⌋ = ∑_{i≥2} ∑_{j≥i} (\frac{j!}{i!}) n_{j} −∑_{i≥2} ∑_{j≥i} (\frac{j!}{i!}) (n−1)_{j} = ∑_{i≥2} ∑_{j≥i} \frac{j!}{i!}(n_{j} −(n−1)_{j}).

Now, we see from the representations of n and n − 1 that

n_{j} − (n − 1)_{j} = \begin{cases}0 − j, & j < x; \\ n_{x} − (n_{x} − 1) = 1, & j = x; \\ n_{j} − n_{j} = 0, & j > x. \end{cases}

Therefore,

∑_{i≥2} ⌊\frac{n}{i!}⌋ − ∑_{i≥2} ⌊\frac{n − 1}{i!}⌋ = ∑_{i≥2} (∑_{j=i}^{x−1} \frac{j!}{i!·}(−j) + \frac{x!}{i!})

= ∑_{i≥2} (\frac{x!}{i!} − ∑_{j=i}^{x−1} \frac{j · j!}{i!})

= ∑_{i=2}^{x} (\frac{x!}{i!} − \frac{1}{i!} ∑_{j=1}^{x−1} j · j! + \frac{1}{i!} ∑_{j=1}^{i−1} j · j!)

= ∑_{i=2}^{x} (\frac{x!}{i!} − \frac{x! − 1}{i!} + \frac{i! − 1}{i!})

= ∑_{i=2}^{x} \frac{i!}{i!} = x − 1 = v(n) + 1 − 1 = v(n),

which proves the first part. For the second part, we compute

∑_{i=1}^{n} (∑_{j≥2} ⌊\frac{i}{j!}⌋ − ∑_{j≥2} ⌊\frac{i − 1}{j!}⌋) = ∑_{i=1}^{n} ∑_{j≥2} ⌊\frac{i}{j!}⌋ − ∑_{i=1}^{n} ∑_{j≥2} ⌊\frac{i − 1}{j!}⌋

= ∑_{i=1}^{n} ∑_{j≥2} ⌊\frac{i}{j!}⌋ − ∑_{i=0}^{n−1} ∑_{j≥2} ⌊\frac{i}{j!}⌋

= ∑_{j≥2} ⌊\frac{n}{j!}⌋ .

Thus, we see that

F_{V} (n) = ∏_{i=1}^{n} V (i) = ∏_{i=1}^{n} 2^{v(i)} = 2^{∑_{i=1}^{n} v(i)} = 2^{∑{n \atop i=1}(∑_{j≥2}⌊^{\frac{i}{j!}}⌋−∑_{j≥2}⌊\frac{i−1}{j!}⌋)} = 2∑^{j≥2}^{⌊^{\frac{n}{j!}}⌋}.

Theorem 15. For all natural numbers m and n, we have

\binom{m + n}{n}_{V} = 2^{∑_{i≥1} ϵ_{i}},

where ϵ is the carry sequence for m and n.

Proof. Let n = (n_{1}, n_{2}, …, m_{k})_{!}, m = (m_{1}, m_{2}, …, m_{k})_{!}, and (0, ϵ_{1}, ϵ_{2}, …, ϵ_{k}) be the carry sequence for n and m (appending 0’s if necessary to ensure that the representations are the same length as the carry sequence). First, by Lemmas 14 and 13, we have

F_{V} (ℓ) = 2∑{∞ \atop i=2}^{⌊^{\frac{ℓ}{i!}}⌋} = 2^{∑_{i=2}^{∞} ∑_{j=i}^{∞} ℓ_{j}· \frac{j!}{i!}} .

Thus, by definition we have

\binom{m + n}{n}_{V} = \frac{F_{V} (m + n)}{F_{V} (m) · F_{V} (n)} = 2^{∑_{i≥2} ∑_{j=i}^{∞}((m+n)_{j}−m_{j}−n_{j})· \frac{j!}{i!}}
= 2^{∑_{i≥2} ∑_{j=i}^{∞}(ϵ_{j−1}−ϵ_{j}·(j+1))· \frac{j!}{i!}}
= 2^{∑_{i≥2}(∑_{j=i}^{∞} ϵ_{j−1}· \frac{j!}{i!} −∑_{j=i}^{∞} ϵ_{j}· \frac{(j+1)!}{i!} )}
= 2^{∑_{i≥2}(∑_{j=i}^{∞} ϵ_{j−1}· \frac{j!}{i!} −∑_{j=i+1}^{∞} ϵ_{j−1}· \frac{j!}{i!} )}
= 2^{∑_{i≥2} ϵ_{i−1}· \frac{i!}{i!}}
= 2^{∑_{i≥1} ϵ_{i}},

where the third equality follows from Theorem 5.

The V -binomial coefficients thus determine the sum of carries when adding the factorial base representations of n and m without determining factorial digits of either numbers. We can organize these coefficients into a triangular array, as seen in Figure 4. By considering only the exponents of this triangle, we produce the sum-of-carries triangle pictured in Figure 5.

Figure 4: The V -binomial coefficients up to row 36.

Figure 5: The exponent of 2 from V -binomial coefficients.

4.2 Second analog of Kummer’s theorem

The investigation of analogs of Kummer’s theorem for rational base arithmetic [5] and Zeckendorf arithmetic [1] prompted us to investigate the sequence w given by w(n) = 1 + s_{!}(n − 1) − s_{!}(n). One can check (based on the proof of Lemma 14) that w(n) = T (v(n)) where T (ℓ) = \frac{ℓ·(ℓ+1)}{2} is the sequence of triangular numbers. Again, we define W (n) = 2^{w(n)} and the corresponding W -factorial function; the first few values of these are listed in Table 2.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ w(n) & 0 & 1 & 0 & 1 & 0 & 3 & 0 & 1 & 0 & 1 & 0 \\ W (n) & 1 & 2 & 1 & 2 & 1 & 8 & 1 & 2 & 1 & 2 & 1 \\ F_{W} (n) & 1 & 2 & 2 & 4 & 4 & 32 & 32 & 64 & 64 & 128 & 128 \end{matrix}

\begin{matrix}n & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ w(n) & 3 & 0 & 1 & 0 & 1 & 0 & 3 \\ W (n) & 8 & 1 & 2 & 1 & 2 & 1 & 8 \\ F_{W} (n) & 1024 & 1024 & 2048 & 2048 & 4096 & 4096 & 32768 \end{matrix}

Table 2: Sequences derived from w.

The following lemma allows us to demonstrate the resulting analog of Kummer’s theorem.

Lemma 16. For all natural numbers n, we have F_{W} (n) = 2^{n−s_{!}(n)}.

Proof. This follows from the definitions:

\begin{aligned}F_{W} (n) = ∏_{i=1}^{n} 2^{W (i)} = 2^{∑_{i=1}^{n} 1+s_{!}(i−1)−s_{!}(i)} & = 2^{∑_{i=1}^{n} 1+∑_{i=1}^{n} s_{!}(i−1)−∑_{i=1}^{n} s_{!}(i)} \\ & = 2^{n+∑_{i=0}^{n−1} s_{!}(i)−∑_{i=1}^{n} s_{!}(i)} = 2^{n−s_{!}(n)}, \end{aligned}

since s_{!}(0) = 0.

Theorem 17. For all natural numbers m and n, we have

\binom{m + n}{n}_{W} = 2^{∑_{i≥1} i·ϵ_{i}},

where ϵ is the carry sequence for m and n.

Proof. From the definition we have \binom{m+n}{n}_{W} = \frac{F_{W} (m+n)}{F_{W} (m)·F_{W} (n)}. Then by Lemma 16,

\binom{n}{k}_{W} = \frac{2^{(m+n)−s_{!}(m+n)}}{2^{m−s_{!}(m)} · 2^{n−s_{!}(n)}} = 2^{s_{!}(m)+s_{!}(n)−s_{!}(m+n)} = 2^{∑^{i≥1} i·ϵ_{i}},

where the last equality is due to Theorem 6.

The W -binomial coefficients yield the weighted-sum-of-carries when adding the factorial base representations of n and m. We once again organize these coefficients into a triangular array as seen in Figure 6; the exponents of this triangle are pictured in Figure 7, which we call the weighted-sum-of-carries triangle.

Figure 6: The W-binomial coefficients.

Figure 7: The exponent of 2 from W-binomial coefficients, i.e. the weighted sum-of-carries triangle.

4.3 Third analog of Kummer’s theorem

We finish this section with one final integer sequence whose generalized binomial coefficients contain information about factorial base arithmetic. Let D be the sequence where D(n) is the largest factorial dividing n (see \underline{A055770} in [18]). More precisely, D(n) = (v(n) + 1)!. The sequence D and the D-factorial function are listed in Table 3.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ D(n) & 1 & 2 & 1 & 2 & 1 & 6 & 1 & 2 & 1 & 2 & 1 \\ F_{D}(n) & 1 & 2 & 2 & 4 & 4 & 24 & 24 & 48 & 48 & 96 & 96 \end{matrix}

\begin{matrix}n & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ D(n) & 6 & 1 & 2 & 1 & 2 & 1 & 6 \\ F_{D}(n) & 576 & 576 & 1152 & 1152 & 2304 & 2304 & 13824 \end{matrix}

Table 3: Sequences derived from D.

As in the previous two subsections, we determine information about these sequences to show how they are related to factorial base representations.

Lemma 18. For any natural number n = (n_{1}, n_{2}, …, n_{k})_{!},

D(n) = ∏_{i=1}^{k} i^{⌊^{\frac{n}{i!}}⌋−⌊\frac{n−1}{i!}⌋}.

Proof. First we note that by Lemma 13, we have

∏_{i=1}^{k} i^{⌊^{\frac{n}{i!}}⌋−⌊\frac{n−1}{i!}⌋} = ∏_{i=1}^{k} i^{∑_{j=i}^{k} \frac{j!}{i!} n_{j}−∑_{j=i}^{k} \frac{j!}{i!} (n−1)_{j}} = ∏_{i=1}^{k} i^{∑_{j=i}^{k} \frac{j!}{i!} (n_{j}−(n−1)_{j})}.

Now, as in the proof of Lemma 14, we let x be the largest integer such that x! divides n so that n = (0, 0, …, 0, n_{x}, n_{x+1}, …, n_{k})_{!} and n − 1 = (1, 2, …, x − 1, n_{x} − 1, n_{x+1}, …, n_{k})_{!}, which implies

n_{j} − (n − 1)_{j} = \begin{cases}0 − j, & j < x; \\ n_{x} − (n_{x} − 1) = 1, & j = x; \\ n_{j} − n_{j} = 0, & j > x. \end{cases}

Thus, we have

∏_{i=1}^{k} i^{⌊^{\frac{n}{i!}}⌋−⌊\frac{n−1}{i!}⌋} = ∏_{i=1}^{x} i^{∑_{j=i}^{k} \frac{j!}{i!} (n_{j}−(n−1)_{j})} · ∏_{i=x+1}^{k} i^{∑_{j=i}^{k} \frac{j!}{i!} (n_{j}−(n−1)_{j})}

= ∏_{i=1}^{x} i^{∑_{j=i}^{x−1} \frac{j!}{i!} (−j)+ \frac{x!}{i!}}

= ∏_{i=1}^{x} i^{\frac{x!}{i!} −∑_{j=i}^{x−1} \frac{j·j!}{i!}}

= ∏_{i=1}^{x} i^{\frac{x!}{i!} −∑_{j=1}^{x−1} \frac{j·j!}{i!} +∑_{j=1}^{i−1} \frac{j·j!}{i!}}

= ∏_{i=1}^{x} i^{\frac{x!}{i!} − \frac{x!−1}{i!} + \frac{i!−1}{i!}} = ∏_{i=1}^{x} i = x! = D(n),

where we make use of equation (1) twice.

Lemma 19. For any natural number n = (n_{1}, n_{2}, …, n_{k})_{!} we get

F_{D}(n) = ∏_{i=1}^{k} i^{⌊^{\frac{n}{i!}}⌋}.

Proof. For a natural number i, we know i = (i_{1}, i_{2}, …, i_{k})_{!} where we append 0’s if necessary to ensure i has the same length as the representation for n. Then we use Lemma 18 to see

F_{D}(n) = ∏_{i=1}^{n} D(i) = ∏_{i=1}^{n} ∏_{j=1}^{k} j^{⌊^{\frac{i}{j!}}⌋−⌊\frac{i−1}{j!}⌋} = ∏_{j=1}^{k} ∏_{i=1}^{n} j^{⌊^{\frac{i}{j!}}⌋−⌊\frac{i−1}{j!}⌋}

= ∏_{j=1}^{k} (∏_{i=1}^{n} j^{⌊^{\frac{i}{j!}}⌋} · ∏_{i=1}^{n} j^{−⌊\frac{i−1}{j!}⌋})

= ∏_{j=1}^{k} (∏_{i=1}^{n} j^{⌊^{\frac{i}{j!}}⌋} · ∏_{i=0}^{n−1} j^{−⌊\frac{i}{j!}⌋})

= ∏_{j=1}^{k} (j^{⌊^{\frac{n}{j!}}⌋} · j^{−⌊\frac{0}{j!}⌋}) = ∏_{i=1}^{k} i^{⌊^{\frac{n}{i!}}⌋}.

We can now show the relationship between D-binomial coefficients and carry sequences.

Theorem 20. Let n and m be natural numbers, and let ϵ be the carry sequence for m and n. Then

\binom{m + n}{n}_{D} = ∏_{i≥1} i^{ϵ_{i−1}}.

Proof. Let n = (n_{1}, …, n_{k})_{!}, m = (m_{1}, …, m_{k})_{!} m + n = ((m + n)_{1}, …, (m + n)_{k})_{!} and (0, ϵ_{1}, ϵ_{2}, …, ϵ_{k}) be the carry sequence for n and m (appending 0’s if necessary to ensure that the representations are the same length as the carry sequence). Lemmas 19 and 13 imply

F_{D}(n) = ∏_{i≥1} i^{⌊n/i!⌋} = ∏_{i≥1} i^{∑_{j=i}^{∞} n_{j}· \frac{j!}{i!}} .

Thus, we have

\binom{m + n}{n}_{D} = \frac{F_{D}(m + n)}{F_{D}(m) · F_{D}(n)} = ∏_{i≥1} i^{∑_{j≥i}(m+n)_{j}· \frac{j!}{i!} −∑_{j≥i} m_{j}· \frac{j!}{i!} −∑_{j≥i} n_{j}· \frac{j!}{i!}}

= ∏_{i≥1} i^{∑_{j≥i}((m+n)_{j}−m_{j}−n_{j})· \frac{j!}{i!}}

= ∏_{i≥1} i^{∑_{j≥i}(ϵ_{j−1}−ϵ_{j}·(j+1))· \frac{j!}{i!}}

= ∏_{i≥1} i^{ϵ_{i−1}· \frac{i!}{i!}} = ∏_{i≥1} i^{ϵ_{i−1}}.

One final time we include the triangular array of D-binomial coefficients in Figure 8.

Figure 8: The D-binomial coefficients

5 Digital dominance

P. de Castro et al. [3] connect divisibility of binomial coefficients by prime powers, p^{α}, and base-p arithmetic to the digital dominance order on the natural numbers (given in terms of the base-p representations). We extend their results to factorial base representations by connecting the generalized binomial coefficients of the previous section and hyperfactorial partitions to the digital dominance order determined by factorial base representations.

Given two natural numbers, m = (m_{1}, m_{2}, …, m_{k})_{!} and n = (n_{1}, n_{2}, …, n_{k})_{!} (appending zeroes if necessary), we say m digitally dominates n in factorial base if n_{i} ≤ m_{i} for all i ≤ k. In this case, we write n ≪_{!} m. This relation forms a ranked partial order (in fact a lattice) on the set of natural numbers with rank function given by the factorial base sum-of-digits function. We call this poset D_{!} = (ℕ, ≪_{!}), and for any positive integer n, we let D_{!}(n) be the restriction of this poset to the finite set {0, 1, 2, …, n}. For instance, Figure 9 shows the Hasse diagram for D_{!}(23).

Figure 9: The Hasse diagram of ≪_{!} up to n = 23.

We can also visualize the dominance order as a triangular array where we shade entry ℓ in row n (starting with row 0) if ℓ ≪_{!} n; we call an array of this form with m dots on the base A_{m}. For instance, the array A_{120} is pictured in Figure 10.

Figure 10: Triangular array representing factorial base digital dominance up to n = 120.

The blocks of unshaded subtriangles in these arrays consist of T_{i!−1} dots, where again we let T_{k} represent the kth triangular number. For instance, Figure 10 has unshaded triangles with T_{1}, T_{5}, and T_{23} dots. We also note that we can iteratively build A_{n!} by stacking, in a triangular fashion, T_{n} copies of A_{(n−1)!}.

One of the apparent symmetries of Figure 10 is explained by the following lemma.

Lemma 21. Let n and ℓ be natural numbers. If ℓ ≪_{!} n, then n − ℓ ≪_{!} n.

Proof. Assume ℓ ≪_{!} n. Then n − ℓ = ∑_{i=1}^{k}(n_{i} · i!) − ∑_{i=1}^{k}(ℓ_{i} · i!) = ∑_{i=1}^{k}(n_{i} − ℓ_{i}) · i!. Since ℓ ≪_{!} n, we know ℓ_{i} ≤ n_{i} for all i and so, and 0 ≤ n_{i} − ℓ_{i} ≤ n_{i} ≤ i for all i. Therefore, for each i we se (n − ℓ)_{i} = n_{i} − ℓ_{i}, so that (n − ℓ)_{i} ≤ n_{i}, which implies n − ℓ ≪_{!} n.

The interpretation of this triangular array in terms of the digital dominance order demonstrates that the number of shaded entries in row n = (n_{1}, n_{2}, …, n_{k})_{!} of the infinite array is given by ∏_{i=1}^{k}(n_{i} + 1) since n_{i} + 1 counts the number of digits less than or equal to n_{i}. The number of shaded entries in row n is thus given by sequence \underline{A227154}.

Moreover, as we mentioned, the full array of generalized binomial coefficients has connections to the triangular arrays of generalized binomial coefficients from Section 4 just as Pascal’s triangle is related to the Sierpiński triangle.

Theorem 22. Let m and n be natural numbers. Then n ≪_{!} m + n if and only if the carry sequence for n and m is the zero sequence, ϵ = (0, …, 0).

Proof. First, suppose that n ≪_{!} m + n so that n_{i} ≤ (m + n)_{i} for all i; by the proof of Lemma 21, we know that, for each i, m_{i} = (m + n)_{i} − n_{i} so that (m + n)_{i} = m_{i} + n_{i}. thus, since ϵ_{0} = 0, we can use Theorem 5 inductively to show that ϵ_{i} = 0 for all i.

Conversely, suppose each entry in the carry sequence is 0, and let i ≤ k. Again, Theorem 5 implies that (m + n)_{i} = m_{i} + n_{i} + ϵ_{i−1} − ϵ_{i} · (i + 1) = m_{i} + n_{i} ≥ n_{i}. Therefore, by the definition, n ≪_{!} m + n.

Thus the binomial coefficients \binom{m+n}{n}_{V}, \binom{m+n}{n}_{W}, and \binom{m+n}{n}_{D}, pictured in Figures 4, 6 and 8 respectively, are each 1 if and only if n ≪_{!} (m + n). In particular, if we reduce either the array of V -binomial coefficients or the array W -binomial coefficients modulo 2, we obtain the factorial digital dominance triangular array. It would be interesting to investigate the array of D-binomial coefficients modulo different integers.

We can also draw a deeper connection between the digital dominance order, hyperfactorial partitions, and the W -binomial coefficients. Recall from Section 3 that given positive integers x = (x_{1}, x_{2}, …, x_{k})_{!} and y = (y_{1}, y_{2}, …, y_{k})_{!}, we let x⊞_{!}y = [x_{1}+y_{1}, x_{2}+y_{2}, …, x_{k}+y_{k}]_{!}, which is a hyperfactorial partition of n = x + y. Moreover, for an integer n, every hyperfactorial partition h = [h_{1}, h_{2}, …, h_{k}]_{!} of n is of the form x ⊞_{!} y where x = (x_{1}, x_{2}, …, x_{k})_{!} and y = (y_{1}, y_{2}, …, y_{k})_{!} with x_{i} := min{h_{i}, i} and y_{i} := h_{i} − x_{i}. To verify this, we note that for each i we have 0 ≤ x_{i} ≤ i so that x = (x_{1}, x_{2}, …, x_{k})_{!} is the factorial base representation for x. Now, if y_{i} > i, then h_{i} − x_{i} > i so that h_{i} > x_{i} + i, which implies that x_{i} = i and that h_{i} > 2i. This contradicts the fact that h is a hyperfactorial and so 0 ≤ y_{i} ≤ i for all i, making y = (y_{1}, y_{2}, …, y_{k})_{!} the factorial base representation. By definition x + y = n.

Now, if n = (n_{1}, n_{2}, …, n_{k})_{!} is a positive integer and h = [h_{1}, h_{2}, …, h_{k}]_{!} is a hyperfactorial partition of n, then we define the weight of h to be

wt(h) := ∑_{i=1}^{k} h_{i} − n_{i}.

Theorem 17 can be restated in terms of the weight of a hyperfactorial partition.

Theorem 23. Let m and n both be natural numbers. The exponent of \binom{m+n}{n}_{W} is wt(m⊞_{!}n).

Proof. First, we let n = (n_{1}, n_{2}, …, n_{k})_{!}, m = (m_{1}, m_{2}, …, m_{k})_{!}, and m + n = ((m + n)_{1}, (m + n)_{2}, …, (m + n)_{k})_{!} (with zeroes appended to ensure the same length). Then m ⊞_{!} n = [n_{1} + m_{1}, n_{2} + m_{2} …, n_{k} + m_{k}]_{!} so that

\begin{aligned}wt(m ⊞_{!} n) = ∑_{i=1}^{k}(m_{i} + n_{i}) − (m + n)_{i} = ∑_{i=1}^{k} ϵ_{i} · (i + 1) − ϵ_{i−1} & = ∑_{i=1}^{k} ϵ_{i} · (i + 1) − ∑_{i=1}^{k} ϵ_{i−1} \\ & = ∑_{i=1}^{k} ϵ_{i} · i \end{aligned}

by Theorem 5 and the fact that ϵ_{0} = ϵ_{k} = 0 when ϵ is the carry sequence for n and m.

Now, for a positive integer n and a hyperfactorial partition h of n, we define the set I_{!}(h) := {x ∈ ℕ | x ⊞_{!} (n − x) = h}. If we let H(n) be the set of hyperfactorial partitions of n, then the set {I_{!}(h) | h ∈ H(n)} forms a set partition of the set {0, 1, 2, …, n}, and we can determine precisely when an element x is in I_{!}(h).

Lemma 24. Let n be a positive integer and h = [h_{1}, h_{2}, …, h_{k}]_{!} be a hyperfactorial partition of n. Then x = (x_{1}, …, x_{k})_{!} (appending zeroes if necessary) satisfies x ∈ I_{!}(h) if and only if

h_{i} − min{h_{i}, i} ≤ x_{i} ≤ min{h_{i}, i}

for all 1 ≤ i ≤ k.

Proof. Suppose that x ∈ I_{!}(h) so that x ⊞_{!} (n − x) = h where n − x = (y_{1}, y_{2}, …, y_{k})_{!}. Note that y_{i} ≥ 0 so that h_{i} = x_{i} + y_{i} implies x_{i} ≤ h_{i}; since x_{i} ≤ i (from the definition of factorial base representations), we have x_{i} ≤ min{h_{i}, i}. By symmetry, we have y_{i} ≤ min{h_{i}, i}, and so x_{i} = h_{i} − y_{i} ≥ h_{i} − min{h_{i}, i} as required.

Next, assume that h_{i} − min{h_{i}, i} ≤ x_{i} ≤ min{h_{i}, i} for all 1 ≤ i ≤ k. For each i we define w_{i} = h_{i} − x_{i}, and since x_{i} ≤ h_{i} we know w_{i} ≥ 0. Moreover, h_{i} − min{h_{i}, i} ≤ x_{i} so that w_{i} ≤ min{h_{i}, i} ≤ i. Thus (w_{1}, w_{2}, …, w_{k})_{!} is a factorial base representation; let w = (w_{1}, w_{2}, …, w_{k})_{!}. By construction x_{i} + w + i = h_{i} so that x + w = n and x ⊞_{!} w = h. Hence x ∈ I_{!}(h).

According to Lemma 24, if x ≪_{!} y ≪_{!} z and x, z ∈ I_{!}(h), then y, n − y ∈ I_{!}(h) as well, where h is a hyperfactorial for n. Furthermore, I_{!}(h) has both a minimal element, m := (m_{1}, m_{2}, …, m_{k})_{!} where m_{i} = h_{i}−min{h_{i}, i}, and maximal element, M := (M_{1}, M_{2}, …, M_{k})_{!} where M_{i} = min{h_{i}, i}, under digital dominance, thus implying the following theorem.

Theorem 25. Let n be a natural number and h be a hyperfactorial partition of n. Then (I_{!}(h), ≪_{!}) is an interval in D_{!}(n) and the set of intervals {I_{!}(h) | h ∈ H(n)} forms a set partition of D_{!}(n).

Figure 11: The partially ordered set D_{!}(14) color-coded according to the four hyperfactorial partitions of 14. Note that all pairs (x, y) with x + y = 14 are colored the same and that each monochromatic subset forms a subinterval.

For instance, Figure 11 illustrates D_{!}(14) as a subset of D_{!}(23). Each set of colored nodes represents the set I_{!}(h) for some h in set of hyperfactorial partitions of 14, H(14) = {[0, 1, 2]_{!}, [2, 0, 2]_{!}, [2, 3, 1]_{!}, [0, 4, 1]}. Note that the weight of the associated hyperbinary partition can be obtained by adding the factorial base sum-of-digits of the maximal and minimal elements of the corresponding interval and subtracting the sum of digits of n. Figure 12 shows the exponents of triangular array of W -binomial coefficients; the numbers in row 14 correspond to the weights of the associated hyperfactorial partition and are color-coded to show how we can visualize, in some sense, the poset decomposition in Figure 11 in the array of W -binomial coefficients.

Figure 12: The array of exponents of W -binomial coefficients up to row 14 with entry ℓ in row 14 color-coded (with colors matching Figure 11) by weight of the hyperfactorial partition ℓ ⊞_{!} (14 − ℓ).

6 Acknowledgments

This work was performed as part of the 2017 SUMmER REU at Seattle University funded by NSF grant DMS-1460537. We would like to thank Allison Henrich and Steven Klee for their organization of the REU and their guidance during the summer.

References

[1] T. Ball, R. Chaiser, D. Dustin, T. Edgar, and P. Lagarde, Some combinatorics from Zeckendorf representations, Involve 12 (2019), 1241–1260.

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

[3] P. de Castro, D. Domini, T. Edgar, D. M. Johnson, S. Klee, and R. Sundaresan, Counting binomial coefficients divisible by a prime power. Amer. Math. Monthly 125 (2018), 531–540.

[4] T. Edgar, Proof without words: factorial sums. Math. Mag. 89 (2016), 338–339.

[5] T. Edgar, H. Olafson, and J. Van Alstine, The combinatorics of rational base representations, preprint, 2014. Available at https://community.plu.edu/~edgartj/

preprints/basepqarithmetic.pdf.

[6] T. Edgar and M. Z. Spivey, Multiplicative functions generalized binomial coefficients, and generalized Catalan numbers. J. Integer Sequences 19 (2016), Article 16.1.6.

[7] S. Even, Algorithmic Combinatorics, Macmillan, 1973.

[8] A. S. Fraenkel, Systems of numeration, Amer. Math. Monthly 92 (1985), 105–114.

[9] D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison-Wesley, 1998.

[10] D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, 1998.

[11] 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.

[12] C. A. Laisant, Sur la numération factorielle, application aux permutations. Bull. Soc. Math. France 16 (1888), 176–183.

[13] D. H. Lehmer, The machine tools of combinatorics, in Applied Combinatorial Mathematics, Wiley, 1964, pp. 5–31.

[14] H. W. Lenstra, Profinite Fibonacci numbers, Nieuw Archief voor Wiskunde 6 (2005), 297–300.

[15] J. Leroy, M. Rigo, and M. Stipulanti, Behavior of digital sequences through exotic numeration systems, Electron. J. Combin. 24 (2017), Paper 1.44.

[16] J. Leroy, M. Rigo, and M. Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Math. 340 (2017), 862–881.

[17] J. Leroy, M. Rigo, and M. Stipulanti, Generalized Pascal triangle for binomial coefficients of words, Adv. Appl. Math. 80 (2016), 24–27.

[18] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2019. Available

at https://oeis.org.

2010 Mathematics Subject Classification: Primary 11Y55; Secondary 05A10, 06A06, 05A17. Keywords: factorial base representations, sum of digits, generalized binomial coefficient, Kummer’s theorem, digital dominance order.

(Concerned with sequences \underline{A034968}, \underline{A055770}, \underline{A227154}, \underline{A230403}, and \underline{A331128}.) Received March 28 2019; revised version received December 29 2019; January 10 2020. Published in Journal of Integer Sequences, February 23 2020. Return to Journal of Integer Sequences home page.