Editing Falling and rising factorials

{{Short description|Mathematical functions}}
{{Use American English|date = March 2019}}
{{Redirect|Rising power|the description of a sovereign state or union of states with significant rising influence in global affairs|emerging power}}
In [[mathematics]], the '''falling factorial''' (sometimes called the '''descending factorial''',<ref name=Steffensen/> '''falling sequential product''', or '''lower factorial''') is defined as the polynomial
<math display="block">
\begin{align}
(x)_n = x^\underline{n} &= \overbrace{x(x-1)(x-2)\cdots(x-n+1)}^{n\text{ factors}} \\
&= \prod_{k=1}^n(x-k+1) = \prod_{k=0}^{n-1}(x-k) .
\end{align}</math>

The '''rising factorial''' (sometimes called the '''Pochhammer function''', '''Pochhammer polynomial''', '''ascending factorial''',<ref name=Steffensen>
{{cite book
 | last = Steffensen | first = J.F. | author-link = Johan Frederik Steffensen
 | date = 17 March 2006
 | title = Interpolation
 | publisher = Dover Publications | edition = 2nd
 | isbn = 0-486-45009-0
 | page = 8
}} — A reprint of the 1950 edition by Chelsea Publishing.
</ref> '''rising sequential product''', or '''upper factorial''') is defined as
<math display="block">
\begin{align}
x^{(n)} = x^\overline{n} &= \overbrace{x(x+1)(x+2)\cdots(x+n-1)}^{n\text{ factors}} \\
&= \prod_{k=1}^n(x+k-1) = \prod_{k=0}^{n-1}(x+k) .
\end{align}</math>

The value of each is taken to be 1 (an [[empty product]]) when <math>n=0</math>. These symbols are collectively called '''factorial powers'''.<ref name="The Art of Computer Programming">
{{cite book
 |last=Knuth |first=D.E. |author-link=Donald Knuth
 |title=[[The Art of Computer Programming]] |edition=3rd
 |volume=1 |page=50
}}
</ref>

The '''Pochhammer symbol''', introduced by [[Leo August Pochhammer]], is the notation <math>(x)_n</math>, where {{mvar|n}} 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 <math>(x)_n</math> with yet another meaning, namely to denote the [[binomial coefficient]] <math>\tbinom{x}{n}</math>.<ref name=Knuth>
{{cite journal
 |last=Knuth |first=D.E.  |author-link=Donald Knuth
 |year=1992
 |title=Two notes on notation
 |journal=[[American Mathematical Monthly]]
 |volume=99 |issue=5 |pages=403–422
 |arxiv=math/9205211 |doi=10.2307/2325085
 |jstor=2325085 |s2cid=119584305
}} The remark about the Pochhammer symbol is on page 414.
</ref>

In this article, the symbol <math>(x)_n</math> is used to represent the falling factorial, and the symbol <math>x^{(n)}</math> is used for the rising factorial. These conventions are used in [[combinatorics]],<ref>
{{cite book
 |last=Olver |first=P.J. |author-link=Peter J. Olver
 |year=1999
 |title=Classical Invariant Theory
 |publisher=Cambridge University Press
 |isbn=0-521-55821-2 |mr=1694364
 |page=101
}}
</ref>
although [[Donald Knuth|Knuth]]'s underline and overline notations <math>x^\underline{n}</math> and <math>x^\overline{n}</math> are increasingly popular.<ref name="The Art of Computer Programming"/><ref>
{{cite book
 |last1=Harris
 |last2=Hirst
 |last3=Mossinghoff
 |year=2008
 |title=Combinatorics and Graph Theory 
 |publisher=Springer
 |isbn=978-0-387-79710-6
 |at=ch.&nbsp;2
}}
</ref>
In the theory of [[special functions]] (in particular the [[hypergeometric function]]) and in the standard reference work ''[[Abramowitz and Stegun]]'', the Pochhammer symbol <math>(x)_n</math> is used to represent the rising factorial.<ref>
{{cite book
 |editor1=Abramowitz, Milton
 |editor2=Stegun, Irene A.
 |date=December 1972  |orig-date=June 1964
 |title=Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables
 |title-link=Abramowitz and Stegun
 |place=Washington, DC
 |publisher=[[United States Department of Commerce]]
 |series=[[National Bureau of Standards]] [[Applied Mathematics]] Series
 |volume=55
 |lccn=64-60036
 |at=p.&nbsp;256 eqn.&nbsp;6.1.22
}}
</ref><ref>
{{cite book
 |last=Slater |first=Lucy J.
 |year=1966
 |title=Generalized Hypergeometric Functions
 |publisher=Cambridge University Press
 |mr=0201688 |at=Appendix&nbsp;I
}} — Gives a useful list of formulas for manipulating the rising factorial in {{math|(''x''){{sub|''n''}}}} notation.
</ref>
 
