Falling and rising factorials explained
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial
The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial,[1] rising sequential product, or upper factorial) is defined as
The value of each is taken to be 1 (an empty product) when
These symbols are collectively called
factorial powers.
[2] The Pochhammer symbol, introduced by Leo August Pochhammer, is the notation
, where is a
non-negative integer. It may represent
either the rising or the falling factorial, with different articles and authors using different conventions. Pochhammer himself actually used
with yet another meaning, namely to denote the
binomial coefficient
.
[3] In this article, the symbol
is used to represent the falling factorial, and the symbol
is used for the rising factorial. These conventions are used in
combinatorics,
[4] although
Knuth's underline and overline notations
and
are increasingly popular.
[2] [5] In the theory of
special functions (in particular the
hypergeometric function) and in the standard reference work
Abramowitz and Stegun, the Pochhammer symbol
is used to represent the rising factorial.
[6] [7] When
is a positive integer,
gives the number of -permutations (sequences of distinct elements) from an -element set, or equivalently the number of
injective functions from a set of size
to a set of size
. The rising factorial
gives the number of
partitions of an
-element set into
ordered sequences (possibly empty).
Examples and combinatorial interpretation
The first few falling factorials are as follows:The first few rising factorials are as follows:The coefficients that appear in the expansions are Stirling numbers of the first kind (see below).
When the variable
is a positive integer, the number
is equal to the number of -permutations from a set of items, that is, the number of ways of choosing an ordered list of length consisting of distinct elements drawn from a collection of size
. For example,
is the number of different podiums—assignments of gold, silver, and bronze medals—possible in an eight-person race. On the other hand,
is "the number of ways to arrange
flags on
flagpoles",
[8] where all flags must be used and each flagpole can have any number of flags. Equivalently, this is the number of ways to partition a set of size
(the flags) into
distinguishable parts (the poles), with a linear order on the elements assigned to each part (the order of the flags on a given pole).
Properties
The rising and falling factorials are simply related to one another:
Falling and rising factorials of integers are directly related to the ordinary factorial:
Rising factorials of half integers are directly related to the double factorial:
The falling and rising factorials can be used to express a binomial coefficient:
Thus many identities on binomial coefficients carry over to the falling and rising factorials.
The rising and falling factorials are well defined in any unital ring, and therefore
can be taken to be, for example, a
complex number, including negative integers, or a
polynomial with complex coefficients, or any
complex-valued function.
Real numbers and negative n
The falling factorial can be extended to real values of
using the
gamma function provided
and
are real numbers that are not negative integers:
and so can the rising factorial:
Calculus
Falling factorials appear in multiple differentiation of simple power functions:
The rising factorial is also integral to the definition of the hypergeometric function: The hypergeometric function is defined for
by the
power seriesprovided that
. Note, however, that the hypergeometric function literature typically uses the notation
for rising factorials.
Connection coefficients and identities
Falling and rising factorials are closely related to Stirling numbers. Indeed, expanding the product reveals Stirling numbers of the first kind
And the inverse relations uses Stirling numbers of the second kind
The falling and rising factorials are related to one another through the Lah numbers :[9]
Since the falling factorials are a basis for the polynomial ring, one can express the product of two of them as a linear combination of falling factorials:[10]
The coefficients
\tbinom{m}{k}\tbinom{n}{k}k!
are called
connection coefficients, and have a combinatorial interpretation as the number of ways to identify (or "glue together") elements each from a set of size and a set of size .
There is also a connection formula for the ratio of two rising factorials given by
Additionally, we can expand generalized exponent laws and negative rising and falling powers through the following identities:[11]
Finally, duplication and multiplication formulas for the falling and rising factorials provide the next relations:
Relation to umbral calculus
} f(x1)-f(x), and which is formally similar to
Taylor's theorem:
In this formula and in many other places, the falling factorial
in the calculus of
finite differences plays the role of
in differential calculus. Note for instance the similarity of
to
.
A similar result holds for the rising factorial and the backward difference operator.
The study of analogies of this type is known as umbral calculus. A general theory covering such relations, including the falling and rising factorial functions, is given by the theory of polynomial sequences of binomial type and Sheffer sequences. Falling and rising factorials are Sheffer sequences of binomial type, as shown by the relations:
where the coefficients are the same as those in the binomial theorem.
Similarly, the generating function of Pochhammer polynomials then amounts to the umbral exponential,
since
Alternative notations
An alternative notation for the rising factorial
and for the falling factorial
goes back to A. Capelli (1893) and L. Toscano (1939), respectively.[2] Graham, Knuth, and Patashnik[11] propose to pronounce these expressions as "
to the
rising" and "
to the
falling", respectively.
An alternative notation for the rising factorial
is the less common
. When
is used to denote the rising factorial, the notation
is typically used for the ordinary falling factorial, to avoid confusion.
Generalizations
The Pochhammer symbol has a generalized version called the generalized Pochhammer symbol, used in multivariate analysis. There is also a -analogue, the -Pochhammer symbol.
For any fixed arithmetic function
and symbolic parameters,, related generalized factorial products of the form
may be studied from the point of view of the classes of generalized Stirling numbers of the first kind defined by the following coefficients of the powers of in the expansions of and then by the next corresponding triangular recurrence relation:
These coefficients satisfy a number of analogous properties to those for the Stirling numbers of the first kind as well as recurrence relations and functional equations related to the -harmonic numbers,[12]
See also
Notes and References
- Book: Steffensen, J.F. . Johan Frederik Steffensen . 17 March 2006 . Interpolation . Dover Publications . 2nd . 0-486-45009-0 . 8. — A reprint of the 1950 edition by Chelsea Publishing.
- Book: Knuth, D.E. . Donald Knuth . . 3rd . 1 . 50.
- Knuth . D.E. . Donald Knuth . 1992 . Two notes on notation . . 99 . 5 . 403–422 . math/9205211 . 10.2307/2325085 . 2325085 . 119584305. The remark about the Pochhammer symbol is on page 414.
- Book: Olver, P.J. . Peter J. Olver . 1999 . Classical Invariant Theory . Cambridge University Press . 0-521-55821-2 . 1694364 . 101.
- Book: Harris . Hirst . Mossinghoff . 2008 . Combinatorics and Graph Theory . Springer . 978-0-387-79710-6 . ch. 2.
- Book: Abramowitz, Milton . Stegun, Irene A. . December 1972 . June 1964 . Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables . Abramowitz and Stegun . Washington, DC . . National Bureau of Standards Applied Mathematics Series . 55 . 64-60036 . p. 256 eqn. 6.1.22.
- Book: Slater, Lucy J.
. 1966 . Generalized Hypergeometric Functions . Cambridge University Press . 0201688 . Appendix I. — Gives a useful list of formulas for manipulating the rising factorial in notation.
- Book: Feller
, William . An Introduction to Probability Theory and Its Applications . 1 . Ch. 2.
- Web site: Introduction to the factorials and binomials . Wolfram Functions Site.
- Rosas. Mercedes H.. 2002. Specializations of MacMahon symmetric functions and the polynomial algebra . 246. 1–3. Discrete Math.. 10.1016/S0012-365X(01)00263-1. 285–293. 11441/41678 . free.
- Book: Ronald L. . Graham . Ronald L. Graham . Donald E. . Knuth . Donald E. Knuth . Oren . Patashnik . Oren Patashnik . amp . 1988 . . Addison-Wesley . Reading, MA . 0-201-14236-8 . 47, 48, 52.
- Schmidt . Maxie D. . 1611.04708v2 . 2 . Journal of Integer Sequences . 3779776 . 18.2.7 . Combinatorial identities for generalized Stirling numbers expanding -factorial functions and the -harmonic numbers . 21 . 2018.