Multiplicative Functions Generalized Binomial Coefficients, and

Generalized Catalan Numbers

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

                    edgartj@plu.edu

Michael Z. Spivey Department of Mathematics and Computer Science University of Puget Sound Tacoma, WA 98416-1043 USA

                mspivey@pugetsound.edu

Abstract

We investigate generalized binomial coefficients of multiplicative functions. We provide a formula for these coefficients and use this formula to prove that the coefficients are always integral if the function is also a divisible function. Furthermore, we prove that multiplicative and divisible functions have integral generalized Fuss-Catalan numbers. Along the way, we include some results about specific multiplicative functions such as gcd_{k} and ϕ. We finish by connecting these results to a classical result due to Ward.

1 Introduction

Let ℕ be the set of positive integers. Then, given a function f : ℕ → ℕ, define for nonnegative integers n and m the generalized binomial coefficient \binom{n+m}{n}_{f} via

\binom{n + m}{n}_{f} = \frac{∏_{i=1}^{n+m} f(i)}{(∏_{i=1}^{n} f(i)) (∏_{i=1}^{m} f(i))},

where an empty product is defined to be 1.

What conditions on f result in the generalized binomial coefficient \binom{n+m}{n}_{f} taking on only integer values? Obviously the usual binomial coefficients, where f(n) = n, are integers. Several authors have investigated this question for other functions f. Knuth and Wilf [5] have proved that the generalized binomial coefficients are integers when the function f is strongly divisible; i.e., when gcd(f(m), f(n)) = f(gcd(m, n)) for all m, n. This includes the Fibonacci sequence, as it is strongly divisible. Other authors (see, for example, Carmichael [2]) have proved that the generalized binomial coefficients are integers for generalized Fibonacci sequences defined by f(n + 2) = af(n + 1) + bf(n), with a, b integers and f(1) = f(2) = 1. Edgar [4] has also proved that Euler’s ϕ-function, Jordan’s generalization of it, and Dedekind’s ψ-function as choices for f give rise to integer generalized binomial coefficients. In fact, it turns out that these three examples can be shown to have integer generalized binomial coefficients as a consequence of a result by Ward [7].

A related result for the usual binomial coefficients is Kummer’s theorem, which describes their prime factorization. More specifically, Kummer’s theorem states that the exponent of the largest power of a prime p that divides \binom{n+m}{n} is the number of carries when n and m are added in base p. Knuth and Wilf [5] generalize Kummer’s theorem and give an analog of it for a certain class of strongly divisible functions.

In this paper we investigate generalized binomial coefficients formed from multiplicative functions; i.e., functions f in which f(1) = 1 and f(mn) = f(m)f(n) when m and n are relatively prime.

Our main theorem (Theorem 3) gives a formula for \binom{n+m}{n}_{f} when f is multiplicative. This result has the following consequences.

1. The formula is in terms of i) the values of f at prime powers and ii) the carries when n and m are added in prime bases. The formula thus generalizes Kummer’s theorem in a different way than that of Knuth and Wilf.

2. While multiplicative functions in general do not give rise to integral generalized binomial coefficients, our formula allows us to prove that \binom{n+m}{n}_{f} is an integer when f is both multiplicative and divisible, i.e., when m|n implies f(m)|f(n), but not necessarily strongly divisible. This category includes completely multiplicative functions. In Section 5, we prove that this result is a special case of a result of Ward’s. However, this is not obvious: Ward’s result does not apply to multiplicative functions alone, nor to divisible functions alone, but it does turn out to apply to functions that are both multiplicative and divisible.

3. Let gcd_{k}(n) denote the function that, for fixed k, yields the greatest common divisor of n and k. We obtain a Kummer-like result that the highest power of a prime p that divides \binom{n+m}{n}_{gcd_{k}} is the number of carries in the base p sum of n and m that occur before the ν_{p}(k) position, where ν_{p}(k) is the exponent of the highest power of p that divides k.

4. The formula gives a necessary and sufficient criterion for determining the values of n and m yielding integral generalized binomial coefficients for all multiplicative functions.

5. We obtain an explicit formula for the generalized Fuss-Catalan number, given by A_{f}(n, q, r) = \frac{f(r)}{f(nq+r)} \binom{nq+r}{n}_{f}, in terms of the values of f at prime powers and certain carries in prime bases, for f multiplicative. If f is also divisible, this implies that the generalized Fuss-Catalan number is an integer for all values of n, q, and r. Thus the generalized Catalan number, \frac{1}{f(n+1)} \binom{2n}{n}_{f}, is also always an integer when f is multiplicative and divisible. In addition, as Euler’s ϕ-function is both multiplicative and divisible, we obtain a positive answer to Edgar’s question [4] as to whether \frac{1}{ϕ(n+1)} \binom{2n}{n}_{ϕ} is always an integer.

In the final section, we investigate the slightly more general formulation due to Ward and provide formulas for the associated Fuss-Catalan numbers as discussed in (5) above. We obtain alternate formulas for generalized binomial coefficients that can be shown to be equivalent to the others we present here. However, the general results require all base-b representations of natural numbers whereas the multiplicative and divisible functions only require prime base representations.

We now define notation that will be used throughout. Let n, m and b be nonnegative integers. Then n has a unique base-b representation of the form n = n_{0} + n_{1}b + ⋯ + n_{k}b^{k}. We express this more compactly as (n_{0}, n_{1}, …, n_{k})_{b}. Similarly, m has a unique base-b representation m = m_{0} + m_{1}b + ⋯ + m_{l}b^{l} that we express as (m_{0}, m_{1}, …, m_{l})_{b}.

Define the (b, n, m)-carry sequence, ϵ^{b,n,m}, recursively via

ϵ_{i}^{b,n,m} = ⌊\frac{n_{i} + m_{i} + ϵ_{i−1}}{b} ⌋ ,

where we take ϵ_{−1}^{b,n,m} = 0. (When the context is understood, we omit the superscripts.) The base-b representation of n + m is then given by

