nLab
falling factorial

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 expression 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 January 14, 2018 at 14:57:22. See the history of this page for a list of all contributions to it.