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