(n + m)_{i} = n_{i} + m_{i} + ϵ_{i−1} − bϵ_{i}.  (1)

Since n_{i} < b and m_{i} < b, the definition of ϵ_{i}^{b,n,m} implies that ϵ_{i}^{b,n,m} is either 0 or 1 for each i. We say there is a carry in the ith position of the base-b sum of m and n if ϵ_{i}^{b,n,m} = 1.

Let κ_{b}(n, m) = ∑_{i} ϵ_{i}^{p,n,m}, the sum of the carries in the base-b sum of n and m.

When p is prime, we let ν_{p}(n) denote the exponent of the highest power of p that divides n.

Finally, let [P] denote the Iverson bracket for the statement P:

[P] = \begin{cases}1, & if P is true; \\ 0, & otherwise. \end{cases}

2 A formula for \binom{n+m}{n}_{f} when f is multiplicative

Before we prove our main result, an expression for \binom{n+m}{n}_{f} when f is multiplicative, we prove a couple of lemmas we will need. The first gives two equivalent expressions for the existence of a carry in the ith position when m and n are added in base p with p prime.

Lemma 1. Let p be prime and n and m be two nonnegative integers.

ϵ_{r}^{p,n,m} = [(n + m) mod p^{r+1} < n mod p^{r+1}]

= ⌊\frac{n + m}{p^{r+1}}⌋ − ⌊\frac{n}{p^{r+1}} ⌋ − ⌊\frac{m}{p^{r+1}} ⌋ .

Proof. For the first equality, we have, by (1),

(n + m) mod p^{r+1} − n mod p^{r+1} = ∑_{i=0}^{r} ((n + m)_{i}p^{i} − n_{i}p^{i})

= ∑_{i=0}^{r} (m_{i}p^{i} + p^{i}ϵ_{i−1} − p^{i+1}ϵ_{i})

= ∑_{i=0}^{r} m_{i}p^{i} − p^{r+1}ϵ_{r}

= m mod p^{r+1} − p^{r+1}ϵ_{r}.

This last expression is negative precisely when ϵ_{r} = 1.

For the second equality, the proof is similar. Let ((n + m)_{0}, (n + m)_{1}, …, (n + m)_{t_{p}})_{p} be the base-p representation of n + m. We have, again by (1),

⌊\frac{n + m}{p^{r+1}}⌋ − ⌊\frac{n}{p^{r+1}} ⌋ − ⌊\frac{m}{p^{r+1}} ⌋ = ∑_{i=r+1}^{t_{p}} ((n + m)_{i}p^{i−(r+1)} − n_{i}p^{i−(r+1)} − m_{i}p^{i−(r+1)})

= ∑_{i=r+1}^{t_{p}} (p^{i−(r+1)}ϵ_{i−1} − p^{i−(r+1)+1}ϵ_{i})

= ϵ_{r} − p^{t_{p}−r}ϵ_{t_{p}}

= ϵ_{r}, as ϵ_{t_{p}} = 0 (otherwise, n + m would have, in its base-p representation, a digit in the t_{p} + 1 position).

The second lemma we need is the following.

Lemma 2. There are ⌊n/p^{r}⌋ − ⌊n/p^{r+1}⌋ elements of {1, 2, …, n} for which p^{r} is the highest power of p occurring in that element’s prime factorization.

Proof. The number of elements of {1, 2, …, n} for which p^{r} is the highest power of p occurring in that element’s prime factorization is the number of integers in {1, 2, … n} that are divisible by p^{r} but not by p^{r+1}. This is exactly ⌊n/p^{r}⌋ − ⌊n/p^{r+1}⌋.

With Lemmas 1 and 2 in hand we are ready to prove our main result.

Theorem 3. Let f : ℕ → ℕ be a multiplicative function. Then

\binom{n + m}{n}_{f} = ∏_{p} (∏_{i≥1} f(p^{i})^{ϵ_{i−1}^{p}−ϵ_{i}^{p}})

= ∏_{p} (∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p}}) .

Proof. First, we have, since f is multiplicative,

∏_{k=1}^{n} f(k) = ∏_{k=1}^{n} f (∏_{p|k} p^{ν_{p}(k)}) = ∏_{k=1}^{n} (∏_{p|k} f(p^{ν_{p}(k)})) .

Swapping the order of the products and using Lemma 2 to count the number of times p^{i} occurs as the highest power, we obtain

∏_{k=1}^{n} f(k) = ∏_{k=1}^{n} (∏_{p|k} f(p^{ν_{p}(k)})) = ∏_{p} (∏_{i≥1} f(p^{i})^{⌊n/p^{i}⌋−⌊n/p^{i+1}⌋}) .

Therefore,

\binom{n + m}{n}_{f} = ∏_{p} (∏_{i≥1} f(p^{i})^{⌊(n+m)/p^{i}⌋−⌊n/p^{i}⌋−⌊m/p^{i}⌋−(⌊(n+m)/p^{i+1}⌋−⌊n/p^{i+1}⌋−⌊(m/p^{i+1}⌋)})

= ∏_{p} (∏_{i≥1} f(p^{i})^{ϵ_{i−1}^{p}−ϵ_{i}^{p}}) ,

where the second equality follows from Lemma 1.

In addition, ϵ_{i}^{p} occurs twice in the inner product of this expression: once as the power on f(p^{i+1}) and once as the negative power on f(p^{i}). Thus we also have

\binom{n + m}{n}_{f} = ∏_{p} (∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p}}) .

3 Some integrality conditions for \binom{n+m}{n}_{f} when f is multiplicative

In this section we discuss some conditions on a multiplicative function f that imply \binom{n+m}{n}_{f} is an integer for all values of n and m. We also give a condition on n and m under which \binom{n+m}{n}_{f} is an integer for all multiplicative functions f.

Our first condition is a straightforward consequence of Theorem 3.

Corollary 4. If f : ℕ → ℕ is multiplicative and f(p^{r})|f(p^{r+1}) for all primes p and nonnegative integers r then \binom{n+m}{n}_{f} is an integer for all m, n. In this case we have

