{{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 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. 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. 256 eqn. 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 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 {{mvar|n}}-permutations (sequences of distinct elements) from an {{mvar|x}}-element set, or equivalently the number of injective functions 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 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 {{slink|#Connection coefficients and identities}} below.
When the variable <math>x</math> is a positive integer, the number <math>(x)_n</math> is equal to the number of {{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>
A useful identity for the sums of falling factorials is<ref name="CMath">{{cite book |last1=Graham |first1=Ronald L. |last2=Knuth |first2=Donald Ervin |last3=Patashnik |first3=Oren |title=Concrete mathematics: a foundation for computer science |date=1994 |publisher=Addison-Wesley |location=Reading, Mass |isbn=0-201-55802-5 |page=50 |edition=2nd}}</ref> <math display="block"> \sum_{k=0}^{n-1}(k)_m = \frac{(n)_{m+1}}{m+1}. </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, 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.
===Calculus===
Falling factorials appear in multiple 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 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 <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 and multiplication formulas 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 &\neq 0 \\[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 polynomials 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{d}{dx}\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 differences 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{d}{dx}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 polynomial sequences of binomial type and Sheffer sequences. 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!}=(1+t)^x,</math>
since
<math display="block">\ \operatorname\Delta_x (1+t)^x=t\cdot(1+t)^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 \ge 0 </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 "{{mvar|x}} to the {{mvar|m}} rising" and "{{mvar|x}} to the {{mvar|m}} 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 analysis. There is also a {{mvar|q}}-analogue, the {{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 {{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