## 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  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  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.)

References

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.