\binom{n + m}{n}_{f} = ∏_{p≤n+m} (∏_{i≥0} g_{p}(i)^{ϵ_{i}^{p}}) ,

where g_{p}(r) = f(p^{r+1})/f(p^{r}).

Our second result shows that, for a multiplicative function, f, the condition on f in Corollary 4 is equivalent to f being divisible.

Theorem 5. Let f : ℕ → ℕ be a multiplicative function. Then f satisfies f(p^{r})|f(p^{r+1}) for all primes p and nonnegative integers r iff f is divisible.

Proof. First, suppose f satisfies f(p^{r})|f(p^{r+1}) for all p and r. This implies that if s < r then f(p^{s})|f(p^{r}). Suppose m|n. We have that f(m) = ∏_{p|m} f(p^{ν_{p}(m)}) and f(n) = ∏_{p|n} f(p^{ν_{p}(n)}). For any prime p, the fact that m|n implies that p^{ν_{p}(m)}|p^{ν_{p}(n)}, and so ν_{p}(m) ≤ ν_{p}(n). Thus f(p^{ν_{p}(m)})|f(p^{ν_{p}(n)}), and so f(m)|f(n). Therefore, f is a divisible function.

Next, suppose f(m)|f(n) for all m and n such that m|n. Let m = p^{r} and n = p^{r+1}. Then f(p^{r})|f(p^{r+1}).

Theorem 5 allows us to express Corollary 4 in a more compact form.

Corollary 6. If f : ℕ → ℕ is multiplicative and divisible, then \binom{n+m}{n}_{f} is an integer for all m, n.

In Appendix A, we provide a list of functions (sequences) that are both multiplicative and divisible.

We look at two particularly important functions from this list: Euler’s totient function and the gcd_{k}(n) function. The fact that the totienomial coefficient \binom{n+m}{n}_{ϕ} is an integer was proved by Edgar [4]; this also follows from the main theorem in Ward [7]. With Corollary 4, we obtain this result plus the following formula.

Corollary 7. The totienomial coefficient \binom{n+m}{n}_{ϕ} is an integer for all n, m. Moreover,

\binom{n + m}{n}_{ϕ} = ∏_{p≤n+m}(p − 1)^{ϵ_{0}^{p}}p^{κ_{p}(n,m)−ϵ_{0}^{p}}.

Proof. It is well-known that ϕ is multiplicative with ϕ(p^{r}) = p^{r−1}(p − 1). Thus

\frac{ϕ(p^{r+1})}{ϕ(p^{r})} = \begin{cases}p − 1, & r = 0; \\ p, & r ≥ 1. \end{cases}

The result then follows from Corollary 4.

Using Corollary 4, we get a Kummer-like theorem for the gcd_{k} function, where gcd_{k}(n) is, for fixed k, the greatest common divisor of k and n.

Corollary 8. We have that \binom{n+m}{n}_{gcd_{k}} is an integer for all n, m. Moreover, the exponent of the largest power of a prime p that divides \binom{n+m}{n}_{gcd_{k}} is the number of carries in the base p sum of n and m that occur before the ν_{p}(k) position; i.e.,

\binom{n + m}{n}_{gcd_{k}} = ∏_{p} ( ∏_{i=0}^{ν_{p}(k)−1} p^{ϵ_{i}^{p}} ) .

Proof. We have that gcd_{k}(p^{r}q^{s}) = p^{min{r,ν_{p}(k)}}q^{min{s,ν_{q}(k)}} = gcd_{k}(p^{r}) gcd_{k}(q^{s}). It follows that gcd_{k}(n) is multiplicative.

In addition,

\frac{gcd_{k}(p^{r+1})}{gcd_{k}(p^{r})} = \frac{p^{min\{r+1,ν_{p}(k)\}}}{p^{min\{r,ν_{p}(k)\}}} = \begin{cases}p, & r < ν_{p}(k); \\ 1, & r ≥ ν_{p}(k). \end{cases}

The result then follows from Corollary 4.

An important class of multiplicative functions that are divisible is the class of completely multiplicative functions, which are functions satisfying f(mn) = f(m)f(n) for all m and n.

Corollary 9. If f : ℕ → ℕ is completely multiplicative, then \binom{n+m}{n}_{f} is an integer for all n, m.

Proof. If f is completely multiplicative, then f(p^{r+1})/f(p^{r}) = (f(p))^{r+1}/(f(p))^{r} = f(p). By Corollary 4, then, \binom{n+m}{n}_{f} is an integer for all m, n, with

\binom{n + m}{n}_{f} = ∏_{p≤n+m} f(p)^{κ_{p}(n,m)}.

Some functions that are completely multiplicative include the identity function and sequence \underline{A003958} in the On-Line Encyclopedia of Integer Sequences (OEIS) [6]. In particular, if we let f(n) = n in Corollary 9, then we quickly obtain Kummer’s theorem.

Corollary 10 (Kummer). For any n, m ∈ ℕ, the exponent of the largest power of p dividing \binom{n+m}{n} is the number of carries occurring in the base-p sum of n and m; i.e.,

ν_{p} (\binom{n + m}{n}) = κ_{p}(n, m).

Proof. This statement is exactly the statement given in Corollary 9 since f(p) = p for all p.

Corollary 11. The totienomial coefficients and classical binomial coefficients are related by the following equation:

\binom{n + m}{n}_{ϕ} = \binom{n + m}{n} · ∏_{p≤n+m} (\frac{p − 1}{p})^{ϵ_{0}^{p,n,m}} .

Proof. Combining Corollary 10 with Corollary 7 gives this result.

The results thus far in this section provide conditions such that, given f, \binom{n+m}{n}_{f} is an integer for all values of n and m. Our next result describes a necessary and sufficient condition such that, given n and m, \binom{n+m}{n}_{f} is an integer for all multiplicative functions f.

