Изменения

Перейти к: навигация, поиск

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

12 577 байт добавлено, 00:58, 8 октября 2017
Символ Похгаммера: Новая тема
#* Пробел после запятой, разделяющей аргументы функции
#* Используем какой-то определённый стиль именования переменных(я бы рекомендовал lowerCamelCase для переменных и функций и UpperCamelCase для классов)
 
== Символ Похгаммера ==
 
В математике '''убывающим факториалом''' (falling factorial) (иногда называется '''нисходящим факториалом''', '''постепенно убывающим факториалом''' или '''нижним факториалом''' (descending factorial, falling sequential product или lower factorial)) обозначают:
 
:<tex>(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)</tex>
 
'''Растущий факториал''' (rising factorial) (иногда называется '''функцией Похгаммера''', '''многочленом Похгаммера''', '''восходящим факториалом''', '''постепенно растущим произведением''' или '''верхним факториалом''' (Pochhammer function, Pochhammer polynomial, ascending factorial, rising sequential product или upper 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 (пустое произведение).
 
'''Символ Похгаммера''' введен Лео Августом Похгаммером в записи <tex>(x)^n</tex>, где <tex>n</tex> неотрицательное целое число. В зависимости от контекста символ Похгаммера может обозначать как растущий факториал, так и падающий факториал как определено выше. Поэтому при чтении любой статьи необходимо обратить внимание на то, какой именно из двух факториалов имеется в виду. Сам Похгаммер для себя использовал <tex>(x)^n</tex> в другом смысле - для обозначения биномиального коэффициента <tex>\tbinom xn</tex>.
 
В этой статье <tex>(x)_n</tex> означает убывающий факториал и <tex>(x)^n</tex> - растущий факториал. Такое же обозначение используется в комбинаторике.
 
Когда <tex>x</tex> неотрицательное целое число, <tex>(x)_n</tex> равняется числу инъективных отображений из множества с <tex>n</tex> элементами во множество из <tex>x</tex> элементов. Для обозначения этого числа часто применяют обозначения <tex>_x P_n</tex> и <tex>P(x,n)</tex>. Символ Похгаммера в основном используется в алгебре, где <tex>x</tex> - переменная, то есть <tex>(x)_n</tex> есть ни что иное как многочлен степени <tex>n</tex> от <tex>x</tex>.
 
==Примеры==
Несколько первых растущих факториалов:
:<tex>x^{(0)}=x^{\overline0}=1 </tex>
:<tex>x^{(1)}=x^{\overline1}=x </tex>
:<tex>x^{(2)}=x^{\overline2}=x(x+1)=x^2+x </tex>
:<tex>x^{(3)}=x^{\overline3}=x(x+1)(x+2)=x^3+3x^2+2x </tex>
:<tex>x^{(4)}=x^{\overline4}=x(x+1)(x+2)(x+3)=x^4+6x^3+11x^2+6x </tex>
Несколько первых убывающих факториалов:
:<tex>(x)_{0}=x^{\underline0}=1 </tex>
:<tex>(x)_{1}=x^{\underline1}=x </tex>
:<tex>(x)_{2}=x^{\underline2}=x(x-1)=x^2-x </tex>
:<tex>(x)_{3}=x^{\underline3}=x(x-1)(x-2)=x^3-3x^2+2x </tex>
:<tex>(x)_{4}=x^{\underline4}=x(x-1)(x-2)(x-3)=x^4-6x^3+11x^2-6x </tex>
Коэффициенты в выражениях являются числами Стирлинга первого рода.
 
==Свойства==
Растущий и убывающий факториалы могут быть использованы для обозначения биномиального коэффициента:
 
:<tex>\frac{x^{(n)}}{n!} = {x+n-1 \choose n} \quad\mbox{and}\quad \frac{(x)_n}{n!} = {x \choose n}.</tex>
 
Таким образом, многие свойства биномиальных коэффициентов справедливы для падающих и растущих факториалов.
 
Растущий факториал может быть выражен как падающий факториал, начинающийся с другого конца,
 
:<tex>x^{(n)} = {(x + n - 1)}_n ,</tex>
 
или как убывающий с противоположным аргументом,
 
:<tex>x^{(n)} = {(-1)}^n {(-x)}_{{n}} .</tex>
 
Убывающий и растущий факториалы определены так же и в любом ассоциативном кольце с единицей и, следовательно, <tex>x</tex> может быть даже комплексным числом, многочленом с комплексными коэффициентами или любой функцией определенной на комплексных числах.
 
Растущий факториал может быть продолжен на вещественные значения <tex>n</tex>, но с использованием Гаммы функции при условии, что <tex>x</tex> и <tex>x+n</tex> вещественные числа, но не отрицательные целые:
 
:<tex>x^{(n)}=\frac{\Gamma(x+n)}{\Gamma(x)},</tex>
 
то же самое и про убывающий факториал:
 
:<tex>(x)_n=\frac{\Gamma(x+1)}{\Gamma(x-n+1)}.</tex>
 
Если <tex>D</tex> означает производную по <tex>x</tex>, то
 
:<tex>D^n(x^a) = (a)_n\,\, x^{a-n}.</tex>
 
== Связующие коэффициенты и тождества ==
 
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>:<ref>{{cite web|title=Introduction to the factorials and binomials|url=http://functions.wolfram.com/GammaBetaErf/Factorial/introductions/FactorialBinomials/05/|website=Wolfram Functions Site}}</ref>
 
:<tex>
\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}
</tex>
 
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:
 
:<tex>(x)_m (x)_n = \sum_{k=0}^m {m \choose k} {n \choose k} k!\, (x)_{m+n-k}.</tex>
 
The coefficients of the (''x'')<sub>''m''+''n''&minus;''k''</sub>, called '''connection coefficients''', have a combinatorial interpretation as the number of ways to identify (or glue together) {{math|''k''}} elements each from a set of size {{math|''m''}} and a set of size {{math|''n''}}.
We also have a connection formula for the ratio of two Pochhammer symbols given by
 
:<tex>\frac{(x)_n}{(x)_i} = (x+i)_{n-i},\ n \geq i. </tex>
 
Additionally, we can expand generalized exponent laws and negative rising and falling powers through the following identities:
:<tex>x^{\underline{m+n}} & = x^{\underline{m}} (x-m)^{\underline{n}}</tex>
:<tex>(x)_{m+n} & = (x)_m (x+m)_n</tex>
:<tex>(x)_{-n} & = \frac{1}{(x-n)_n} = \frac{1}{(x-1)^{\underline{n}}}</tex>
:<tex>x^{\underline{-n}} & = \frac{1}{(x+1)_n} = \frac{1}{n! \binom{x+n}{n}} = \frac{1}{(x+1)(x+2) \cdots (x+n)}</tex>
 
Finally, [[duplication formula|duplication]] and [[multiplication formulas]] for the rising factorials provide the next relations:
 
:<tex>(x)_{k+mn} = (x)_k m^{mn} \prod_{j=0}^{m-1} \left(\frac{x+j+k}{m}\right)_n,\ m \in \mathbb{N} </tex>
:<tex>(ax+b)_n = x^n \prod_{k=0}^{x-1} \left(a+\frac{b+k}{x}\right)_{n/x},\ x \in \mathbb{Z}^{+} </tex>
:<tex>(2x)_{2n} = 2^{2n} (x)_n \left(x+\frac{1}{2}\right)_n. </tex>
 
==Альтернативные формы записи==
 
An alternate notation for the rising factorial
 
:<tex>x^{\overline{m}}=\overbrace{x(x+1)\ldots(x+m-1)}^{m~\mathrm{factors}}\qquad\mbox{for integer }m\ge0,</tex>
 
and for the falling factorial
 
:<tex>x^{\underline{m}}=\overbrace{x(x-1)\ldots(x-m+1)}^{m~\mathrm{factors}}\qquad\mbox{for integer }m\ge0;</tex>
 
goes back to A. Capelli (1893) and L. Toscano (1939), respectively.<ref>According to Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., p. 50.</ref> Graham, Knuth and Patashnik<ref>[[Ronald L. Graham]], [[Donald E. Knuth]] and [[Oren Patashnik]] in their book ''[[Concrete Mathematics]]'' (1988), Addison-Wesley, Reading MA. {{ISBN|0-201-14236-8}}, pp.&nbsp;47,48</ref> propose to pronounce these expressions as "<tex>x</tex> to the <tex>m</tex> rising" and "<tex>x</tex> to the <tex>m</tex> falling", respectively.
 
Other notations for the falling factorial include <tex>P(x,n)</tex>, <tex>^x P_n</tex>, ,<tex>P_{x,n}</tex> или <tex>_x P_n</tex>.
 
An alternate notation for the rising factorial <tex>x^(n)</tex> is the less common <tex>(x)^+_n</tex>. When the notation <tex>(x)^+_n</tex> is used for the rising factorial, the notation <tex>(x)^-_n</tex> is typically used for the ordinary falling factorial to avoid confusion.
 
==Обобщения==
The Pochhammer symbol has a generalized version called the [[generalized Pochhammer symbol]], used in multivariate [[Mathematical analysis|analysis]]. There is also a [[q-analog|''q''-analogue]], the [[q-Pochhammer symbol|''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|&minus;''h''}} is the decrement and {{math|''k''}} 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'']<sup>''k''/1</sup> and [''x'']<sup>''k''/&minus;1</sup>, 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>.<ref>''[https://arxiv.org/abs/1611.04708 Combinatorial Identities for Generalized Stirling Numbers Expanding f-Factorial Functions and the f-Harmonic Numbers]'' (2016).</ref>
 
==Литература==
* [http://mathworld.wolfram.com/PochhammerSymbol.html, Pochhammer Symbol]
* [https://www.scribd.com/doc/288367437/A-Compilation-of-Mathematical-Demonstrations, Elementary Proofs]
 
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Символ Похгаммера]]
Анонимный участник

Навигация