For a natural number and an element of a (unital) ring, the falling factorial or falling power (also sometimes written ) is defined by
If and are two finite sets of cardinalities and , then the falling factorial counts the number of injections from to . Dividing by the action of the permutation group of with elements and counting the orbits, the so called binomial coefficient counts the number of subsets of of cardinality .
In the calculus of finite differences, where an analogy is set up between the ordinary “continuous” derivative and the “discrete” derivative (= difference operator)
it is the falling factorial that plays a role analogous to the ordinary power . For example, we have . Compare the formula which interpolates the Pascal triangle recurrence
The discrete analogue of the identity is the identity
This may be used to motivate the definition of for all integers . For a natural number, define
Then the difference formula and the multiplicative identity continue to hold for all integers . These facts have numerous applications throughout discrete mathematics.
Falling Factorial on Wolfram MathWorld.
Ronald Graham, Donald Knuth, and Oren Patashnik, Concrete Mathematics, 2 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.