Corollary 12. Let n and m be nonnegative integers. Then \binom{n+m}{n}_{f} is an integer for all multiplicative functions f : ℕ → ℕ if and only if for all p ≤ n + m there exists an s_{p} ≥ 0 such that ϵ_{i}^{p} = 1 for all i < s_{p} and ϵ_{i}^{p} = 0 for all i ≥ s_{p}.

Proof. We prove the contrapositive of the statement. If \binom{n+m}{n}_{f} is not an integer, then Theorem 3 implies that there must be some prime p and some i ≥ 1 such that ϵ_{i−1}^{p} = 0 but ϵ_{i}^{p} = 1. This is precisely the situation ruled out by the condition in the corollary.

Now, suppose there exists some prime p and some i such that ϵ_{i−1}^{p} = 0 and ϵ_{i}^{p} = 1. Since multiplicative functions are determined by their values at prime powers, let f be the multiplicative function defined, for primes q, by

f(q^{j}) = \begin{cases}2, & q = p, j = i; \\ 1, & q ≠ p or j ≠ i. \end{cases}

By Theorem 3, \binom{n+m}{n}_{f} = 1/2.

Figure 1 contains a graph of the first 90 rows (starting at row 0) of a triangular array. The row n + m, column n entries that are shaded are those such that \binom{n+m}{n}_{f} is an integer for all multiplicative functions f (using the condition from Corollary 12). These entries are more concentrated on the sides of the triangle, which is not surprising, but there are some entries close to the middle of the triangle even fairly far down.

Figure 1: Triangle of values of n and m such that \binom{n+m}{n}_{f} is always an integer when f is multiplicative.

Looking carefully at this triangle, the following are apparent.

Corollary 13. Let f be a multiplicative function and n be a nonnegative integer. Then

1. \binom{n}{0}_{f} and \binom{n}{1}_{f} are always integers.

2. \binom{n}{2}_{f} is an integer if and only if n ≡ 2 (mod 4) or n ≡ 3 (mod 4).

Proof. Part 1 is immediate from the definition and the facts that the empty product is 1 and f(1) = 1 for multiplicative functions. For part 2, we note that if n is equivalent to 2 or 3 mod 4 then n = (0, 1, … n_{k})_{2} or n = (1, 1, …, n_{k})_{2} and so n − 2 = (0, 0, …, n_{k})_{2} or n − 2 = (1, 0, … n_{k})_{2}. In either case, ϵ_{i}^{2,n−2,2} = 0 for all i. Now, for any prime p > 2 we have 2 = (2)_{p}; consequently, for i > 0, we see that ϵ_{i}^{p,n−2,2} = 1 only if ϵ_{i−1}^{p,n−2,2} = 1. Conversely, if n is equivalent to 0 or 1 mod 4, then (n − 2)_{2} = (0, 1, …, n_{k})_{2} or (n − 2)_{2} = (1, 1, …, n_{k})_{2}. As such, ϵ_{0}^{2,n−2,2} = 0 and ϵ_{1}^{2,n−2,2} = 1. The result follows by Corollary 12.

4 Generalized Catalan and Fuss-Catalan numbers when f is multiplicative

The Fuss-Catalan number A(n, q, r) is given by A(n, q, r) = \frac{r}{nq+r} \binom{nq+r}{n}. When q = 2 and r = 1, we have A(n, 2, 1) = \frac{1}{2n+1} \binom{2n+1}{n} = \frac{1}{n+1} \binom{2n}{n} = C(n), the usual nth Catalan number. (Here we use the absorption identity for the binomial coefficients.)

For a function f : ℕ → ℕ and n, q, r ≥ 0, we define the f-Fuss-Catalan number A_{f}(n, q, r) via

A_{f}(n, q, r) = \frac{f(r)}{f(nq + r)}\binom{nq + r}{n}_{f}.

In this section we find a formula for A_{f}(n, q, r), when f is multiplicative, analogous to Theorem 3. We then use this formula to obtain a Kummer-like theorem for Fuss-Catalan numbers. We also prove that when f is multiplicative and divisible, A_{f}(n, q, r) is an integer for all n ≥ 0. In addition, we give the versions of all of these results for the usual Catalan numbers. Since Euler’s ϕ-function is both multiplicative and divisible, we also answer in the affirmative a question of Edgar [4] as to whether C_{ϕ}(n) is an integer for all n ≥ 0.

Theorem 14. If f : ℕ → ℕ is multiplicative, then the f-Fuss-Catalan number given by

A_{f}(n, q, r) = \frac{f(r)}{f(nq + r)}\binom{nq + r}{n}_{f} satisifies

A_{f}(n, q, r) = A(n)B(n)D(n),

where

\begin{aligned}A(n) & = ∏_{p|n,ν_{p}(nq)≥ν_{p}(r)} (∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n,n(q−1)+r}} ) , \\ B(n) & = ∏_{p|n,ν_{p}(nq)<ν_{p}(r)} (\frac{f(p^{ν_{p}(r)})}{f(p^{ν_{p}(nq)})} ∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n,n(q−1)+r}} ) , \\ D(n) & = ∏_{p∤n} (f(p^{ν_{p}(r)}) ∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n−1,n(q−1)+r}} ) . \end{aligned}

Proof. By Theorem 3, and the fact that f is multiplicative, we have

\frac{f(r)}{f(nq + r)}\binom{nq + r}{n}_{f} = ∏_{p} \frac{f(p^{ν_{p}(r)})}{f(p^{ν_{p}(nq+r)})} (∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n,n(q−1)+r}} ) .

We now break the primes into three cases, corresponding to the three factors A(n), B(n), and D(n) in the theorem statement.

1. Suppose p is a prime that divides n such that that ν_{p}(nq) ≥ ν_{p}(r). Since p divides n, p divides nq. Since ν_{p}(nq) ≥ ν_{p}(r), ν_{p}(nq + r) = ν_{p}(r). The contribution to the value of A_{f}(n, q, r) for a prime p in this case, then, is

∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n,n(q−1)+r}} .

