Обсуждение:Дискретная математика и алгоритмы

Материал из Викиконспекты
Перейти к: навигация, поиск

Я ЕЩЁ НЕ ДОДЕЛАЛ, ЭТО ЧЕРНОВИК!!!

В математике убывающим факториалом (англ. falling factorial) (иногда называется нисходящим факториалом, постепенно убывающим факториалом или нижним факториалом) обозначают:

[math](x)_{n}=x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)=\prod_{k=1}^{n}(x-(k-1))=\prod_{k=0}^{n-1}(x-k)[/math]

Растущий факториал (rising factorial) (иногда называется функцией Похгаммера, многочленом Похгаммера, восходящим факториалом, постепенно растущим произведением или верхним факториалом) определяется следующей формулой:

[math]x^{(n)}=x^{\overline{n}}=x(x+1)(x+2)\cdots(x+n-1)=\prod_{k=1}^{n}(x+(k-1))=\prod_{k=0}^{n-1}(x+k). [/math]

При n=0 значение принимается равным 1 (пустое произведение).

Символ Похгаммера введен Лео Августом Похгаммером в записи [math](x)^n[/math], где [math]n[/math] неотрицательное целое число. В зависимости от контекста символ Похгаммера может обозначать как растущий факториал, так и падающий факториал как определено выше. Поэтому при чтении любой статьи необходимо обратить внимание на то, какой именно из двух факториалов имеется в виду. Сам Похгаммер для себя использовал [math](x)^n[/math] в другом смысле - для обозначения биномиального коэффициента [math]\tbinom xn[/math].

В этой статье [math](x)_n[/math] означает убывающий факториал и [math](x)^n[/math] - растущий факториал. Такое же обозначение используется в комбинаторике.

Когда [math]x[/math] неотрицательное целое число, [math](x)_n[/math] равняется числу инъективных отображений из множества с [math]n[/math] элементами во множество из [math]x[/math] элементов. Для обозначения этого числа часто применяют обозначения [math]_x P_n[/math] и [math]P(x,n)[/math]. Символ Похгаммера в основном используется в алгебре, где [math]x[/math] - переменная, то есть [math](x)_n[/math] есть ни что иное как многочлен степени [math]n[/math] от [math]x[/math].

Примеры

Несколько первых растущих факториалов:

[math]x^{(0)}=x^{\overline0}=1 [/math]
[math]x^{(1)}=x^{\overline1}=x [/math]
[math]x^{(2)}=x^{\overline2}=x(x+1)=x^2+x [/math]
[math]x^{(3)}=x^{\overline3}=x(x+1)(x+2)=x^3+3x^2+2x [/math]
[math]x^{(4)}=x^{\overline4}=x(x+1)(x+2)(x+3)=x^4+6x^3+11x^2+6x [/math]

Несколько первых убывающих факториалов:

[math](x)_{0}=x^{\underline0}=1 [/math]
[math](x)_{1}=x^{\underline1}=x [/math]
[math](x)_{2}=x^{\underline2}=x(x-1)=x^2-x [/math]
[math](x)_{3}=x^{\underline3}=x(x-1)(x-2)=x^3-3x^2+2x [/math]
[math](x)_{4}=x^{\underline4}=x(x-1)(x-2)(x-3)=x^4-6x^3+11x^2-6x [/math]

Коэффициенты в выражениях являются числами Стирлинга первого рода.

Свойства

Растущий и убывающий факториалы могут быть использованы для обозначения биномиального коэффициента:

[math]\frac{x^{(n)}}{n!} = {x+n-1 \choose n} \quad\mbox{and}\quad \frac{(x)_n}{n!} = {x \choose n}.[/math]

Таким образом, многие свойства биномиальных коэффициентов справедливы для падающих и растущих факториалов.

Растущий факториал может быть выражен как падающий факториал, начинающийся с другого конца,

[math]x^{(n)} = {(x + n - 1)}_n ,[/math]

или как убывающий с противоположным аргументом,

[math]x^{(n)} = {(-1)}^n {(-x)}_{{n}} .[/math]

Убывающий и растущий факториалы определены так же и в любом ассоциативном кольце с единицей и, следовательно, [math]x[/math] может быть даже комплексным числом, многочленом с комплексными коэффициентами или любой функцией определенной на комплексных числах.

Растущий факториал может быть продолжен на вещественные значения [math]n[/math], но с использованием Гаммы функции при условии, что [math]x[/math] и [math]x+n[/math] вещественные числа, но не отрицательные целые:

[math]x^{(n)}=\frac{\Gamma(x+n)}{\Gamma(x)},[/math]

то же самое и про убывающий факториал:

[math](x)_n=\frac{\Gamma(x+1)}{\Gamma(x-n+1)}.[/math]

Если [math]D[/math] означает производную по [math]x[/math], то

[math]D^n(x^a) = (a)_n\,\, x^{a-n}.[/math]

Связующие коэффициенты и тождества

The falling and rising factorials are related to one another through the Lah numbers and through sums for integral powers of a variable [math]x[/math] involving the Stirling numbers of the second kind in the following forms where [math]\binom{r}{k} = r^{\underline{k}} / k![/math]:[1]

