Generalized binomial coefficients

by David Radcliffe

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

Advertisements