2. Suppose p is a prime that divides n such that ν_{p}(nq) < ν_{p}(r). Since p divides n, we know p divides nq. The fact that ν_{p}(nq) < ν_{p}(r) implies that p also divides r and nq + r, and consequently that ν_{p}(nq + r) = ν_{p}(nq). The contribution to the value of A_{f}(n, q, r) for a prime p in this case is

\frac{f(p^{ν_{p}(r)})}{f(p^{ν_{p}(nq)})} ∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n,n(q−1)+r}} .

3. Suppose p is a prime that does not divide n. In this case it helps to express A_{f}(n, q, r) as

\frac{f(r)}{f(nq + r)}\binom{nq + r}{n}_{f} = \frac{f(r)}{f(nq + r)} \frac{f(nq + r) ⋯ f(n(q − 1) + r + 1)}{f(n) ⋯ f(1)}

= \frac{f(r)}{f(n)} \frac{f(nq + r − 1) ⋯ f(n(q − 1) + r + 1)}{f(n − 1) ⋯ f(1)}

= \frac{f(r)}{f(n)}\binom{nq + r − 1}{n − 1}_{f}

= ∏_{p} \frac{f(p^{ν_{p}(r)})}{f(p^{ν_{p}(n)})} (∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n−1,n(q−1)+r}} ) .

Since p does not divide n, ν_{p}(n) = 0. Thus the contribution to A_{f}(n, q, r) for a prime in this case is

f(p^{ν_{p}(r)}) (∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n−1,n(q−1)+r}} ) .

If we let f(n) = n in Theorem 14, then we obtain a Kummer-like theorem for the Fuss-Catalan numbers.

Corollary 15. The exponent of the largest power of a prime p dividing A(n, q, r) is given by the following:

ν_{p} (A(n, q, r)) = \begin{cases}κ_{p}(n, n(q − 1) + r), & p|n, ν_{p}(nq) ≥ ν_{p}(r); \\ ν_{p}(r) − ν_{p}(nq) + κ_{p}(n, n(q − 1) + r), & p|n, ν_{p}(nq) < ν_{p}(r); \\ ν_{p}(r) + κ_{p}(n − 1, n(q − 1) + r), & p ∤ n. \end{cases}

Proof. Let f be the identity function; i.e., f(n) = n. Again, the identity function is clearly multiplicative. Applying Theorem 14 to the case of a prime p that divides n and satisfies ν_{p}(nq) ≥ ν_{p}(r), we obtain the following contribution to A(n, q, r) from p:

∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n,n(q−1)+r}} = ∏_{i≥0} p^{ϵ_{i}^{p,n,n(q−1)+r}} = p^{∑_{i≥0} ϵ_{i}^{p,n,n(q−1)+r}} = p^{κ_{p}(n,n(q−1)+r)}.

The proofs of the other two cases are similar.

Theorem 14 also implies that A_{f}(n, q, r) is an integer when f is multiplicative and divisible.

Corollary 16. If f : ℕ → ℕ is both multiplicative and divisible, then A_{f}(n, q, r) is an integer for all n. In this case we have

A_{f}(n, q, r) = A(n)B(n)D(n),

where

A(n) = ∏_{p|n,ν_{p}(nq)≥ν_{p}(r)} (∏_{i≥0} g_{p}(i)^{ϵ_{i}^{p,n,n(q−1)+r}}) ,

B(n) = ∏_{p|n,ν_{p}(nq)<ν_{p}(r)} (\frac{f(p^{ν_{p}(r)})}{f(p^{ν_{p}(nq)})} ∏_{i≥0} g_{p}(i)^{ϵ_{i}^{p,n,n(q−1)+r}}) ,

D(n) = ∏_{p∤n} (f(p^{ν_{p}(r)}) ∏_{i≥0} g_{p}(i)^{ϵ_{i}^{p,n−1,n(q−1)+r}}) ,
g_{p}(i) = f(p^{i+1})/f(p^{i}).

Proof. Since f is divisible, f(p^{i}) divides f(p^{i+1}). In addition, since ν_{p}(nq) < ν_{p}(r) then f(p^{ν_{p}(nq)}) divides f(p^{ν_{p}(r)}). The result then follows from Theorem 14.

The next few corollaries are the versions of Theorem 14 and Corollaries 15 and 16 for the usual Catalan numbers.

Corollary 17. If f : ℕ → ℕ is multiplicative, then the f-Catalan number, given by C_{f}(n) =

\frac{1}{f(n + 1)}\binom{2n}{n}_{f}, satisfies

C_{f}(n) = A(n)D(n),

where

A(n) = ∏_{p|n} (∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n,n}}) and D(n) = ∏_{p∤n} (∏_{i≥0} (\frac{f(p^{i+1})}{f(p^{i})})^{ϵ_{i}^{p,n−1,n+1}}) .

Proof. The usual Catalan number is the case q = 2, r = 1, of the more general Fuss-Catalan number. In this case, ν_{p}(r) = 0 for all primes p. Thus in Theorem 14 we have B(n) = 1. In addition, if p divides n, then the base-p representation of n has a 0 in the ones place. Thus ϵ_{i}^{p,n,n+1} = ϵ_{i}^{p,n,n} in this case. The rest of the result follows directly from Theorem 14.

We also have a Kummer-like theorem for the Catalan numbers.

Corollary 18. If a prime p divides n, the exponent of the largest power of p dividing C(n) is the number of carries occurring in the base-p sum of n with itself. Otherwise, the exponent of the largest power of p dividing C(n) is the number of carries occurring in the base-p sum of n − 1 and n + 1. In other words,

ν_{p} (C(n)) = \begin{cases}κ_{p}(n, n), & p|n; \\ κ_{p}(n − 1, n + 1), & p ∤ n. \end{cases}

Proof. This follows from Corollary 15, with q = 2, r = 1. As in the proof of Corollary 17, ν_{p}(r) = 0 for all primes p, and so the case ν_{p}(nq) < ν_{p}(r) does not occur. Also as in the proof of Corollary 17, if p|n then ϵ_{i}^{p,n,n+1} = ϵ_{i}^{p,n,n} for all i. Thus κ_{p}(n, n + 1) = κ_{p}(n, n).

