nLab falling factorial

Contents

Contents

Definition

For kk a natural number and xx an element of a (unital) ring, the falling factorial or falling power x k̲x^{\underline{k}} (also sometimes written (x) k(x)_k) is defined by

x k̲=x(x1)(xk+1).x^{\underline{k}} = x(x-1)\ldots (x-k+1).

If XX and YY are two finite sets of cardinalities |X|=k|X| = k and |Y|=n|Y| = n, then the falling factorial n k̲n^{\underline{k}} counts the number of injections from XX to YY. Dividing by the action of the permutation group of XX with k!k! elements and counting the orbits, the so called binomial coefficient n k̲k!=(nk)\frac{n^{\underline{k}}}{k!} = \binom{n}{k} counts the number of subsets of YY of cardinality kk.

Properties

In the calculus of finite differences, where an analogy is set up between the ordinary “continuous” derivative (Df)(x)=lim h0f(x+h)f(x)h(D f)(x) = \lim_{h \to 0} \frac{f(x+h) - f(x)}{h} and the “discrete” derivative (= difference operator)

(Δf)(x)f(x+1)f(x),(\Delta f)(x) \coloneqq f(x+1) - f(x),

it is the falling factorial x k̲x^{\underline{k}} that plays a role analogous to the ordinary power x kx^k. For example, we have Δx k̲=kx k1̲\Delta x^{\underline{k}} = k x^{\underline{k-1}}. Compare the formula Δx k̲k!=x k1̲(k1)!\Delta \frac{x^{\underline{k}}}{k!} = \frac{x^{\underline{k-1}}}{(k-1)!} which interpolates the Pascal triangle recurrence

(n+1k)(nk)=(n1k).\binom{n+1}{k} - \binom{n}{k} = \binom{n-1}{k}.

The discrete analogue of the identity x kx l=x k+lx^k x^l = x^{k+l} is the identity

x k̲(xk) l̲=x k+l̲.x^{\underline{k}} (x-k)^{\underline{l}} = x^{\underline{k+l}}.

This may be used to motivate the definition of x k̲x^{\underline{k}} for all integers kk. For kk a natural number, define

x k̲1(x+k) k̲=1(x+k)(x+k1)(x+1).x^{\underline{-k}} \coloneqq \frac1{(x+k)^{\underline{k}}} = \frac1{(x+k)(x+k-1) \ldots (x+1)}.

Then the difference formula Δx k̲=kx k1̲\Delta x^{\underline{k}} = k x^{\underline{k-1}} and the multiplicative identity x k̲(xk) l̲=x k+l̲x^{\underline{k}} (x-k)^{\underline{l}} = x^{\underline{k+l}} continue to hold for all integers k,lk, l. These facts have numerous applications throughout discrete mathematics.

References

  • Falling Factorial on Wolfram MathWorld.

  • Ronald Graham, Donald Knuth, and Oren Patashnik, Concrete Mathematics, 2nd^{nd} edition, Addison-Wesley (1994).

Last revised on October 13, 2020 at 16:50:52. See the history of this page for a list of all contributions to it.