Falling and rising factorial

In mathematics, the falling or rising factorial denotes a function similar to exponentiation , but in which the factors fall or rise gradually, i.e. i.e., be reduced or increased by one.

definition

For natural numbers and with the -th decreasing or increasing factorial is noted as or (in some older textbooks also or ) and is defined as follows: ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n\geq k\geq 0}$ ${\displaystyle k}$ ${\displaystyle n^{\underline {k}}}$ ${\displaystyle n^{\overline {k}}}$ ${\displaystyle (n)_{k}}$ ${\displaystyle n^{(k)}}$

${\displaystyle n^{\underline {k}}:=n(n-1)(n-2)\cdots (n-k+1)={\frac {n!}{(n-k)!}}}$

${\displaystyle n^{\overline {k}}:=n(n+1)(n+2)\cdots (n+k-1)={\frac {(n+k-1)!}{(n-1)!}}}$

Combinatorial interpretation

In the urn model , the falling factorial can be interpreted as the number of possibilities to remove balls from an urn with different balls , without replacing them, taking into account the sequence. There are candidates for the first ball , for the second ... and finally for the last ball . There are therefore options for the overall selection . ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-k+1}$ ${\displaystyle n(n-1)\cdots (n-k+1)=n^{\underline {k}}}$

In general, the number of - permutations of a - set or, alternatively, the number of injective mappings of a - set into a - set. ${\displaystyle n^{\underline {k}}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$

generalization

The definition is analogous for a complex number and a natural number : ${\displaystyle x}$ ${\displaystyle k}$

${\displaystyle x^{\underline {k}}:=x(x-1)(x-2)\cdots (x-k+1)}$

${\displaystyle x^{\overline {k}}:=x(x+1)(x+2)\cdots (x+k-1)}$

One can then understand and as complex polynomials in . ${\displaystyle x^{\underline {k}}}$ ${\displaystyle x^{\overline {k}}}$ ${\displaystyle x}$

For the increasing factorial corresponds to the Pochhammer symbol . ${\displaystyle x\in \mathbb {N} }$ ${\displaystyle x^{\overline {k}}}$ ${\displaystyle (x,k)}$

properties

Calculation rules

The following calculation rules apply:

${\displaystyle x^{\underline {1}}=x^{\overline {1}}=x}$

${\displaystyle x^{\underline {0}}=x^{\overline {0}}=1}$

${\displaystyle (-x)^{\overline {k}}=(-1)^{k}x^{\underline {k}}}$

${\displaystyle x^{\underline {k}}=(-x)^{\overline {k}}=0}$  For ${\displaystyle 0\leq x<k}$

Relationships with other known numbers

With the help of the falling factorials, the binomial coefficients can be defined in general:

${\displaystyle {\binom {x}{k}}:={\frac {1}{k!}}x^{\underline {k}}}$

The following equations also apply, where and denote the (unsigned) Stirling numbers of the first and second kind: ${\displaystyle \displaystyle \left[{n \atop k}\right]}$ ${\displaystyle \displaystyle \left\{\!{n \atop k}\!\right\}}$

${\displaystyle \displaystyle x^{k}=\sum _{j=-\infty }^{\infty }\left\{\!{k \atop j}\!\right\}\cdot x^{\underline {j}}}$

${\displaystyle \displaystyle x^{k}=\sum _{j=-\infty }^{\infty }(-1)^{k-j}\left\{{k \atop j}\right\}\cdot x^{\overline {j}}}$

${\displaystyle \displaystyle x^{\overline {k}}=\sum _{j=-\infty }^{\infty }\left[{k \atop j}\right]\cdot x^{j}}$

${\displaystyle \displaystyle x^{\underline {k}}=\sum _{j=-\infty }^{\infty }(-1)^{k-j}\left[{k \atop j}\right]\cdot x^{j}}$

Occurrence in analysis

${\displaystyle {{\operatorname {d} ^{j}} \over \operatorname {d} \!x^{j}}x^{k}=k^{\underline {j}}x^{k-j}}$

literature

• Martin Aigner : Discrete Mathematics . Vieweg + Teubner, Wiesbaden 2009, ISBN 978-3-8348-0084-8 .
• Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Elements of discrete mathematics. Numbers and counting, graphs and associations . De Gruyter, Berlin 2013, ISBN 978-3-11-027767-8 .
• Ronald L. Graham , Donald E. Knuth , Oren Patashnik : Concrete mathematics. A foundation for computer science. Second edition . Addison-Wesley, 1994, ISBN 978-0-201-55802-9 .