Finally, Corollary 16 implies that C_{f}(n) is an integer when f is multiplicative and divisible.

Corollary 19. If f : ℕ → ℕ is both multiplicative and divisible, then C_{f}(n) is an integer for all n. In this case we have

C_{f}(n) = A(n)D(n),

where

A(n) = ∏_{p|n} (∏_{i≥0} g_{p}(i)^{ϵ_{i}^{p,n,n}}) and D(n) = ∏_{p∤n} (∏_{i≥0} g_{p}(i)^{ϵ_{i}^{p,n−1,n+1}})

with g_{p}(i) = f(p^{i+1})/f(p^{i}).

Since Euler’s ϕ-function is both multiplicative and divisible, Corollary 19 answers in the affirmative a question of Edgar [4] as to whether C_{ϕ}(n) is an integer for all n ≥ 0.

5 Ward’s divisor functions

As mentioned in the introduction, Ward [7] proves that a larger class of functions have integer generalized binomial coefficients. We introduce that class of sequences here and obtain formulas for the associated Fuss-Catalan numbers, which also turn out to be integers. This class of sequences includes the multiplicative and divisible functions, but the formulas in this section require knowledge of carries in every base less than or equal to n + m instead of only those arising in prime base arithmetic. Consequently, the formulas here are not as precise as the ones previously established.

For any sequence of integers s = (s_{1}, s_{2}, s_{3}, …) define the function f_{s} : ℕ → ℕ by

f_{s}(n) = ∏_{d|n} s_{d},  (2)

where the product is over all divisors of n.

Theorem 20 (Ward). Let s be a sequence of nonzero integers with associated function f_{s}. For any nonnegative integers n and m we have

\binom{n + m}{n}_{f_{s}} = ∏_{b>1} s_{b}^{ϵ_{0}^{b}},  (3)

where ϵ_{0}^{b} = ϵ_{0}^{b,n,m} is the carry in the ones position.

Proof. Fix b > 1. Then, the number of times that s_{b} appears in ∏_{i=1}^{k} f(k) is equal to the number of integers in \{1, …, k\} divisible by b, which is given by ⌊\frac{k}{b}⌋. Hence, the number of times s_{b} appears in the quotient

\binom{n + m}{n}_{f} = \frac{∏_{i=1}^{n+m} f(i)}{(∏_{i=1}^{n} f(i)) (∏_{i=1}^{m} f(i))}

is given by ⌊\frac{n+m}{b}⌋−⌊\frac{n}{b}⌋−⌊\frac{m}{b}⌋. Finally, a proof identical to the one given in Lemma 1 shows that ϵ_{0}^{b,n,m} = ⌊\frac{n+m}{b}⌋ − ⌊\frac{n}{b}⌋ − ⌊\frac{m}{b}⌋.

In particular, since carries are always 0 or 1, this theorem implies that such functions f_{s} always have integral generalized binomial coefficients. As previously mentioned, this characterization requires arithmetic in all bases whereas our results in previous sections only require arithmetic in prime bases.

Remark 21. Dyer [3] suggests using equation (3) as a definition of generalized binomial coefficients. Doing so would allow one to define such coefficients for sequences in an arbitrary ring, as well as allow for f(k) = 0 for some values of k.

Theorem 22. Let f be a multiplicative and divisible function. Then there exists an integer sequence s such that f(n) = ∏_{d|n} s_{d} for all n.

Proof. Since f is multiplicative, we must have f(1) = 1, so we let s_{1} = 1. Then for i > 1, we define s as follows:

s_{i} = \begin{cases}\frac{f(p^{r})}{f(p^{r−1})}, & if i = p^{r} (r > 0) for p prime; \\ 1, & otherwise. \end{cases}

Since f is divisible, s_{i} is an integer for all i. Next, by definition we get f(p^{r}) = \frac{f(p^{r})}{f(p^{r−1})} ·

\frac{f(p^{r−1})}{f(p^{r−2})} ⋯ \frac{f(p)}{1} = ∏_{i=1}^{r} s_{p^{i}} = ∏_{d|p^{r}} s_{d}. Then, since f is multiplicative and s_{i} = 1 when i is not a prime power, we get that f(n) = ∏_{d|n} s_{d} as required.

We note that there are multiplicative sequences for which no integer sequence exists satisfying Condition (2). In addition, there are divisible sequences for which no integer sequence exists satisfying Condition (2). Moreover, there are sequences satisfying Condition (2) that are not multiplicative and divisible; Ball, et al. [1] describe a few examples of such sequences, and some are listed in the appendix.

Similar to previous sections, we use Theorem 20 to demonstrate that the associated Fuss-Catalan numbers are integers. Before doing this, we have the following lemma.

Lemma 23. Let n, r, q, b be integers with n ≥ 0, r ≥ 0, q > 0, and b > 1. If b divides (nq + r) and b does not divide r, then ϵ_{0}^{b,n(q−1)+r,n} = 1.

Proof. We have that n = (n_{0}, n_{1}, …, n_{k})_{b}, nq + r = (m_{0}, m_{1}, …, m_{l})_{b}, and n(q − 1) + r = (l_{0}, l_{1}, …, l_{t})_{b}. Since b divides nq + r, we have m_{0} = 0, and we know that n_{0} + l_{0} = m_{0} (mod b). Suppose, for the sake of contradiction, that ϵ_{0}^{b,n(q−1)+r,n} = 0; this implies that n_{0} = 0 and l_{0} = 0. Thus, b divides n and b divides n(q − 1) + r. In turn, we conclude that b divides n(q − 1). The previous two statements imply that b divides r, contradicting our main assumptions. Therefore, ϵ_{0}^{b,n(q−1)+r,n} = 1 as required.

The integrality of f_{s}-Fuss-Catalan numbers is now immediate from Theorem 20.

Theorem 24. Let s be a sequence of nonzero integers with associated function f_{s}. Then A_{f_{s}}(n, q, r) is an integer for all n. In particular we have

