Contents

# Contents

## Definition

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

$x^{\underline{k}} = x(x-1)\ldots (x-k+1).$

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

## Properties

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

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

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

$\binom{n+1}{k} - \binom{n}{k} = \binom{n-1}{k}.$

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

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

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

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

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

## References

• Falling Factorial on Wolfram MathWorld.

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

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