When <math>x</math> is a positive integer, <math>(x)_n</math> gives the number of [[k-permutation|{{mvar|n}}-permutations]] (sequences of distinct elements) from an {{mvar|x}}-element set, or equivalently the number of [[injective function]]s from a set of size <math>n</math> to a set of size <math>x</math>.  The rising factorial <math>x^{(n)}</math> gives the number of [[Partition of a set|partitions]] of an <math>n</math>-element set into <math>x</math> ordered sequences (possibly empty).{{efn|Here the parts are distinct; for example, when {{math|1=''x'' = ''n'' = 2}}, the {{math|1=(2){{sup|(2)}} = 6}} partitions are <math>(12, -)</math>, <math>(21, -)</math>, <math>(1, 2)</math>, <math>(2, 1)</math>, <math>(-, 12)</math>, and <math>(-, 21)</math>, where − denotes an empty part.}}

==Examples and combinatorial interpretation==
The first few falling factorials are as follows:

<math display="block">
\begin{alignat}{2}
(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{alignat}</math>

The first few rising factorials are as follows:

<math display="block">
\begin{alignat}{2}
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{alignat}</math>

The coefficients that appear in the expansions are [[Stirling numbers of the first kind]] (see below).

When the variable <math>x</math> is a positive integer, the number <math>(x)_n</math> is equal to the number of [[k-permutation|{{mvar|n}}-permutations from a set of {{mvar|x}} items]], that is, the number of ways of choosing an ordered list of length {{mvar|n}} consisting of distinct elements drawn from a collection of size <math>x</math>. For example, <math>(8)_3 = 8\times7\times6 = 336</math> is the number of different podiums—assignments of gold, silver, and bronze medals—possible in an eight-person race. On the other hand, <math>x^{(n)}</math> is "the number of ways to arrange <math>n</math> flags on <math>x</math> flagpoles",<ref name=Feller>
{{cite book
 |first=William |last=Feller
 |title=An Introduction to Probability Theory and Its Applications
 |volume=1 |at=Ch. 2
}}
</ref>
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 <math>n</math> (the flags) into <math>x</math> 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:
<math display="block">
\begin{alignat}{2}
{(x)}_n &= {(x-n+1)}^{(n)} &&= (-1)^n (-x)^{(n)},\\
x^{(n)} &= {(x+n-1)}_{n} &&= (-1)^n (-x)_n.
\end{alignat}</math>

Falling and rising factorials of integers are directly related to the ordinary [[factorial]]:
<math display="block">
\begin{align}
n! &= 1^{(n)} = (n)_n,\\[6pt]
(m)_n &= \frac{m!}{(m-n)!},\\[6pt]
m^{(n)} &= \frac{(m+n-1)!}{(m-1)!}.
\end{align}</math>

Rising factorials of half integers are directly related to the [[double factorial]]:
<math display="block">
\begin{align}
\left[\frac{1}{2}\right]^{(n)} = \frac{(2n-1)!!}{2^n},\quad
\left[\frac{2m+1}{2}\right]^{(n)} = \frac{(2(n+m)-1)!!}{2^n(2m-1)!!}.
\end{align}</math>

The falling and rising factorials can be used to express a [[binomial coefficient]]:
<math display="block">
\begin{align}
\frac{(x)_n}{n!} &= \binom{x}{n},\\[6pt]
\frac{x^{(n)}}{n!} &= \binom{x+n-1}{n}.
\end{align}</math>

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|unital]] [[ring (mathematics)|ring]], and therefore <math>x</math> 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 number|real]] values of <math>x</math> using the [[gamma function]] provided <math>x</math> and <math>x+n</math> are real numbers that are not negative integers:
<math display="block">
(x)_n = \frac{\Gamma(x+1)}{\Gamma(x-n+1)}\ ,
</math>
and so can the rising factorial:
<math display="block">
x^{(n)} = \frac{\Gamma(x+n)}{\Gamma(x)}\ .
</math>