A_{f_{s}}(n, q, r) = G(n)H(n)J(n),

with

G(n) = ∏_{\begin{matrix}b>1 \\ b|r \\ b ∤ nq+r \end{matrix}} s_{b}^{1+ϵ_{0}^{b}},  H(n) = ∏_{\begin{matrix}b>1 \\ b ∤ r \\ b ∤ nq+r \end{matrix}} s_{b}^{ϵ_{0}^{b}},  J(n) = ∏_{\begin{matrix}b>1 \\ b|r \\ b|nq+r \end{matrix}} s_{b}^{ϵ_{0}^{b}},

where ϵ_{0}^{b} = ϵ_{0}^{b,n(q−1)+r,n}.

Proof. When q = 0, the result is true by Theorem 20. Now by definition of f_{s} and Theorem 20 we get

A_{f_{s}}(n, q, r) = \frac{f_{s}(r)}{f_{s}(nq + r)}\binom{nq + r}{n}_{f_{s}} = \frac{∏_{d|r} s_{d}}{∏_{d|nq+r} s_{d}} · ∏_{b>1} s_{b}^{ϵ_{0}^{b,n(q−1)+r,n}}.

If either d|r and d|nq + r or d ∤ r and d ∤ nq + r then there is no contribution of s_{d} from the first fraction. On the other hand, if d|r and d ∤ nq +r, then we have a total of 1+ϵ_{0}^{d,n(q−1)+r,n} occurrences of s_{d} in the product (not in the denominator). Finally, if d ∤ r and d|nq + r, then by Lemma 23, we have ϵ_{0}^{d,n(q−1)+r,n} = 1 and so there is an occurrence of s_{d} in both the numerator and the denominator, which cancel out.

In a similar fashion to Remark 21, we could take the characterization in Theorem 24 as the definition of the f_{s}-Fuss-Catalan numbers.

A Sequences with integer generalized binomial coefficients

The Online Encyclopedia of Integer sequences (OEIS) contains a wealth of examples of multiplicative and divisible sequences that we consider in this paper as well as many examples of sequences satisfying the property of Ward described in Section 5. In this appendix, we include a list of relevant examples of sequences. Moreover, every collection of generalized binomial coefficients can be interpreted as a triangle, read by rows, where entry k in row n is given by \binom{n}{k}_{f}. After the tables, we also describe a method for efficiently generating the triangle of generalized binomial coefficients efficiently.

The following table lists interesting examples of multiplicative and divisible sequences along with the OEIS number. Additionally, we have provided the listing of the associated generalized binomial coefficients (typically read as a triangle by rows).

Name, Description, or Formula OEIS Entry

Generalized binomial coefficients

Euler totient function (ϕ)

\underline{A000010}

\underline{A238453}

Identity function

\underline{A000027}

\underline{A007318}
Squares  \underline{A000290} \underline{A008459}
Cubes  \underline{A000578} \underline{A181543}

Dedekind psi function

\underline{A001615}

\underline{A238498}
f(n) = nϕ(n) \underline{A002618} \underline{A255914}

Completely multiplicative, with f(p) = p − 1

\underline{A003958}

Completely multiplicative with f(p_{k}) = p_{k} ·(k+1)

\underline{A003961}
If n = ∏ p_{k}^{e_{k}} then a(n) = ∏(p_{k} − 1)^{e_{k}}, a(1) = 1  \underline{A003958}
If n = ∏ p_{k}^{e_{k}} then a(n) = ∏(p_{k} + 1)^{e_{k}}, a(1) = 1  \underline{A003959}

Radical (largest squarefree number dividing n)

\underline{A007947}

\underline{A048804}

n divided by the radical

\underline{A003557}

\underline{A246465}

Largest square dividing n

\underline{A008833}

Number of solutions to x^{2} = 0 (mod n)

\underline{A000188}

Number of solutions to x^{2} = 1 (mod n)

\underline{A060594}

f(n) = n if n is odd, f(n) = 2n if n is even

\underline{A022998}

f(n) = n if n odd, n/2 if n even

\underline{A026741}

\underline{A214281}

Unitary divisor function

\underline{A034444}

Number of squares dividing n

\underline{A046951}

Unitary totient function

\underline{A047994}

Name, Description, or Formula OEIS Entry

Generalized binomial coefficients

Unitary Jordan function J_{2}^{∗}(n)

\underline{A191414}
f(n) = n ∏_{p|n} p \underline{A064549}

Multiplicative, with f(p^{k}) = p − 1

\underline{A173557}

\underline{A239702}

Jordan function (J_{2})

\underline{A007434}

\underline{A238688}

Jordan function (J_{3})

\underline{A059376}

\underline{A238743}

Jordan function (J_{4})

\underline{A059377}

\underline{A238754}

Jordan function (J_{5})

\underline{A059378}

\underline{A239633}

Jordan function (J_{6})

\underline{A069091}

\underline{A255915}

Jordan function (J_{7})

\underline{A069092}

Jordan function (J_{8})

\underline{A069093}

Jordan function (J_{9})

\underline{A069094}

Jordan function (J_{10})

\underline{A069095}
gcd_{2}(n)  \underline{A000034}
gcd_{3}(n)  \underline{A109007}
gcd_{4}(n)  \underline{A109008}
gcd_{5}(n)  \underline{A109009}
gcd_{6}(n)  \underline{A089128}
gcd_{7}(n)  \underline{A109010}
gcd_{8}(n)  \underline{A109011}

Highest power of 2 dividing n

\underline{A006519}

\underline{A082907}

Highest power of 3 dividing n

\underline{A038500}

\underline{A242849}

Highest power of 5 dividing n

\underline{A060904}

\underline{A254609}

Highest power of 7 dividing n Highest power of 11 dividing n Odd part of n

\underline{A000265}

Remove 3’s from n

\underline{A038502}

Largest divisor of n not divisible by 5

\underline{A132739}

Largest divisor of n not divisible by 7

\underline{A242603}

Replace primes factor of n by 2: a(n) = 2^{Ω(n)}

