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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Числа Лаха)
Строка 105: Строка 105:
 
:<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>\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>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+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>n+1</tex> точке и при этом имеют степень не больше <tex dpi=150>n</tex>, то есть они формально совпадают.
 
Многочлены, стоящие в левой и правой частях тождества, оказались равны в <tex dpi=150>n+1</tex> точке и при этом имеют степень не больше <tex dpi=150>n</tex>, то есть они формально совпадают.
 
}}
 
}}

Версия 03:52, 20 января 2018

Определение:
В математике убывающим факториалом (англ. 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]


Определение:
Растущий факториал (англ. 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]


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

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

В зависимости от контекста символ Похгаммера может обозначать как растущий факториал, так и убывающий факториал. Сам Лео Август Похгаммер для себя использовал [math](x)^n[/math] в другом смысле - для обозначения биномиального коэффициента [math]\tbinom xn[/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](x)_{m+n-k}[/math] называются связывающими коэффициентами (англ. connection coefficients).

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

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

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

Кроме того, мы можем выразить убывающие факториалы следующим образом:

[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]

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

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

[math] x^n = \sum\limits_{k=0}^{n} \left\{\begin{matrix} n \\ n-k \end{matrix} \right\} x^{\underline{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]

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

[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\lt k[/math], поэтому слагаемые из суммы в правой части, начиная с [math]k\geqslant m[/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(x) = x(x-1)(x-2)\cdots\{x\}[/math] — для вещественного [math]x[/math]. Значит,

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

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

[math]\Gamma(x) = (x-1)(x-2)(x-3)\cdots\{x-1\}[/math]

[math]=(x-1)(x-2)(x-3)\cdots\{x\}[/math]

Объединив эти два факта, получим:

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

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

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

Утверждение:
[math](x)_n=\frac{\Gamma(x+1)}{\Gamma(x-n+1)}[/math]
[math]\triangleright[/math]

[math]\Gamma(x) = x(x-1)(x-2)\cdots\{x\}[/math] — по определению. Значит,

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

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

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

Объединив эти два факта, получим:

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

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

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

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

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

Теорема об умножении

По теореме об умножении[6] получаем следующие выражения для растущего факториала:

[math](x)_{k+mn} = (x)_k m^{mn} \prod\limits_{j=0}^{m-1} \left(\frac{x+j+k}{m}\right)_n,\ m \in \mathbb{N} [/math]
[math](ax+b)_n = x^n \prod\limits_{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]

Обобщения

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

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

[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. ↑ 4,0 4,1 Lah numbers
  5. ↑ Gamma function
  6. ↑ Multiplication theorem
  7. ↑ Generalized Pochhammer symbol
  8. ↑ q-analog
  9. ↑ q-Pochhammer symbol

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Символ_Похгаммера&oldid=63654»