===Calculus===

Falling factorials appear in multiple [[derivative|differentiation]] of simple power functions:
<math display="block">
\left(\frac{\mathrm{d}}{\mathrm{d}x}\right)^n x^a = (a)_n \cdot x^{a-n}.
</math>

The rising factorial is also integral to the definition of the [[hypergeometric function]]: The hypergeometric function is defined for <math>|z| < 1</math> by the [[power series]]
<math display="block">
{}_2F_1(a,b;c;z) = \sum_{n=0}^\infty \frac{a^{(n)} b^{(n)}}{c^{(n)}}  \frac{z^n}{n!}
</math>
provided that <math>c \neq 0, -1, -2, \ldots</math>. Note, however, that the hypergeometric function literature typically uses the notation <math>(a)_n</math> for rising factorials.

== Connection coefficients and identities ==

Falling and rising factorials are closely related to [[Stirling number|Stirling numbers]]. Indeed, expanding the product reveals [[Stirling numbers of the first kind]]<math display="block">
\begin{align}
(x)_n & = \sum_{k=0}^n s(n,k) x^k \\
      &= \sum_{k=0}^n \begin{bmatrix}n \\ k \end{bmatrix} (-1)^{n-k}x^k \\
x^{(n)} & = \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} x^k \\
\end{align}
</math>

And the inverse relations uses [[Stirling numbers of the second kind]]<math display="block">
\begin{align}
x^n & = \sum_{k=0}^{n} \begin{Bmatrix} n \\ k \end{Bmatrix} (x)_{k} \\
    & = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} (-1)^{n-k} x^{(k)} .
\end{align} 
</math>