\underline{A061142}

Completely multiplicative with f(p) = p#

\underline{A108951}

The following table lists sequences that have integral generalized binomial coefficients by Theorem 20 but that are not multiplicative and divisible. Again we include their OEIS entry and triangle of associated coefficients.

Name, Description, or

Formula OEIS Entry

Generalized binomial coefficients

Fibonacci numbers

\underline{A000045}

\underline{A010048}
Pell numbers \underline{A000129} \underline{A099927}

Highest power of 4 dividing n

\underline{A234957}

\underline{A243756}

Highest power of 6 dividing n

\underline{A234959}

\underline{A254730}

Highest power of 8 dividing n Highest power of 9 dividing n Remove factors of 2 and 3 not contributing to 6

\underline{A214681}

Remove factors of 2 not contributing to 4

\underline{A214682}

Remove factors of 2, 3, 5 not contributing to 30

\underline{A214685}

Denominators of even Bernoulli numbers

\underline{A002445}

Denominators of Bernoulli numbers (variant)

\underline{A141056}

We note that generating the triangle of generalized binomial coefficients using the definition is inefficient. However, it turns out that there is a relatively simple recurrence relation that all generalized binomial coefficients satisfy (similar to Pascal’s identity for classical binomial coefficients).

Theorem 25. Let f : ℕ → ℕ be a nonzero integer sequence, and let m, n ∈ ℕ with n ≤ m. Then

\binom{m}{n}_{f} = \frac{nf(m)}{mf(n)}\binom{m − 1}{n − 1}_{f} + \frac{(m − n)f(m)}{mf(m − n)}\binom{m − 1}{n}_{f}.

Proof. This follows by definition since the right hand side is given by

\frac{nf(m) ∏_{i=1}^{m−1} f(i)}{mf(n) (∏_{i=1}^{n−1} f(i)) (∏_{i=1}^{m−n} f(i))} + \frac{(m − n)f(m) ∏_{i=1}^{m−1} f(i)}{mf(m − n) (∏_{i=1}^{n} f(i)) (∏_{i=1}^{m−n−1} f(i))}

which simplifies to

\frac{n ∏_{i=1}^{m} f(i)}{m (∏_{i=1}^{n} f(i)) (∏_{i=1}^{m−n} f(i))} + \frac{(m − n) ∏_{i=1}^{m} f(i)}{m (∏_{i=1}^{n} f(i)) (∏_{i=1}^{m−n} f(i))}.

The result now follows since \frac{n}{m} + \frac{m−n}{m} = 1.

We note that the previous theorem is true for all integer sequences (not only those considered in this paper). However, the results are typically not integral. Moreover, this theorem cannot be used to prove integrality of the coefficients because the expressions \frac{nf(m)}{mf(n)}

and \frac{(m−n)f(m)}{mf(m−n)} are rarely integral. Using this theorem does allow for efficient computation of the triangle of generalized binomial coefficients, though.

Finally, the result in the previous theorem may be concisely given by the relation

\frac{m}{f(m)}\binom{m}{n}_{f} = \frac{n}{f(n)}\binom{m − 1}{n − 1}_{f} + \frac{m − n}{f(m − n)}\binom{m − 1}{n}_{f}.

References

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

[2] R. D. Carmichael, On the numerical factors of the arithmetic forms α^{n} ± β^{n}, Ann. of Math., 15 (1913-1914), 30–48.

[3] Matthew J. Dyer, Rank two detection of singularities of Schubert varieties, preprint,

   2001. Available at http://www.nd.edu/~dyer/papers/ranktwo.pdf.

[4] Tom Edgar, Totienomial coefficients, Integers, 14 (2014), Paper A62.

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

[6] The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences,

   http://oeis.org.

[7] Morgan Ward, A note on divisibility sequences, Bull. Amer. Math. Soc., 45 (1939), 334–336.

2010 Mathematics Subject Classification: Primary 11B65; Secondary 05A10, 11A05. Keywords: multiplicative function, divisible function, generalized binomial coefficient, Kummer’s theorem, Fuss-Catalan number.

(Concerned with sequences \underline{A000010}, \underline{A000027}, \underline{A000034}, \underline{A000045}, \underline{A000129}, \underline{A000188}, \underline{A000265}, \underline{A000290}, \underline{A000578}, \underline{A001615}, \underline{A002445}, \underline{A002618}, \underline{A003557}, \underline{A003958}, \underline{A003959}, \underline{A003961}, \underline{A006519}, \underline{A007318}, \underline{A007434}, \underline{A007947}, \underline{A008459}, \underline{A008833}, \underline{A010048}, \underline{A022998}, \underline{A026741}, \underline{A034444}, \underline{A038500}, \underline{A038502}, \underline{A046951}, \underline{A047994}, \underline{A048804}, \underline{A059376}, \underline{A059377}, \underline{A059378}, \underline{A060594}, \underline{A060904}, \underline{A061142}, \underline{A064549}, \underline{A069091}, \underline{A069092}, \underline{A069093}, \underline{A069094}, \underline{A069095}, \underline{A082907}, \underline{A089128}, \underline{A099927}, \underline{A108951}, \underline{A109007}, \underline{A109008}, \underline{A109009}, \underline{A109010}, \underline{A109011}, \underline{A132739}, \underline{A141056}, \underline{A173557}, \underline{A181543}, \underline{A191414}, \underline{A214281}, \underline{A214681}, \underline{A214682}, \underline{A214685}, \underline{A234957}, \underline{A234959}, \underline{A238453}, \underline{A238498}, \underline{A238688}, \underline{A238743}, \underline{A238754}, \underline{A239633}, \underline{A239702}, \underline{A242603}, \underline{A242849}, \underline{A243756}, \underline{A246465}, \underline{A254609}, \underline{A254730}, \underline{A255914}, \underline{A255915}.)

Received September 17 2015; revised versions received December 10 2015; December 17 2015. Published in Journal of Integer Sequences, December 18 2015.

Return to Journal of Integer Sequences home page.