Falling factorial

In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial

:$\begin (x)_n = x^\underline &= \overbrace^ \\ &= \prod_^n(x-k+1) = \prod_^(x-k) \,. \end$

The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial, (A reprint of the 1950 edition by Chelsea Publishing Co.) rising sequential product, or upper factorial) is defined as

:$\begin x^ = x^\overline &= \overbrace^ \\ &= \prod_^n(x+k-1) = \prod_^(x+k) \,. \end$

The value of each is taken to be 1 (an empty product) when . These symbols are collectively called
factorial powers.

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 $\tbinom xn$.. The remark about the Pochhammer symbol is on page 414.

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, although Knuth's underline and overline notations $x^\underline$ and $x^\overline$ are increasingly popular. 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.

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 ; while gives the number of partitions of a -element set into ''x'' ordered sequences (possibly empty), or the number of ways to arrange ''k'' distinct flags on a row of ''x'' flagpoles.

Examples and combinatorial interpretation

The first few rising factorials are as follows:
:$\begin x^& &=1 \\ x^& &=x \\ x^&=x(x+1)&=x^2+x \\ x^&=x(x+1)(x+2)&=x^3+3x^2+2x \\ x^&=x(x+1)(x+2)(x+3)&=x^4+6x^3+11x^2+6x \end$
The first few falling factorials are as follows:
:$\begin (x)_0& &=1 \\ (x)_1& &=x \\ (x)_2&=x(x-1)&=x^2-x \\ (x)_3&=x(x-1)(x-2)&=x^3-3x^2+2x \\ (x)_4&=x(x-1)(x-2)(x-3)&=x^4-6x^3+11x^2-6x \end$
The coefficients that appear in the expansions are Stirling numbers of the first kind.

When the variable is a positive integer, the number is equal to the number of -permutations from an -set, 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. Also, is "the number of ways to arrange flags on flagpoles", where all flags must be used and each flagpole can have at most one flag. In this context, other notations like , or are also sometimes used.

Properties

The rising and falling factorials are simply related to one another:

:$\begin m^ &= _ &= (-1)^n (-m)_n \\ _n &= ^ &= (-1)^n (-m)^ \end$

The rising and falling factorials are directly related to the ordinary factorial:

:\begin
n! &= 1^ = (n)_n \\ pt(m)_n &= \frac \\ ptm^ &= \frac
\end

The rising and falling factorials can be used to express a binomial coefficient:

:\begin
\frac &= \binom \\ pt\frac &= \binom
\end

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.

The rising factorial can be extended to real values of using the gamma function provided and are real numbers that are not negative integers:

:$x^=\frac\,,$

and so can the falling factorial:

:$(x)_n=\frac\,.$

Falling factorials appear in multiple differentiation of simple power functions:

:$\frac\,x^a = (a)_n x^ \,.$

The rising factorial is also integral to the definition of the hypergeometric function: The hypergeometric function is defined for by the power series

:$_2F_1(a,b;c;z) = \sum_^\infty \frac \frac$

provided that . Note, however, that the hypergeometric function literature typically uses the notation for rising factorials.

Relation to umbral calculus

The falling factorial occurs in a formula which represents polynomials using the forward difference operator $\Delta f(x)\stackrel f(x1)-f(x)$, and which is formally similar to Taylor's theorem:

:$f(x) = \sum_^\infty \frac\,(x)_n.$

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. Rising and falling factorials are Sheffer sequences of binomial type, as shown by the relations:

:\begin
(a + b)^ &= \sum_^n \binom (a)^(b)^ \\ pt(a + b)_n &= \sum_^n \binom (a)_(b)_
\end

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,

:$\sum_^\infty (x)_n \frac = \left(1+t\right)^x \,,$

since

:$\operatorname \Delta_x \left( 1 + t \right)^x = t \, \left( 1 + t \right)^x \,.$

Connection coefficients and identities