The falling and rising factorials are related to one another through the [[Lah numbers|Lah numbers <math display="inline">L(n, k) = \binom{n-1}{k-1} \frac{n!}{k!} </math>]]:<ref name="Wolfram_functions">
{{cite web |title=Introduction to the factorials and binomials |url=http://functions.wolfram.com/GammaBetaErf/Factorial/introductions/FactorialBinomials/05/ |website=Wolfram Functions Site}}
</ref><math display="block">
\begin{align}
x^{(n)} & = \sum_{k=0}^n L(n,k) (x)_k \\
(x)_n & = \sum_{k=0}^n L(n,k) (-1)^{n-k} x^{(k)}
\end{align}
</math>

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:<ref>{{cite journal|last1=Rosas|first1=Mercedes H.|year= 2002|title=Specializations of MacMahon symmetric functions and the polynomial algebra |volume=246|number=1–3|journal=Discrete Math.|doi=10.1016/S0012-365X(01)00263-1|pages=285–293|hdl=11441/41678 |hdl-access=free}}</ref>
<math display="block">
(x)_m (x)_n = \sum_{k=0}^m \binom{m}{k} \binom{n}{k} k! \cdot (x)_{m+n-k} \ .</math>

The coefficients <math>\tbinom{m}{k} \tbinom{n}{k} k! </math> are called ''connection coefficients'', and have a combinatorial interpretation as the number of ways to identify (or "glue together") {{mvar|k}} elements each from a set of size {{mvar|m}} and a set of size {{mvar|n}}.

There is also a connection formula for the ratio of two rising factorials given by
<math display="block">
\frac{x^{(n)}}{x^{(i)}} = (x+i)^{(n-i)} ,\quad \text{for }n \geq i .</math>

Additionally, we can expand generalized exponent laws and negative rising and falling powers through the following identities:<ref name="Graham-Knuth-Patashnik-1988">
{{cite book
 |first1=Ronald L. |last1=Graham    |author1-link=Ronald L. Graham
 |first2=Donald E. |last2=Knuth     |author2-link=Donald E. Knuth
 |first3=Oren      |last3=Patashnik |author3-link=Oren Patashnik
 |name-list-style=amp
 |year=1988
 |title=[[Concrete Mathematics]]
 |publisher=Addison-Wesley
 |place=Reading, MA
 |isbn=0-201-14236-8
 |pages=47, 48, 52
}}
</ref>{{rp|style=ama|p= 52}}

<math display="block">
\begin{align} 
(x)_{m+n} & = (x)_m (x-m)_n = (x)_n (x-n)_m \\[6pt]
x^{(m+n)} & = x^{(m)} (x+m)^{(n)} = x^{(n)} (x+n)^{(m)} \\[6pt]
x^{(-n)} & = \frac{\Gamma(x-n)}{\Gamma(x)} = \frac{(x-n-1)!}{(x-1)!} = \frac{1}{(x-n)^{(n)}} = \frac{1}{(x-1)_n} = \frac{1}{(x-1)(x-2) \cdots (x-n)} \\[6pt]
(x)_{-n} & = \frac{\Gamma(x+1)}{\Gamma(x+n+1)} = \frac{x!}{(x+n)!} = \frac{1}{(x+n)_n} = \frac{1}{(x+1)^{(n)}} = \frac{1}{(x+1)(x+2) \cdots (x+n)}
\end{align} 
</math>

Finally, [[duplication formula|duplication]] and [[multiplication formula]]s for the falling and rising factorials provide the next relations:
<math display="block">
\begin{align}
(x)_{k+mn} &= x^{(k)} m^{mn} \prod_{j=0}^{m-1} \left(\frac{x-k-j}{m}\right)_{n}\,,& \text{for } m &\in \mathbb{N} \\[6pt]
x^{(k+mn)} &= x^{(k)} m^{mn} \prod_{j=0}^{m-1} \left(\frac{x+k+j}{m}\right)^{(n)},& \text{for } m &\in \mathbb{N} \\[6pt]
(ax+b)^{(n)} &= x^n \prod_{j=0}^{n-1} \left(a+\frac{b+j}{x}\right),& \text{for } x &\in \mathbb{Z}^+ \\[6pt]
(2x)^{(2n)} &= 2^{2n} x^{(n)} \left(x+\frac{1}{2}\right)^{(n)} .
\end{align}</math>

==Relation to umbral calculus==
The falling factorial occurs in a formula which represents [[polynomial]]s using the forward [[difference operator]] <math>\ \operatorname\Delta f(x) ~ \stackrel{\mathrm{def}}{=} ~ f(x{+}1) - f(x)\ ,</math> which in form is an exact analogue to [[Taylor's theorem]]: Compare the series expansion from [[umbral calculus]]
:<math display="block">\qquad
f(t) = \sum_{n=0}^\infty\ \frac{ 1 }{\ n! }\operatorname{\Delta}_x^n f(x)\bigg\vert_{x = 0}\ (t)_n \qquad
</math>
with the corresponding series from [[differential calculus]]
:<math display="block">\qquad
f(t) = \sum_{n=0}^\infty\ \frac{ 1 }{\ n! } \left[\frac{\ \operatorname{d} }{ \operatorname{d} x }\right]^n f(x)\ \bigg\vert_{x = 0} \ t^n 
~.</math>

In this formula and in many other places, the falling factorial <math>\ (x)_n\ </math> in the calculus of [[finite difference]]s plays the role of <math>\ x^n\ </math> in differential calculus. For another example, note the similarity of <math>~ \operatorname\Delta (x)_n = n\ (x)_{n-1} ~</math> to <math>~ \frac{\ \operatorname{d} }{ \operatorname{d} x }\ x^n = n\ x^{n-1} ~.</math>

A corresponding relation 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 [[binomial type|polynomial sequences of binomial type]] and [[Sheffer sequence]]s. Falling and rising factorials are Sheffer sequences of binomial type, as shown by the relations:

<math display="block">
\ \begin{align}
(a + b)_n &= \sum_{j=0}^n\ \binom{n}{j}\ (a)_{n-j}\ (b)_{j}\   \\[6pt]
(a + b)^{(n)} &= \sum_{j=0}^n\ \binom{n}{j}\ a^{(n-j)}\ b^{(j)}\ 
\end{align}\ </math>

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,

<math display="block">\ \sum_{n=0}^\infty\ (x)_n\ \frac{~ t^n\ }{\ n! }\ =\ \left(\ 1 + t\ \right)^x\ ,</math>

since

<math display="block">\ \operatorname\Delta_x \left(\ 1 + t\ \right)^x\ =\ t \cdot \left(\ 1 + t\ \right)^x ~.</math>

==Alternative notations==
An alternative notation for the rising factorial
<math display="block">
x^\overline{m} \equiv (x)_{+m} \equiv (x)_m = \overbrace{x(x+1)\ldots(x+m-1)}^{m \text{ factors}} \quad \text{for integer } m\ge0 </math>

and for the falling factorial
<math display="block">
x^\underline{m} \equiv (x)_{-m} = \overbrace{x(x-1)\ldots(x-m+1)}^{m \text{ factors}} \quad \text{for integer } m \ge 0</math>

goes back to A. Capelli (1893) and L. Toscano (1939), respectively.<ref name="The Art of Computer Programming"/> Graham, Knuth, and Patashnik<ref name=Graham-Knuth-Patashnik-1988/>{{rp|style=ama|pp= 47, 48}}
propose to pronounce these expressions as "<math>x</math> to the <math>m</math> rising" and "<math>x</math> to the <math>m</math> falling", respectively.

An alternative notation for the rising factorial <math>x^{(n)}</math> is the less common <math>(x)_n^+</math>. When <math>(x)_n^+</math> is used to denote the rising factorial, the notation <math>(x)_n^-</math> is typically used for the ordinary falling factorial, to avoid confusion.<ref name="Knuth" />

==Generalizations==
The Pochhammer symbol has a generalized version called the [[generalized Pochhammer symbol]], used in multivariate [[Mathematical analysis|analysis]]. There is also a [[q-analog|{{mvar|q}}-analogue]], the [[q-Pochhammer symbol|{{mvar|q}}-Pochhammer symbol]].

For any fixed arithmetic function <math>f: \mathbb{N} \rarr \mathbb{C}</math> and symbolic parameters {{mvar|x}}, {{mvar|t}}, related generalized factorial products of the form

<math display="block">
(x)_{n,f,t} := \prod_{k=0}^{n-1} \left(x+\frac{f(k)}{t^k}\right)</math>

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 {{mvar|x}} in the expansions of {{math|(''x'')<sub>''n'',''f'',''t''</sub>}} and then by the next corresponding triangular recurrence relation:

<math display="block">
\begin{align} 
\left[\begin{matrix} n \\ k \end{matrix} \right]_{f,t} & = \left[x^{k-1}\right] (x)_{n,f,t} \\ 
     & = f(n-1) t^{1-n} \left[\begin{matrix} n-1 \\ k \end{matrix} \right]_{f,t} + \left[\begin{matrix} n-1 \\ k-1 \end{matrix} \right]_{f,t} + \delta_{n,0} \delta_{k,0}. 
\end{align} 
</math>

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 {{mvar|f}}-harmonic numbers,<ref>{{cite journal
 | last = Schmidt | first = Maxie D.
 | arxiv = 1611.04708v2
 | issue = 2
 | journal = Journal of Integer Sequences
 | mr = 3779776
 | article-number = 18.2.7
 | title = Combinatorial identities for generalized Stirling numbers expanding {{mvar|f}}-factorial functions and the {{mvar|f}}-harmonic numbers
 | volume = 21
 | year = 2018}}</ref>
<math display="block">
F_n^{(r)}(t) := \sum_{k \leq n} \frac{ t^k }{ f(k)^r }\,.</math>

==See also==
*[[Pochhammer k-symbol|Pochhammer {{mvar|k}}-symbol]]
*[[Vandermonde identity]]

==References==
{{notelist}}
{{reflist|25em}}

==External links==
* {{MathWorld |title=Pochhammer Symbol |urlname=PochhammerSymbol}}

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