[math] \begin{align} x^{\underline{n}} & = \sum_{k=1}^n \binom{n-1}{k-1} \frac{n!}{k!} \times (x)_k \\ & = (-1)^n (-x)_n = (x-n+1)_n = \frac{1}{(x+1)^{\overline{-n}}} \\ (x)_n & = \sum_{k=0}^{n} \binom{n}{k} (n-1)^{\underline{n-k}} \times x^{\underline{k}} \\ & = (-1)^n (-x)^{\underline{n}} = (x+n-1)^{\underline{n}} = \frac{1}{(x-1)^{\underline{-n}}} \\ & = \binom{-x}{n} (-1)^n n! \\ & = \binom{x+n-1}{n} n! \\ x^n & = \sum_{k=0}^{n} \left\{\begin{matrix} n \\ n-k \end{matrix} \right\} x^{\underline{n-k}} \\ & = \sum_{k=0}^{n} \left\{\begin{matrix} n \\ k \end{matrix} \right\}(-1)^{n-k} (x)_k. \end{align} [/math]

Since the falling factorials are a basis for the polynomial ring, we can re-express the product of two of them as a linear combination of falling factorials:

[math](x)_m (x)_n = \sum_{k=0}^m {m \choose k} {n \choose k} k!\, (x)_{m+n-k}.[/math]

The coefficients of the (x)m+nk, called connection coefficients, have a combinatorial interpretation as the number of ways to identify (or glue together) Шаблон:Math elements each from a set of size Шаблон:Math and a set of size Шаблон:Math. We also have a connection formula for the ratio of two Pochhammer symbols given by

[math]\frac{(x)_n}{(x)_i} = (x+i)_{n-i},\ n \geq i. [/math]

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

[math]x^{\underline{m+n}} & = x^{\underline{m}} (x-m)^{\underline{n}}[/math]
[math](x)_{m+n} & = (x)_m (x+m)_n[/math]
[math](x)_{-n} & = \frac{1}{(x-n)_n} = \frac{1}{(x-1)^{\underline{n}}}[/math]
[math]x^{\underline{-n}} & = \frac{1}{(x+1)_n} = \frac{1}{n! \binom{x+n}{n}} = \frac{1}{(x+1)(x+2) \cdots (x+n)}[/math]

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

[math](x)_{k+mn} = (x)_k m^{mn} \prod_{j=0}^{m-1} \left(\frac{x+j+k}{m}\right)_n,\ m \in \mathbb{N} [/math]
[math](ax+b)_n = x^n \prod_{k=0}^{x-1} \left(a+\frac{b+k}{x}\right)_{n/x},\ x \in \mathbb{Z}^{+} [/math]
[math](2x)_{2n} = 2^{2n} (x)_n \left(x+\frac{1}{2}\right)_n. [/math]

Альтернативные формы записи

Альтернативная форма записи растущего факториала

[math]x^{\overline{m}}=\overbrace{x(x+1)\ldots(x+m-1)}^{m~\mathrm{factors}}\qquad\mbox{for integer }m\ge0,[/math]

и для убывающего факториала

[math]x^{\underline{m}}=\overbrace{x(x-1)\ldots(x-m+1)}^{m~\mathrm{factors}}\qquad\mbox{for integer }m\ge0;[/math]

goes back to A. Capelli (1893) and L. Toscano (1939), respectively.[2] Graham, Knuth and Patashnik[3] 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.

Другие формы записи убывающего факториала: [math]P(x,n)[/math], [math]^x P_n[/math], ,[math]P_{x,n}[/math] или [math]_x P_n[/math].

Другое обозначение растущего факториала [math]x^(n)[/math] реже встречается, чем [math](x)^+_n[/math]. Обозначение [math](x)^+_n[/math] используется для растущего факториала, запись [math](x)^-_n[/math] обычно применяется для обозначения убывающего факториала для избежания недоразумений.

Обобщения

The Pochhammer symbol has a generalized version called the generalized Pochhammer symbol, used in multivariate analysis. There is also a q-analogue, the q-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:

[math][f(x)]^{k/-h}=f(x)\cdot f(x-h)\cdot f(x-2h)\cdots f(x-(k-1)h),[/math]

where Шаблон:Math is the decrement and Шаблон:Math is the number of factors. The corresponding generalization of the rising factorial is

[math][f(x)]^{k/h}=f(x)\cdot f(x+h)\cdot f(x+2h)\cdots f(x+(k-1)h).[/math]

This notation unifies the rising and falling factorials, which are [x]k/1 and [x]k/−1, respectively.

For any fixed arithmetic function [math]f: \mathbb{N} \rightarrow \mathbb{C}[/math] and symbolic parameters [math]x, t[/math], related generalized factorial products of the form

[math](x)_{n,f,t} := \prod_{k=1}^{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 [math]x[/math] in the expansions of [math](x)_{n,f,t}[/math] and then by the next corresponding triangular recurrence relation:

[math] \begin{align} \left[\begin{matrix} n \\ k \end{matrix} \right]_{f,t} & = [x^{k-1}] (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 f-harmonic numbers, [math]F_n^{(r)}(t) := \sum_{k \leq n} t^k / f(k)^r[/math].[4]

Источники материала

  • Шаблон:Cite web
  • According to Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., p. 50.
  • Ronald L. Graham, Donald E. Knuth and Oren Patashnik in their book Concrete Mathematics (1988), Addison-Wesley, Reading MA. Шаблон:ISBN, pp. 47,48
  • Combinatorial Identities for Generalized Stirling Numbers Expanding f-Factorial Functions and the f-Harmonic Numbers (2016).
  • Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Дискретная_математика_и_алгоритмы&oldid=61987»