Символ Похгаммера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 34 промежуточные версии 4 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
В математике '''убывающим факториалом''' (англ. ''falling factorial'') (иногда называется '''нисходящим факториалом''',<ref name="Steffensen" /> '''постепенно убывающим факториалом''' или '''нижним факториалом''') обозначают:
+
В математике '''убывающим факториалом''' (англ. ''falling 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>
+
:<tex>(x)_{n}=x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)=\prod\limits_{k=1}^{n}(x-(k-1))=\prod\limits_{k=0}^{n-1}(x-k)</tex>
 +
При <tex>n=0</tex> значение принимается равным <tex>1</tex> (пустое произведение).
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Растущий факториал''' (англ. ''rising factorial'') (иногда называется '''функцией Похгаммера''', '''многочленом Похгаммера''', '''восходящим факториалом''',<ref name="Steffensen">Steffensen, J. F., Interpolation (2nd ed.), Dover Publications, p. 8, ISBN 0-486-45009-0 (A reprint of the 1950 edition by Chelsea Publishing Co.)</ref> '''постепенно растущим произведением''' или '''верхним факториалом''') определяется следующей формулой:
+
'''Растущий факториал''' (англ. ''rising factorial'') (иногда называется '''функцией Похгаммера''', '''многочленом Похгаммера''', '''восходящим факториалом''', '''постепенно растущим произведением''' или '''верхним факториалом''') определяется следующей формулой:
:<tex>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). </tex>
+
:<tex>x^{(n)}=x^{\overline{n}}=x(x+1)(x+2)\cdots(x+n-1)=\prod\limits_{k=1}^{n}(x+(k-1))=\prod\limits_{k=0}^{n-1}(x+k). </tex>
 +
При <tex>n=0</tex> значение принимается равным <tex>1</tex> (пустое произведение).
 
}}
 
}}
  
При <tex>n=0</tex> значение принимается равным <tex>1</tex> (пустое произведение).
+
Грахам, Кнут и Паташник<ref>Ronald L. Graham, Donald E. Knuth and Oren Patashnik in their book ''Concrete Mathematics'' (<tex>1988</tex>), Addison-Wesley, Reading MA. ISBN <tex>0-201-14236-8</tex>, pp.&nbsp;<tex>47</tex>,<tex>48</tex></ref> предложили произносить эти записи как "<tex>x</tex> растущий к <tex>m</tex>" и "<tex>x</tex> убывающий к <tex>m</tex>" соответственно.
 +
 
 +
В зависимости от контекста символ Похгаммера может обозначать как растущий факториал, так и убывающий факториал.
  
'''Символ Похгаммера''' введен Лео Августом Похгаммером в записи <tex>(x)^n</tex>, где <tex>n</tex> неотрицательное целое число. В зависимости от контекста символ Похгаммера может обозначать как растущий факториал, так и убывающий факториал. Поэтому при чтении любой статьи необходимо обратить внимание на то, какой именно из двух факториалов имеется в виду. Сам Похгаммер для себя использовал <tex>(x)^n</tex> в другом смысле - для обозначения биномиального коэффициента <tex>\tbinom xn</tex>.<ref name="Knuth">Knuth, Donald E. (1992), "Two notes on notation", American Mathematical Monthly, 99 (5): 403–422, arXiv:math/9205211 Freely accessible, doi:10.2307/2325085, JSTOR 2325085. The remark about the Pochhammer symbol is on page 414.</ref>
+
Когда <tex>x</tex> неотрицательное целое число, <tex>(x)_n</tex> равняется числу инъективных отображений<ref name="Injective function">[https://en.wikipedia.org/wiki/Injective_function Injective function]</ref> из множества с <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)_n</tex> означает убывающий факториал и <tex>(x)^n</tex> - растущий факториал. Такое же обозначение используется в комбинаторике.<ref>Olver, Peter J. (1999), Classical Invariant Theory, Cambridge University Press, ISBN 0-521-55821-2, [https://mathscinet.ams.org/mathscinet-getitem?mr=1694364 MR 1694364]</ref>
+
<b>Замечание</b>
  
Когда <tex>x</tex> неотрицательное целое число, <tex>(x)_n</tex> равняется числу [[wikipedia:Injective function|инъективных отображений]] из множества с <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>P(x,n)</tex>, <tex>^x P_n</tex>, ,<tex>P_{x,n}</tex> или <tex>_x P_n</tex>.
  
 +
Другое обозначение растущего факториала <tex>x^{(n)}</tex> реже встречается, чем <tex>(x)^+_n</tex>. Обозначение <tex>(x)^+_n</tex> используется для растущего факториала, запись <tex>(x)^-_n</tex> обычно применяется для обозначения убывающего факториала для избежания недоразумений.<ref name=Knuth>According to Knuth, The Art of Computer Programming, Vol. <tex>1</tex>, <tex>3</tex>rd ed., p. <tex>50</tex>.</ref>
 +
[[File:RisingFactorial_3.jpg|401px|thumb|upright|График растущего факториала для <tex>n</tex> от <tex>0</tex> до <tex>4</tex>]]
 
==Примеры==
 
==Примеры==
[[File:XxxCircles.png|420px|thumb|upright|График убывающего символа Похгаммера]]
+
[[File:PlotThePochhammerSymbolExample_02.png|401px|thumb|upright|График убывающего факториала для <tex>n</tex> от <tex>0</tex> до <tex>4</tex>]]
 
Несколько первых растущих факториалов:
 
Несколько первых растущих факториалов:
 
:<tex>x^{(0)}=x^{\overline0}=1 </tex>
 
:<tex>x^{(0)}=x^{\overline0}=1 </tex>
Строка 35: Строка 41:
  
 
==Свойства==
 
==Свойства==
 +
Убывающий и растущий факториалы определены так же и в любом ассоциативном кольце с единицей и, следовательно, <tex dpi=150>x</tex> может быть даже комплексным числом, многочленом с комплексными коэффициентами или любой функцией определенной на комплексных числах.
 +
 +
===Коэффициенты связи===
 +
Так как убывающие факториалы {{---}} базис кольца многочленов, мы можем переписать произведение двух из них как линейную комбинацию убывающих факториалов:
 +
 +
:<tex dpi=150>(x)_m (x)_n = \sum\limits_{k=0}^m {m \choose k} {n \choose k} k!\, (x)_{m+n-k}.</tex>
 +
{{Определение
 +
|definition=
 +
Коэффициенты <tex dpi=150>{m \choose k} {n \choose k} k!</tex>, стоящие при <tex dpi=150>(x)_{m+n-k}</tex>, называются '''коэффициентами связи''' (англ. ''connection coefficients'').
 +
}}
 +
 +
===Биномиальный коэффициент===
 
Растущий и убывающий факториалы могут быть использованы для обозначения биномиального коэффициента:
 
Растущий и убывающий факториалы могут быть использованы для обозначения биномиального коэффициента:
  
:<tex dpi=150>\frac{x^{(n)}}{n!} = {x+n-1 \choose n} \quad\mbox{and}\quad \frac{(x)_n}{n!} = {x \choose n}.</tex>
+
:<tex dpi=150>\frac{x^{(n)}}{n!} = {x+n-1 \choose n} </tex> и <tex dpi=150>\frac{(x)_n}{n!} = {x \choose n}.</tex>
  
 
Таким образом, многие свойства биномиальных коэффициентов справедливы для убывающих и растущих факториалов.
 
Таким образом, многие свойства биномиальных коэффициентов справедливы для убывающих и растущих факториалов.
  
 +
===Связь убывающего и растущего факториалов===
 
Растущий факториал может быть выражен как убывающий факториал, начинающийся с другого конца,
 
Растущий факториал может быть выражен как убывающий факториал, начинающийся с другого конца,
  
:<tex dpi=150>x^{(n)} = {(x + n - 1)}_n ,</tex>
+
:<tex dpi=150>x^{(n)} = {(x + n - 1)}_n </tex>
  
 
или как убывающий с противоположным аргументом,
 
или как убывающий с противоположным аргументом,
  
:<tex dpi=150>x^{(n)} = {(-1)}^n {(-x)}_{{n}} .</tex>
+
:<tex dpi=150>x^{(n)} = {(-1)}^n {(-x)}_{{n}} </tex>
  
Убывающий и растущий факториалы определены так же и в любом ассоциативном кольце с единицей и, следовательно, <tex dpi=150>x</tex> может быть даже комплексным числом, многочленом с комплексными коэффициентами или любой функцией определенной на комплексных числах. 
+
Отношение двух символов Похгаммера можно выразить следующим образом:
  
Растущий факториал может быть продолжен на вещественные значения <tex dpi=150>n</tex>, но с использованием [[wikipedia:Gamma function|Гамма функции]] при условии, что <tex dpi=150>x</tex> и <tex dpi=150>x+n</tex> вещественные числа, но не отрицательные целые:
+
:<tex dpi=150>\frac{(x)_n}{(x)_i} = (x-i)_{n-i},\ n \geqslant i. </tex>
  
:<tex dpi=150>x^{(n)}=\frac{\Gamma(x+n)}{\Gamma(x)},</tex>
+
Убывающий факториал возможно выразить следующим способом:
 +
 +
:<tex dpi=150>(x)_{m+n} = x_{m} (x-m)_{n}</tex>
 +
:<tex dpi=150>(x)_{-n} = \frac{1}{(x+1)(x+2) \cdots (x+n)} = \frac{1}{(x+1)^n} = \frac{1}{(x+n)_n} = \frac{1}{n! \binom{x+n}{n}}</tex>
  
то же самое и про убывающий факториал:
+
====Числа Стирлинга первого рода====
 +
Растущий факториал выражается с помощью [[Числа Стирлинга первого рода|чисел Стирлинга первого рода]]:
  
:<tex dpi=150>(x)_n=\frac{\Gamma(x+1)}{\Gamma(x-n+1)}.</tex>
+
:<tex dpi=150>x^{(n)} = \sum\limits_{k=1}^n s(n,k) x^k</tex>
  
Если <tex dpi=150>D</tex> означает производную по <tex dpi=150>x</tex>, то
+
====Числа Стирлинга второго рода====
 +
Убывающий и растущий факториалы выражаются друг через друга при помощи [[Числа Стирлинга второго рода|чисел Стирлинга второго рода]]:
  
:<tex dpi=150>D^n(x^a) = (a)_n\,\, x^{a-n}.</tex>
+
<tex dpi=150> x^{(n)} = \sum\limits_{k=0}^{n} \left\{\begin{matrix} n \\ n-k \end{matrix} \right\} (x)_{n-k} </tex>
 +
:<tex dpi=150> = \sum\limits_{k=0}^{n} \left\{\begin{matrix} n \\ k \end{matrix} \right\}(-1)^{n-k} (x)_k </tex>
  
== Связывающие коэффициенты и тождества ==
+
====Числа Лаха====
 +
Убывающий и растущий факториалы связаны друг с другом числами Лаха<ref name="Lah numbers">[https://en.wikipedia.org/wiki/Lah_number Lah numbers]</ref>:
 +
{{Утверждение
 +
|id=
 +
|author=
 +
|about=
 +
|statement=<tex dpi=150> x^{(n)} = \sum\limits_{k=1}^n (L(n,k) \times (x)_k) = \sum\limits_{k=1}^n (\binom{n-1}{k-1} \frac{n!}{k!} \times (x)_k) </tex>
 +
|proof=
 +
Второе равенство получается из определения чисел Лаха. Поэтому осталось доказать лишь то, что левая часть равняется правой:
 +
:<tex dpi=150> x^{(n)} =\sum\limits_{k=1}^n (\binom{n-1}{k-1} \frac{n!}{k!} \times (x)_k) </tex>
 +
Подставим целое <tex dpi=150>m</tex> из отрезка <tex dpi=150>[0;n]</tex>, тогда получим:
 +
:<tex dpi=150> m^{(n)} =\sum\limits_{k=1}^n (\binom{n-1}{k-1} \frac{n!}{k!} \times (m)_k) </tex>
 +
Заметим, что <tex dpi=150>(m)_k=0</tex> при <tex dpi=150>m+1 \leqslant k</tex>, поэтому слагаемые из суммы в правой части, начиная с <tex dpi=150>k\geqslant m+1</tex>, равны нулю, то есть:
 +
:<tex dpi=150>\sum\limits_{k=1}^n (\binom{n-1}{k-1} \frac{n!}{k!} \times (m)_k)=\sum\limits_{k=1}^{min(m,n)} (\binom{n-1}{k-1} \frac{n!}{k!} \times (m)_k)</tex>
 +
Поделим обе части на <tex dpi=150>n!</tex> и получим, что левая часть равна:
 +
:<tex dpi=150>\frac{(n+m-1)!}{(m-1)!n!}=\frac{(n+m-1)!}{((n+m-1)-n)!n!}=\binom{n+m-1}{n}</tex>
 +
а правая часть будет равна:
  
Убывающий и растущий факториалы связаны друг с другом [[wikipedia:Lah number|числами Лаха]] и суммами для интегральных степеней переменной <tex dpi=150>x</tex> с привлечением [[Числа Стирлинга второго рода|чисел Стирлинга второго рода]] в следующих формах, в которых <tex dpi=150>\binom{r}{k} = r^{\underline{k}} / k!</tex>:
+
<tex dpi=150>\sum\limits_{k=1}^{min(m,n)} (\frac{(n-1)!}{(k-1)!(n-k)!}\times\frac{1}{k!}\times\frac{m!}{(m-k)!})=\sum\limits_{k=1}^{min(m,n)} (\frac{(n-1)!}{(k-1)!(n-k)!}\times\frac{m!}{k!(m-k)!})</tex>
<ref name="Introduction to the factorials and binomials">[http://functions.wolfram.com/GammaBetaErf/Factorial/introductions/FactorialBinomials/05/ Wolfram Functions Site {{---}} Introduction to the factorials and binomials]</ref>
+
:<tex dpi=150>=\sum\limits_{k=1}^{min(m,n)} (\frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}\times\frac{m!}{k!(m-k)!})=\sum\limits_{k=1}^{min(m,n)} (\binom{n-1}{k-1}\times\binom{m}{k})</tex>
 +
То есть мы хотим теперь доказать тождество:
 +
:<tex dpi=150>\binom{n+m-1}{n}=\sum\limits_{k=1}^{min(m,n)} (\binom{n-1}{n-k}\times\binom{m}{k})</tex>
  
<tex dpi=150> x^{\underline{n}} = \sum_{k=1}^n \binom{n-1}{k-1} \frac{n!}{k!} \times (x)_k </tex>
+
Это тождество очевидно из комбинаторики, так как обе части равны числу способов выбрать из <tex dpi=150>n+m-1</tex> элементов, разделённых на два множества по <tex dpi=150>n-1</tex> и <tex dpi=150>m</tex> элементов, <tex dpi=150>n</tex> элементов. С одной стороны нельзя не признать, что это левая часть тождества по определению сочетания. С другой стороны нельзя не согласиться, что это правая часть тождества, в котором <tex dpi=150>k</tex> означает количество элементов, берущихся из множества размера <tex dpi=150>m</tex>, а <tex dpi=150>n-k</tex> из второго множества размера <tex dpi=150>n-1</tex>.
:<tex dpi=150> = (-1)^n (-x)_n = (x-n+1)_n = \frac{1}{(x+1)^{\overline{-n}}} </tex>
+
Многочлены, стоящие в левой и правой частях тождества, оказались равны в <tex dpi=150>n+1</tex> точке и при этом имеют степень не больше <tex dpi=150>n</tex>, то есть они формально совпадают.
:<tex dpi=150> (x)_n = \sum_{k=0}^{n} \binom{n}{k} (n-1)^{\underline{n-k}} \times x^{\underline{k}} </tex>
+
}}
:<tex dpi=150> = (-1)^n (-x)^{\underline{n}} = (x+n-1)^{\underline{n}} = \frac{1}{(x-1)^{\underline{-n}}} </tex>
 
:<tex dpi=150> = \binom{-x}{n} (-1)^n n! </tex>
 
:<tex dpi=150> = \binom{x+n-1}{n} n! </tex>
 
<tex dpi=150> x^n = \sum_{k=0}^{n} \left\{\begin{matrix} n \\ n-k \end{matrix} \right\} x^{\underline{n-k}} </tex>
 
:<tex dpi=150> = \sum_{k=0}^{n} \left\{\begin{matrix} n \\ k \end{matrix} \right\}(-1)^{n-k} (x)_k. </tex>
 
  
Так как убывающие факториалы - базис кольца многочленов, мы можем переписать произведение двух из них как линейную комбинацию убывающих факториалов:
+
===Гамма функция===
 +
Растущий факториал может быть продолжен на вещественные значения <tex dpi=150>n</tex>, но с использованием Гамма функции<ref>[https://en.wikipedia.org/wiki/Gamma_function Gamma function]</ref> при условии, что <tex dpi=150>x</tex> и <tex dpi=150>x+n</tex> вещественные числа, но не отрицательные целые.
  
:<tex dpi=150>(x)_m (x)_n = \sum_{k=0}^m {m \choose k} {n \choose k} k!\, (x)_{m+n-k}.</tex>
+
{{Утверждение
{{Определение
+
|id=
|definition=
+
|author=
Коэффициенты <tex dpi=150>(x)_{m+n-k}</tex> называются ''' связывающими коэффициентами''' (англ. ''connection coefficients'').
+
|about=
}}
+
|statement=<tex dpi=150>x^{(n)}=\frac{\Gamma(x+n)}{\Gamma(x)}</tex>
Связывающие коэффициенты имеют комбинаторную интерпретацию как число способов объединить <tex dpi=150>k</tex> элементов из множеств размера <tex dpi=150>m</tex> и <tex dpi=150>n</tex>.
+
|proof=
 +
:<tex dpi=150>\Gamma(z+1) = z\Gamma(z)</tex> {{---}} для комплексного <tex dpi=150>z</tex>.
 +
Значит, это тождество верно и для <tex dpi=150>z=x</tex>, где <tex dpi=150>x</tex> {{---}} вещественное число. То есть:
 +
:<tex dpi=150>\Gamma(x) = (x-1)\Gamma(x-1)</tex> {{---}} для вещественного <tex dpi=150>x</tex>.
 +
Заметим тогда, что:
  
Отношение двух символов Похгаммера определяется как:
+
<tex dpi=150>\Gamma(x+n) = ((x+n)-1)\cdot\Gamma((x+n)-1) = ((x+n)-1)(x+n-2)\cdot\Gamma((x+n)-2)</tex>
 +
:<tex dpi=150>= \cdots = ((x+n)-1)((x+n)-2)\cdots((x+n)-n)\cdot\Gamma((x+n)-n)</tex>
 +
:<tex dpi=150>= ((x+n)-1)((x+n)-2)\cdots x\cdot\Gamma(x)</tex>
  
:<tex dpi=150>\frac{(x)_n}{(x)_i} = (x+i)_{n-i},\ n \geq i. </tex>
+
Значит:
  
Кроме того, мы можем развернуть экспоненты и убывающие факториалы как:
+
<tex dpi=150>\frac{\Gamma(x+n)}{\Gamma(x)} = \frac{((x+n)-1)((x+n)-2)\cdots x\cdot\Gamma(x)}{\Gamma(x)}</tex>
+
:<tex dpi=150>= (x+n-1)(x+n-2)\cdots x = x(x+1)\cdots(x+n-1)=x^{(n)}</tex>
:<tex dpi=150>x^{\underline{m+n}} = x^{\underline{m}} (x-m)^{\underline{n}}</tex>
+
}}
:<tex dpi=150>(x)_{m+n} = (x)_m (x+m)_n</tex>
 
:<tex dpi=150>(x)_{-n} = \frac{1}{(x-n)_n} = \frac{1}{(x-1)^{\underline{n}}}</tex>  
 
:<tex dpi=150>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>
 
  
Наконец, по [[wikipedia:Multiplication theorem|теореме об умножении]] получаем следующие выражения для растущего факториала:
+
то же самое и про убывающий факториал:
  
:<tex dpi=150>(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 dpi=150>(ax+b)_n = x^n \prod_{k=0}^{x-1} \left(a+\frac{b+k}{x}\right)_{n/x},\ x \in \mathbb{Z}^{+} </tex>  
+
|id=
:<tex dpi=150>(2x)_{2n} = 2^{2n} (x)_n \left(x+\frac{1}{2}\right)_n. </tex>
+
|author=
 +
|about=
 +
|statement=<tex dpi=150>(x)_n=\frac{\Gamma(x+1)}{\Gamma(x-n+1)}</tex>
 +
|proof=
 +
:<tex dpi=150>\Gamma(z+1) = z\Gamma(z)</tex> {{---}} для комплексного <tex dpi=150>z</tex>.
 +
Значит, это тождество верно и для <tex dpi=150>z=x</tex>, где <tex dpi=150>x</tex> {{---}} вещественное число. То есть:
 +
:<tex dpi=150>\Gamma(x+1) = x\Gamma(x)</tex> {{---}} для вещественного <tex dpi=150>x</tex>.
 +
Заметим тогда, что:
  
==Альтернативные формы записи==
+
<tex dpi=150>\Gamma(x+1) = x\cdot\Gamma(x) = x(x-1)\cdot\Gamma(x-1)</tex>
 +
:<tex dpi=150>= \cdots = x(x-1)\cdots(x-n+1)\cdot\Gamma(x-n+1)</tex>
  
Альтернативная форма записи растущего факториала:
+
Значит:
:<tex>x^{\overline{m}}=\overbrace{x(x+1)\ldots(x+m-1)}^{m~\mathrm{factors}}\qquad\mbox{for integer }m\ge0,</tex>
 
а убывающего факториала:
 
:<tex>x^{\underline{m}}=\overbrace{x(x-1)\ldots(x-m+1)}^{m~\mathrm{factors}}\qquad\mbox{for integer }m\ge0;</tex>
 
использовались А. Капелли (1893) и Л. Тоскано (1939) соответственно.<ref>According to Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., p. 50.</ref> Грахам, Кнут и Паташник<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> предложили произносить эти записи как "<tex>x</tex> растущий к <tex>m</tex>" и "<tex>x</tex> убывающий к <tex>m</tex>" соответственно.
 
  
Другие формы записи убывающего факториала: <tex>P(x,n)</tex>, <tex>^x P_n</tex>, ,<tex>P_{x,n}</tex> или <tex>_x P_n</tex>.
+
<tex dpi=150>\frac{\Gamma(x+1)}{\Gamma(x-n+1)} = \frac{x(x-1)\cdots(x-n+1)\cdot\Gamma(x-n+1)}{\Gamma(x-n+1)}</tex>
 +
:<tex dpi=150>= x(x-1)\cdots(x-n+1) = (x)_n</tex>
 +
}}
  
Другое обозначение растущего факториала <tex>x^{(n)}</tex> реже встречается, чем <tex>(x)^+_n</tex>. Обозначение <tex>(x)^+_n</tex> используется для растущего факториала, запись <tex>(x)^-_n</tex> обычно применяется для обозначения убывающего факториала для избежания недоразумений.<ref name=Knuth />
+
===Дифференциал===
 +
{{Утверждение
 +
|id=
 +
|author=
 +
|about=
 +
|statement=<tex dpi=150>\frac{\partial^n(x^a)}{\partial x^n} = (a)_n\,\, x^{a-n}</tex>
 +
|proof=
 +
<tex dpi=150>\frac{\partial^n(x^a)}{\partial x^n} =a\times\frac{\partial^{n-1}(x^{a-1})}{\partial x^{n-1}}=a(a-1)\times\frac{\partial^{n-2}(x^{a-2})}{\partial x^{n-2}}</tex>
 +
:<tex dpi=150>=a(a-1)\cdots (a-n+2)\times\frac{\partial(x^{a-(n-1)})}{\partial x}=(a)_n\,\, x^{a-n}</tex>
 +
}}
  
 
==Обобщения==
 
==Обобщения==
Обобщенный символ Похгаммера называется [[wikipedia:Generalized Pochhammer symbol|обобщённый символ Похгаммера]], используемый в многомерном математическом анализе. Также существует [[wikipedia:q-Pochhammer symbol|''q''-аналог]] {{---}} [[wikipedia:q-Pochhammer symbol|''q''-Похгаммер символ]].
+
Существует обобщённый символ Похгаммера<ref>[https://en.wikipedia.org/wiki/Generalized_Pochhammer_symbol Generalized Pochhammer symbol]</ref>, используемый в многомерном математическом анализе. Также существует <tex>q</tex>-аналог<ref>[https://en.wikipedia.org/wiki/Q-analog ''q''-analog]</ref> {{---}} <tex>q</tex>-Похгаммер символ<ref>[https://en.wikipedia.org/wiki/Q-Pochhammer_symbol ''q''-Pochhammer symbol]</ref>.
  
Обобщение убывающего факториала, в которой функция вычисляется по нисходящей арифметической последовательности целых чисел, а значения перемножаются как:
+
Обобщение убывающего факториала {{---}} функция, определённая следующим образом:
  
:<tex>[f(x)]^{k/-h}=f(x)\cdot f(x-h)\cdot f(x-2h)\cdots f(x-(k-1)h),</tex>
+
:<tex dpi=150>[f(x)]^{k/-h}=f(x)\cdot f(x-h)\cdot f(x-2h)\cdots f(x-(k-1)h),</tex>
  
где :<tex>-h</tex> декремент и :<tex>k</tex> число факторов. Соответствующее обобщения растущего факториала:
+
где <tex>-h</tex> и <tex>k</tex> {{---}} разница в убывающей арифметической прогрессии аргументов множителей и число множителей соответственно. Аналогичное обобщение растущего факториала:
  
:<tex>[f(x)]^{k/h}=f(x)\cdot f(x+h)\cdot f(x+2h)\cdots f(x+(k-1)h).</tex>
+
:<tex dpi=150>[f(x)]^{k/h}=f(x)\cdot f(x+h)\cdot f(x+2h)\cdots f(x+(k-1)h).</tex>
  
Эта запись объединяет растущий и убывающий факториалы, которые [''x'']<sup>''k''/1</sup> and [''x'']<sup>''k''/&minus;1</sup> соответственно.
+
Эта запись объединяет растущий и убывающий факториалы, которые <tex dpi=150>[x^{k/1}]</tex> и <tex dpi=150>[x^{k/-1}]</tex> соответственно.
  
Для арифметической функции <tex>f: \mathbb{N} \rightarrow \mathbb{C}</tex> и параметров <tex>x, t</tex> определен обобщенное факториальное произведение вида:
+
Для арифметической функции <tex>f: \mathbb{N} \rightarrow \mathbb{C}</tex> и параметров <tex>x, t</tex> определено обобщенное факториальное произведение вида:
  
:<tex>(x)_{n,f,t} := \prod_{k=1}^{n-1} \left(x+\frac{f(k)}{t^k}\right)</tex>
+
:<tex dpi=150>(x)_{n,f,t} = \prod\limits_{k=1}^{n-1} \left(x+\frac{f(k)}{t^k}\right)</tex>
  
 
== См.также ==
 
== См.также ==
*[[wikipedia:Gamma function|Гамма функция]]
 
 
*[[Числа Стирлинга первого рода]]
 
*[[Числа Стирлинга первого рода]]
 
*[[Числа Стирлинга второго рода]]
 
*[[Числа Стирлинга второго рода]]
*[[wikipedia:Injective function|Инъективное отображение]]
 
*[[wikipedia:Generalized Pochhammer symbol|Обобщённый символ Похгаммера]]
 
*[[wikipedia:q-Pochhammer symbol|''q''-Похгаммер символ]]
 
*[[wikipedia:Lah number|Числа Лаха]]
 
*[[wikipedia:Multiplication theorem|Теорема об умножении]]
 
  
 
==Примeчания==
 
==Примeчания==
Строка 149: Строка 200:
 
* [https://en.wikipedia.org/wiki/Falling_and_rising_factorials#cite_ref-3 Wikipedia {{---}} Falling and rising factorials]
 
* [https://en.wikipedia.org/wiki/Falling_and_rising_factorials#cite_ref-3 Wikipedia {{---}} Falling and rising factorials]
 
* [https://www.mathworks.com/help/symbolic/pochhammer.html?requestedDomain=true Pochhammer Symbol at MATLAB]
 
* [https://www.mathworks.com/help/symbolic/pochhammer.html?requestedDomain=true Pochhammer Symbol at MATLAB]
 +
* [http://mathworld.wolfram.com/RisingFactorial.html Rising Factorial]
 +
* [https://www.researchgate.net/publication/309461372_Several_identities_involving_the_falling_and_rising_factorials_and_the_Cauchy_Lah_and_Stirling_numbers Several identities involving the falling and rising factorials and the Cauchy, Lah, and Stirling numbers]
  
[[Категория:Дискретная математика и алгоритмы]]
+
[[Категория: Дискретная математика и алгоритмы]]
[[Категория:Символ Похгаммера]]
+
[[Категория: Комбинаторика]]
 
 
= ЭТО НЕ КОНЕЦ, ЭТО ЕЩЕ ТОЛЬКО НАЧАЛО =
 

Текущая версия на 19:32, 4 сентября 2022

Определение:
В математике убывающим факториалом (англ. falling factorial) (иногда называется нисходящим факториалом, постепенно убывающим факториалом или нижним факториалом) обозначают:
[math](x)_{n}=x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)=\prod\limits_{k=1}^{n}(x-(k-1))=\prod\limits_{k=0}^{n-1}(x-k)[/math]
При [math]n=0[/math] значение принимается равным [math]1[/math] (пустое произведение).


Определение:
Растущий факториал (англ. rising factorial) (иногда называется функцией Похгаммера, многочленом Похгаммера, восходящим факториалом, постепенно растущим произведением или верхним факториалом) определяется следующей формулой:
[math]x^{(n)}=x^{\overline{n}}=x(x+1)(x+2)\cdots(x+n-1)=\prod\limits_{k=1}^{n}(x+(k-1))=\prod\limits_{k=0}^{n-1}(x+k). [/math]
При [math]n=0[/math] значение принимается равным [math]1[/math] (пустое произведение).


Грахам, Кнут и Паташник[1] предложили произносить эти записи как "[math]x[/math] растущий к [math]m[/math]" и "[math]x[/math] убывающий к [math]m[/math]" соответственно.

В зависимости от контекста символ Похгаммера может обозначать как растущий факториал, так и убывающий факториал.

Когда [math]x[/math] неотрицательное целое число, [math](x)_n[/math] равняется числу инъективных отображений[2] из множества с [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]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] обычно применяется для обозначения убывающего факториала для избежания недоразумений.[3]

График растущего факториала для [math]n[/math] от [math]0[/math] до [math]4[/math]

Примеры

График убывающего факториала для [math]n[/math] от [math]0[/math] до [math]4[/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]x[/math] может быть даже комплексным числом, многочленом с комплексными коэффициентами или любой функцией определенной на комплексных числах.

Коэффициенты связи

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

[math](x)_m (x)_n = \sum\limits_{k=0}^m {m \choose k} {n \choose k} k!\, (x)_{m+n-k}.[/math]
Определение:
Коэффициенты [math]{m \choose k} {n \choose k} k![/math], стоящие при [math](x)_{m+n-k}[/math], называются коэффициентами связи (англ. connection coefficients).


Биномиальный коэффициент

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

[math]\frac{x^{(n)}}{n!} = {x+n-1 \choose n} [/math] и [math]\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]\frac{(x)_n}{(x)_i} = (x-i)_{n-i},\ n \geqslant i. [/math]

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

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

Числа Стирлинга первого рода

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

[math]x^{(n)} = \sum\limits_{k=1}^n s(n,k) x^k[/math]

Числа Стирлинга второго рода

Убывающий и растущий факториалы выражаются друг через друга при помощи чисел Стирлинга второго рода:

[math] x^{(n)} = \sum\limits_{k=0}^{n} \left\{\begin{matrix} n \\ n-k \end{matrix} \right\} (x)_{n-k} [/math]

[math] = \sum\limits_{k=0}^{n} \left\{\begin{matrix} n \\ k \end{matrix} \right\}(-1)^{n-k} (x)_k [/math]

Числа Лаха

Убывающий и растущий факториалы связаны друг с другом числами Лаха[4]:

Утверждение:
[math] x^{(n)} = \sum\limits_{k=1}^n (L(n,k) \times (x)_k) = \sum\limits_{k=1}^n (\binom{n-1}{k-1} \frac{n!}{k!} \times (x)_k) [/math]
[math]\triangleright[/math]

Второе равенство получается из определения чисел Лаха. Поэтому осталось доказать лишь то, что левая часть равняется правой:

[math] x^{(n)} =\sum\limits_{k=1}^n (\binom{n-1}{k-1} \frac{n!}{k!} \times (x)_k) [/math]

Подставим целое [math]m[/math] из отрезка [math][0;n][/math], тогда получим:

[math] m^{(n)} =\sum\limits_{k=1}^n (\binom{n-1}{k-1} \frac{n!}{k!} \times (m)_k) [/math]

Заметим, что [math](m)_k=0[/math] при [math]m+1 \leqslant k[/math], поэтому слагаемые из суммы в правой части, начиная с [math]k\geqslant m+1[/math], равны нулю, то есть:

[math]\sum\limits_{k=1}^n (\binom{n-1}{k-1} \frac{n!}{k!} \times (m)_k)=\sum\limits_{k=1}^{min(m,n)} (\binom{n-1}{k-1} \frac{n!}{k!} \times (m)_k)[/math]

Поделим обе части на [math]n![/math] и получим, что левая часть равна:

[math]\frac{(n+m-1)!}{(m-1)!n!}=\frac{(n+m-1)!}{((n+m-1)-n)!n!}=\binom{n+m-1}{n}[/math]

а правая часть будет равна:

[math]\sum\limits_{k=1}^{min(m,n)} (\frac{(n-1)!}{(k-1)!(n-k)!}\times\frac{1}{k!}\times\frac{m!}{(m-k)!})=\sum\limits_{k=1}^{min(m,n)} (\frac{(n-1)!}{(k-1)!(n-k)!}\times\frac{m!}{k!(m-k)!})[/math]

[math]=\sum\limits_{k=1}^{min(m,n)} (\frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}\times\frac{m!}{k!(m-k)!})=\sum\limits_{k=1}^{min(m,n)} (\binom{n-1}{k-1}\times\binom{m}{k})[/math]

То есть мы хотим теперь доказать тождество:

[math]\binom{n+m-1}{n}=\sum\limits_{k=1}^{min(m,n)} (\binom{n-1}{n-k}\times\binom{m}{k})[/math]

Это тождество очевидно из комбинаторики, так как обе части равны числу способов выбрать из [math]n+m-1[/math] элементов, разделённых на два множества по [math]n-1[/math] и [math]m[/math] элементов, [math]n[/math] элементов. С одной стороны нельзя не признать, что это левая часть тождества по определению сочетания. С другой стороны нельзя не согласиться, что это правая часть тождества, в котором [math]k[/math] означает количество элементов, берущихся из множества размера [math]m[/math], а [math]n-k[/math] из второго множества размера [math]n-1[/math].

Многочлены, стоящие в левой и правой частях тождества, оказались равны в [math]n+1[/math] точке и при этом имеют степень не больше [math]n[/math], то есть они формально совпадают.
[math]\triangleleft[/math]

Гамма функция

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

Утверждение:
[math]x^{(n)}=\frac{\Gamma(x+n)}{\Gamma(x)}[/math]
[math]\triangleright[/math]
[math]\Gamma(z+1) = z\Gamma(z)[/math] — для комплексного [math]z[/math].

Значит, это тождество верно и для [math]z=x[/math], где [math]x[/math] — вещественное число. То есть:

[math]\Gamma(x) = (x-1)\Gamma(x-1)[/math] — для вещественного [math]x[/math].

Заметим тогда, что:

[math]\Gamma(x+n) = ((x+n)-1)\cdot\Gamma((x+n)-1) = ((x+n)-1)(x+n-2)\cdot\Gamma((x+n)-2)[/math]

[math]= \cdots = ((x+n)-1)((x+n)-2)\cdots((x+n)-n)\cdot\Gamma((x+n)-n)[/math]
[math]= ((x+n)-1)((x+n)-2)\cdots x\cdot\Gamma(x)[/math]

Значит:

[math]\frac{\Gamma(x+n)}{\Gamma(x)} = \frac{((x+n)-1)((x+n)-2)\cdots x\cdot\Gamma(x)}{\Gamma(x)}[/math]

[math]= (x+n-1)(x+n-2)\cdots x = x(x+1)\cdots(x+n-1)=x^{(n)}[/math]
[math]\triangleleft[/math]

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

Утверждение:
[math](x)_n=\frac{\Gamma(x+1)}{\Gamma(x-n+1)}[/math]
[math]\triangleright[/math]
[math]\Gamma(z+1) = z\Gamma(z)[/math] — для комплексного [math]z[/math].

Значит, это тождество верно и для [math]z=x[/math], где [math]x[/math] — вещественное число. То есть:

[math]\Gamma(x+1) = x\Gamma(x)[/math] — для вещественного [math]x[/math].

Заметим тогда, что:

[math]\Gamma(x+1) = x\cdot\Gamma(x) = x(x-1)\cdot\Gamma(x-1)[/math]

[math]= \cdots = x(x-1)\cdots(x-n+1)\cdot\Gamma(x-n+1)[/math]

Значит:

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

[math]= x(x-1)\cdots(x-n+1) = (x)_n[/math]
[math]\triangleleft[/math]

Дифференциал

Утверждение:
[math]\frac{\partial^n(x^a)}{\partial x^n} = (a)_n\,\, x^{a-n}[/math]
[math]\triangleright[/math]

[math]\frac{\partial^n(x^a)}{\partial x^n} =a\times\frac{\partial^{n-1}(x^{a-1})}{\partial x^{n-1}}=a(a-1)\times\frac{\partial^{n-2}(x^{a-2})}{\partial x^{n-2}}[/math]

[math]=a(a-1)\cdots (a-n+2)\times\frac{\partial(x^{a-(n-1)})}{\partial x}=(a)_n\,\, x^{a-n}[/math]
[math]\triangleleft[/math]

Обобщения

Существует обобщённый символ Похгаммера[6], используемый в многомерном математическом анализе. Также существует [math]q[/math]-аналог[7][math]q[/math]-Похгаммер символ[8].

Обобщение убывающего факториала — функция, определённая следующим образом:

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

где [math]-h[/math] и [math]k[/math] — разница в убывающей арифметической прогрессии аргументов множителей и число множителей соответственно. Аналогичное обобщение растущего факториала:

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

Эта запись объединяет растущий и убывающий факториалы, которые [math][x^{k/1}][/math] и [math][x^{k/-1}][/math] соответственно.

Для арифметической функции [math]f: \mathbb{N} \rightarrow \mathbb{C}[/math] и параметров [math]x, t[/math] определено обобщенное факториальное произведение вида:

[math](x)_{n,f,t} = \prod\limits_{k=1}^{n-1} \left(x+\frac{f(k)}{t^k}\right)[/math]

См.также

Примeчания

  1. Ronald L. Graham, Donald E. Knuth and Oren Patashnik in their book Concrete Mathematics ([math]1988[/math]), Addison-Wesley, Reading MA. ISBN [math]0-201-14236-8[/math], pp. [math]47[/math],[math]48[/math]
  2. Injective function
  3. According to Knuth, The Art of Computer Programming, Vol. [math]1[/math], [math]3[/math]rd ed., p. [math]50[/math].
  4. Lah numbers
  5. Gamma function
  6. Generalized Pochhammer symbol
  7. q-analog
  8. q-Pochhammer symbol

Источники информации