Generalized Binomial Coefficients from Multiplicative and Divisible Functions

Given a function f from the natural numbers to the natural numbers, one way to generalize the binomial coefficient is via

\displaystyle \binom{n+m}{n}_f = \frac{ \prod_{i=1}^{n+m} f(i)}{ \left( \prod_{i=1}^n f(i) \right) \left( \prod_{i=1}^m f(i) \right)}.

The usual binomial coefficient \binom{n+m}{n} of course has f as the identity function f(n) = n.

Question: What kinds of functions f guarantee that \binom{m+n}{n}_f is an integer for all natural values of n and m?  A famous paper by Knuth and Wilf [2] includes a proof that strongly divisible functions (i.e., functions satisfying \gcd(f(m), f(n)) = f(\gcd (m,n)) guarantee this property.  The most famous strongly divisible function is probably the Fibonacci sequence F_n, so the binomial coefficient \binom{n+m}{n}_F is always an integer.

Another answer to this question comes from a paper [1] Tom Edgar and I just published.  We prove that functions that are both multiplicative and divisible also guarantee that \binom{m+n}{n}_f is an integer for all natural values of n and m.  (Multiplicative functions have f(mn) = f(m)f(n) when m and n are relatively prime.  Divisible functions have f(m)|f(n) whenever m|n.)  The class of multiplicative and divisible functions includes Euler’s totient, Dedekind’s psi, as well as many others.  (See Appendix A in our paper for a long list of some of these.)  It also includes the class of completely multiplicative functions (i.e., f(mn) = f(m)f(n) for all natural numbers m and n).  The class of multiplicative and divisible functions has overlap with the strongly divisible class of functions, but it is neither a subset nor a superset of it.

Tom and I start by proving the following formula for the generalized binomial coefficient when f is multiplicative:

\displaystyle \binom{n+m}{n}_f = \prod_p \left( \prod_{i \geq 0} \left( \frac{f(p^{i+1})}{f(p^i)}\right)^{\epsilon^p_i}\right),

where the outer product is taken over all primes p.  Also, \epsilon^p_i is defined to be 1 if there is a carry in the ith position when m and n are added in base p and 0 otherwise.  Since the condition “f(p^i) divides f(p^{i+1}) for all primes p and nonnegative integers i” turns out to be equivalent to f being divisible, the integrality result follows.

Our formula also allows us to give a quick proof of Kummer’s Theorem on the prime factorization of the binomial coefficients, as f(p^{i+1})/f(p^i) = p when f is the identity function.

In addition, we prove that generalized Catalan numbers C_f = \frac{1}{f(n+1)} \binom{2n}{n}_f are always integers when f is both multiplicative and divisible.  (Actually, we prove this for generalized Fuss-Catalan numbers and then derive the usual Catalan numbers as a special case.)


  1. Tom Edgar and Michael Z. Spivey, “Multiplicative Functions, Generalized Binomial Coefficients, and Generalized Catalan Numbers,” Journal of Integer Sequences 19 (1): Article 16.1.6, 2016.
  2. Donald E. Knuth and Herbert S. Wilf, “The Power of a Prime That Divides a Generalized Binomial Coefficient,” Journal für die reine und angewandte Mathematik 396: 212-219, 1989.


This entry was posted in binomial coefficients, elementary number theory, number theory. Bookmark the permalink.

2 Responses to Generalized Binomial Coefficients from Multiplicative and Divisible Functions

  1. pwgdrk says:

    Interesting. Any combinatorial interpretations of generalized b.c. for some f?

    • mzspivey says:

      Not yet. We’ve been thinking about that for some specific functions f but haven’t come up with anything so far. If you can think of some I’d love to hear them.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s