There are several numbers that are analogous to binomial coefficients and, at least in Donald Knuth’s notation, are written in a style analogous to binomial coefficients. And just as binomial coefficients can be arranged into Pascal’s triangle, these numbers can be arranged into similar triangles.

In Pascal’s triangle, each entry is the sum of the two above it. Specifically,

binom{n}{k} = binom{n-1}{k} + binom{n-1}{k-1}

The q-binomial coefficients satisfy two similar identities.

begin{align*} binom{n}{k}_q &= q^k binom{n-1}{k}_q + binom{n-1}{k-1}_q \ &= binom{n-1}{k}_q + q^{n-k}binom{n-1}{k-1}_q end{align*}

Here are the analogous theorems for Stirling numbers of the first

left[ begin{matrix} n \ k end{matrix} right] = (n-1) left[ begin{matrix} n-1 \ k end{matrix} right] + left[ begin{matrix} n-1 \ k-1 end{matrix} right]

and second

left{ begin{matrix} n \ k end{matrix} right} = k left{ begin{matrix} n-1 \ k end{matrix} right} + left{ begin{matrix} n-1 \ k-1 end{matrix} right}

kinds.

And finally, here is the corresponding theorem for Eulerian numbers.

leftlangle begin{matrix} n \ k end{matrix} rightrangle = (k+1) leftlangle begin{matrix} n-1 \ k end{matrix} rightrangle + (n-k) leftlangle begin{matrix} n-1 \ k-1 end{matrix} rightrangle

(I don’t know why this equation is displaying smaller than the others; the size is declared to be the same.)

The post Analogs of binomial coefficients first appeared on John D. Cook.

Previous Post
Next Post