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

.

The usual binomial coefficient of course has *f* as the identity function .

Question: What kinds of functions *f* guarantee that 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 guarantee this property. The most famous strongly divisible function is probably the Fibonacci sequence , so the binomial coefficient 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 is an integer for all natural values of *n* and *m.* (Multiplicative functions have when *m* and *n* are relatively prime. Divisible functions have whenever .) 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., 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:

where the outer product is taken over all primes *p*. Also, is defined to be 1 if there is a carry in the *i*th position when *m* and *n* are added in base *p* and 0 otherwise. Since the condition “ divides 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 when *f* is the identity function.

In addition, we prove that generalized Catalan numbers 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**

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

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

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.