The falling and rising factorials are related to one another through the Lah numbers:

:
\begin
(x)_n & = \sum_^n \binom \frac x^ \\
& = (-1)^n (-x)^ = (x-n+1)^ \\ ptx^ & = \sum_^n \binom (n-1)_ (x)_k \\
& = (-1)^n (-x)_n = (x+n-1)_n \,.
\end

The following formulas relate integral powers of a variable through sums using the Stirling numbers of the second kind, notated by curly brackets :
:$\begin x^n & = \sum_^ \begin n \\ k \end (x)_ \\ & = \sum_^n \begin n \\ k \end (-1)^ x^ \,. \end$

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:

:$(x)_m (x)_n = \sum_^m \binom \binom k! \cdot (x)_ \,.$

The coefficients $\tbinom \tbinom 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

:$\frac = (x+i)^ \,,\quad \textn \geq i \,.$

Additionally, we can expand generalized exponent laws and negative rising and falling powers through the following identities:

:
\begin
(x)_ & = (x)_m (x-m)_n = (x)_n (x-n)_m \\ ptx^ & = x^ (x+m)^ = x^ (x+n)^ \\ pt
x^ & = \frac = \frac = \frac = \frac = \frac = \frac = (-n)! \binom \\ pt
(x)_ & = \frac = \frac = \frac = \frac = \frac = \frac = (-n)! \binom \,.
\end

Finally, duplication and multiplication formulas for the falling and rising factorials provide the next relations:

:\begin
x_ &= x^ m^ \prod_^ \left(\frac\right)_\,,& \text m &\in \mathbb \\ ptx^ &= x^ m^ \prod_^ \left(\frac\right)^,& \text m &\in \mathbb \\ pt(ax+b)^ &= x^n \prod_^ \left(a+\frac\right)\,,& \text x &\in \mathbb^+ \\ pt(2x)^ &= 2^ x^ \left(x+\frac\right)^ \,.
\end

Alternative notations

An alternative notation for the rising factorial

:$x^\overline \equiv (x)_ \equiv (x)_m = \overbrace^ \quad \text m\ge0 \,,$

and for the falling factorial

:$x^\underline \equiv (x)_ = \overbrace^ \quad \text m \ge 0 \,;$

goes back to A. Capelli (1893) and L. Toscano (1939), respectively. Graham, Knuth, and Patashnik propose to pronounce these expressions as " to the rising" and " to the falling", respectively.

Other notations for the falling factorial include , , , or . (See permutation and combination.)

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.

A generalization of the falling factorial in which a function is evaluated on a descending arithmetic sequence of integers and the values are multiplied is:

:\bigl (x)\bigr=f(x)\cdot f(x-h)\cdot f(x-2h)\cdots f\bigl(x-(k-1)h\bigr),

where is the decrement and is the number of factors. The corresponding generalization of the rising factorial is

:\bigl (x)\bigr=f(x)\cdot f(x+h)\cdot f(x+2h)\cdots f\bigl(x+(k-1)h\bigr).

This notation unifies the rising and falling factorials, which are and respectively.

For any fixed arithmetic function $f: \mathbb \rarr \mathbb$ and symbolic parameters , , related generalized factorial products of the form

:$(x)_ := \prod_^ \left(x+\frac\right)$

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:

:
\begin
\left begin n \\ k \end \right & = \left ^\right(x)_ \\
& = f(n-1) t^ \left begin n-1 \\ k \end \right + \left begin n-1 \\ k-1 \end \right + \delta_ \delta_.
\end

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,
:$F_n^(t) := \sum_ \frac\,.$

A symmetric generalization can be defined as

:$x^\underline\overline \equiv \frac = x^$

See also

* Pochhammer -symbol
* Vandermonde identity

References

External links

*

Elementary Proofs

{{DEFAULTSORT:Pochhammer Symbol
Gamma and related functions
Factorial and binomial topics
Finite differences
Operations on numbers