Английская Википедия:Falling and rising factorials

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Short description Шаблон:Use American English In mathematics, the falling factorial (sometimes called the descending factorial, 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, 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 . These symbols are collectively called factorial powers.

The Pochhammer symbol, introduced by Leo August Pochhammer, is the notation Шаблон:Math, where Шаблон:Mvar 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 with yet another meaning, namely to denote the binomial coefficient <math>\tbinom{x}{n}.</math>

In this article, the symbol Шаблон:Math is used to represent the falling factorial, and the symbol Шаблон:Math is used for the rising factorial. These conventions are used in combinatorics, although Knuth's underline and overline notations <math>x^\underline{n}</math> and <math>x^\overline{n}</math> 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 Шаблон:Math is used to represent the rising factorial.

When Шаблон:Mvar is a positive integer, Шаблон:Math gives the number of [[k-permutation|Шаблон:Mvar-permutations]] (sequences of distinct elements) from an Шаблон:Mvar-element set, or equivalently the number of injective functions from a set of size Шаблон:Mvar to a set of size Шаблон:Mvar. The rising factorial Шаблон:Math gives the number of partitions of an Шаблон:Mvar-element set into Шаблон:Mvar ordered sequences (possibly empty).Шаблон:Efn

Examples and combinatorial interpretation

The first few falling factorials are as follows: <math display="block"> \begin{array}{rll} (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{array}</math> The first few rising factorials are as follows: <math display="block"> \begin{array}{rll} 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{array}</math> The coefficients that appear in the expansions are Stirling numbers of the first kind (see below).

When the variable Шаблон:Mvar is a positive integer, the number Шаблон:Math is equal to the number of [[k-permutation|Шаблон:Mvar-permutations from a set of Шаблон:Mvar items]], that is, the number of ways of choosing an ordered list of length Шаблон:Mvar consisting of distinct elements drawn from a collection of size Шаблон:Mvar. For example, Шаблон:Math is the number of different podiums—assignments of gold, silver, and bronze medals—possible in an eight-person race. In this context, other notations like Шаблон:Math, Шаблон:Math, Шаблон:Math, or Шаблон:Math are also sometimes used. On the other hand, Шаблон:Math is "the number of ways to arrange Шаблон:Mvar flags on Шаблон:Mvar flagpoles", 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 Шаблон:Mvar (the flags) into Шаблон:Mvar 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{array}{rll} {(x)}_n &= {(x-n+1)}^{(n)} &= (-1)^n (-x)^{(n)},\\ x^{(n)} &= {(x+n-1)}_{n} &= (-1)^n (-x)_n. \end{array}</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, and therefore Шаблон:Mvar 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 falling factorial can be extended to real values of Шаблон:Mvar using the gamma function provided Шаблон:Mvar and Шаблон: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>

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 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 . Note, however, that the hypergeometric function literature typically uses the notation Шаблон: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>:<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: <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 elements each from a set of size Шаблон:Mvar and a set of size Шаблон:Mvar.

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:Шаблон:Rp

<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)} = (-n)! \binom{x-n-1}{-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)} = (-n)! \binom{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 &\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 polynomials using the forward difference operator <math>\Delta f(x)\stackrel{\mathrm{def}}{=} f(x{+}1)-f(x),</math> and which is formally similar to Taylor's theorem: <math display="block"> f(x) = \sum_{n=0}^\infty \frac{\Delta^n f(0)}{n!} (x)_n. </math>

In this formula and in many other places, the falling factorial Шаблон:Math in the calculus of finite differences plays the role of Шаблон:Math in differential calculus. Note for instance the similarity of Шаблон:Math to Шаблон:Math .

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:

<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. Graham, Knuth, and PatashnikШаблон:Rp propose to pronounce these expressions as "Шаблон:Mvar to the Шаблон:Mvar rising" and "Шаблон:Mvar to the Шаблон:Mvar falling", respectively.

Other notations for the falling factorial include Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math, or Шаблон:Math. (See permutation and combination.)

An alternative notation for the rising factorial Шаблон:Math is the less common Шаблон:Math. When Шаблон:Math is used to denote the rising factorial, the notation Шаблон:Math 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 [[q-analog|Шаблон:Mvar-analogue]], the [[q-Pochhammer symbol|Шаблон:Mvar-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:Шаблон:Citation needed <math display="block"> \bigl[f(x)\bigr]^{k/-h}=f(x)\cdot f(x-h)\cdot f(x-2h)\cdots f\bigl(x-(k-1)h\bigr),</math>

where Шаблон:Math is the decrement and Шаблон:Math is the number of factors. The corresponding generalization of the rising factorial is <math display="block"> \bigl[f(x)\bigr]^{k/h}=f(x)\cdot f(x+h)\cdot f(x+2h)\cdots f\bigl(x+(k-1)h\bigr).</math>

This notation unifies the rising and falling factorials, which are Шаблон:Math and Шаблон:Math respectively.

For any fixed arithmetic function <math>f: \mathbb{N} \rarr \mathbb{C}</math> and symbolic parameters Шаблон:Mvar, Шаблон:Mvar, 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 in the expansions of Шаблон:Math 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-harmonic numbers, <math display="block"> F_n^{(r)}(t) := \sum_{k \leq n} \frac{ t^k }{ f(k)^r }\,.</math>

A symmetric generalization can be defined as <math display="block"> x^\underline\overline{m} \equiv \frac{x^\overline{m} x^\underline{m}}{x} = x^{\overline{m} + \underline{m} - 1}.</math>

See also

• [[Pochhammer k-symbol|Pochhammer Шаблон:Mvar-symbol]]
• Vandermonde identity

External links

• Шаблон:MathWorld
• Шаблон:Cite web — Elementary proofs