### 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, . We define 0! = 1.

Factorials are used to define the binomial coefficients. The symbol is defined by the equation , provided that . It is not obvious that all binomial coefficients are integers, but this fact can be proved by induction on *n* using Pascal’s rule:

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

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

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

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 implies . Here are some examples of strong divisibility sequences.

- The identity sequence .
- The Fibonacci numbers.
- The
*q-bracket*where 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:

We write this equation out in full, and then simplify using the fact that .

It remains to find *r* and *s*. Since *u* is a strong divisibility sequence, where . But *u _{d}* divides

*u*, since

_{n}*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 *n*th Catalan number is defined by

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 *u _{n}* is the

*n*th Fibonacci number, and the

*q*-Catalan numbers when .

Can you give some examples and some solutions to the examples if possible on binomial coefficients.