### Generalized binomial coefficients

The reader is probably familiar with factorials and binomial coefficients. The factorial of a number n is the product of all positive integers between 1 and n, and it is denoted by n!. For example, $\displaystyle 6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720$. We define 0! = 1.

Factorials are used to define the binomial coefficients. The symbol $\displaystyle \binom{n}{k}$ is defined by the equation $\displaystyle \binom{n}{k} = \frac{n!}{k!\,(n-k)!}$, provided that $0 \le k \le n$. It is not obvious that all binomial coefficients are integers, but this fact can be proved by induction on n using Pascal’s rule:

$\displaystyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\ .$

We can generalize both factorials and binomial coefficients by replacing the sequence of all positive integers {1, 2, 3, 4, 5, …} by an arbitrary sequence of positive integers. Let

$\displaystyle u = \{u_1, u_2, u_3, \ldots\}$

be any sequence of positive integers whatsoever, and define the u-factorial by the formula

$\displaystyle n!_u = u_1 u_2 u_3 \cdots u_n, \quad 0!_u = 1.$

We use the u-factorial function to define the u-binomial coefficient.

$\displaystyle\binom{n}{k}_u = \frac{n!_u}{k!_u\,(n-k)!_u}$

These definitions are very general, and they do not guarantee that our binomial coefficients are integers. To remedy this deficiency, we will assume that u is a strong divisibility sequence, which means that $d = \gcd(m,n)$ implies $u_d = \gcd(u_m, u_n)$. Here are some examples of strong divisibility sequences.

1. The identity sequence $u_n = n$.
2. The Fibonacci numbers.
3. The q-bracket $\displaystyle u_n = [n]_q = \frac{q^n - 1}{q - 1}$ where $q\ge2$ is an integer.

I claim that if u is a strong divisibility sequence then the u-binomial coefficients are always integers, and I will explain how I discovered a proof of this fact. The key idea is to search for a generalization of Pascal’s rule:

$\displaystyle \binom{n}{k}_u = r \binom{n-1}{k-1}_u + s \binom{n-1}{k}_u$

We write this equation out in full, and then simplify using the fact that $m!_u = u_m \cdot (m-1)!_u$.

It remains to find r and s. Since u is a strong divisibility sequence, $\gcd(u_k, u_{n-k}) = u_d$ where $d = \gcd(k, n-k)$. But ud divides un, since d divides n. Therefore, Bézout’s identity implies that the integers r and s exist. This allows us to prove by induction on n that all u-binomial coefficients are integers.

If we start with the Fibonacci numbers, then the numbers defined by this process are called Fibonomial coefficients. We can also define the q-binomial coefficients by starting with the q-brackets.

The Catalan numbers are ubiquitous in combinatorics. The nth Catalan number is defined by

$\displaystyle \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{n!\,(n+1)!}.$

Alexander Bogomolny has given a delightfully simple proof that this quantity is always an integer. I will leave it to the reader to check that the proof remains valid if the factorials are replaced with u-factorials. This produces integer sequences that are analogous to the Catalan numbers, such as the Fibonomial Catalan numbers when un is the nth Fibonacci number, and the q-Catalan numbers when $u_n = (q^n - 1)/(q - 1)$.