Падающие и растущие факториалы

В математике падающий факториал (иногда называемый нисходящим факториалом ) ^[1] падающее последовательное произведение , или нижний факториал ) определяется как полином ${\begin{aligned}(x)_{n}=x^{\underline {n}}&=\overbrace {x(x-1)(x-2)\cdots (x-n+1)} ^{n{\text{ factors}}}\\&=\prod _{k=1}^{n}(x-k+1)=\prod _{k=0}^{n-1}(x-k).\end{aligned}}$

Возрастающий факториал (иногда называемый функцией Поххаммера , полиномом Поххаммера , возрастающим факториалом , ^[1] возрастающее последовательное произведение , или верхний факториал ) определяется как ${\begin{aligned}x^{(n)}=x^{\overline {n}}&=\overbrace {x(x+1)(x+2)\cdots (x+n-1)} ^{n{\text{ factors}}}\\&=\prod _{k=1}^{n}(x+k-1)=\prod _{k=0}^{n-1}(x+k).\end{aligned}}$

Значение каждого принимается равным 1 ( пустой продукт ), когда $n = 0$ . Эти символы вместе называются факториальными степенями . ^[2]

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

В этой статье символ $(x) n$ используется для обозначения падающего факториала, а символ $x (н)$ используется для возрастающего факториала. Эти соглашения используются в комбинаторике . ^[4]хотя Кнута подчеркнутые и зачеркнутые обозначения $x^{\underline {n}}$ и $x^{\overline {n}}$ становятся все более популярными. ^[2]^[5]В теории специальных функций (в частности, гипергеометрической функции ) и в стандартном справочнике Абрамовица и Стегуна символ Похгаммера $(x) n$ используется для обозначения возрастающего факториала. ^[6]^[7]

Когда $x$ является положительным целым числом, $(x) n$ дает количество $n$ -перестановок (последовательностей различных элементов) из $набора x$ -элементов или, что то же самое, количество инъективных функций из набора размера $n$ в набор размера $x.$ . Восходящий факториал $x (н)$ дает количество разделов набора $n$ -элементов на $x$ упорядоченных последовательностей (возможно, пустых). ^[а]

Примеры и комбинаторная интерпретация

Первые несколько падающих факториалов таковы: ${\begin{alignedat}{2}(x)_{0}&&&=1\\(x)_{1}&&&=x\\(x)_{2}&=x(x-1)&&=x^{2}-x\\(x)_{3}&=x(x-1)(x-2)&&=x^{3}-3x^{2}+2x\\(x)_{4}&=x(x-1)(x-2)(x-3)&&=x^{4}-6x^{3}+11x^{2}-6x\end{alignedat}}$ Первые несколько возрастающих факториалов таковы: ${\begin{alignedat}{2}x^{(0)}&&&=1\\x^{(1)}&&&=x\\x^{(2)}&=x(x+1)&&=x^{2}+x\\x^{(3)}&=x(x+1)(x+2)&&=x^{3}+3x^{2}+2x\\x^{(4)}&=x(x+1)(x+2)(x+3)&&=x^{4}+6x^{3}+11x^{2}+6x\end{alignedat}}$ Коэффициенты, входящие в разложения, представляют собой числа Стирлинга первого рода (см. ниже).

Когда переменная $x$ является целым положительным числом, число $(x) n$ равно количеству $n$ -перестановок из набора $x$ элементов , то есть количеству способов выбора упорядоченного списка длины $n,$ состоящего из различных элементов. взято из коллекции размера $x$ . Например, $(8) 3 = 8 \times 7 \times 6 = 336$ — это количество различных подиумов — присвоений золотых, серебряных и бронзовых медалей — возможных в гонке из восьми человек. В этом контексте другие обозначения, такие как $x P n$ , $х П н$ , $П н х$ , или $P (x, n)$ также иногда используются. С другой стороны, $х (н)$ это «количество способов расположить $n$ флагов на $x$ флагштоках», ^[8]где должны использоваться все флаги, и на каждом флагштоке может быть любое количество флагов. Эквивалентно, это количество способов разделить набор размера $n$ (флаги) на $x$ различимых частей (полюсов) с линейным порядком элементов, присвоенных каждой части (порядок флагов на данном полюсе). .

Характеристики

Возрастающие и падающие факториалы просто связаны друг с другом: ${\begin{alignedat}{2}{(x)}_{n}&={(x-n+1)}^{(n)}&&=(-1)^{n}(-x)^{(n)},\\x^{(n)}&={(x+n-1)}_{n}&&=(-1)^{n}(-x)_{n}.\end{alignedat}}$

Падающие и возрастающие факториалы целых чисел напрямую связаны с обычным факториалом : ${\begin{aligned}n!&=1^{(n)}=(n)_{n},\\[6pt](m)_{n}&={\frac {m!}{(m-n)!}},\\[6pt]m^{(n)}&={\frac {(m+n-1)!}{(m-1)!}}.\end{aligned}}$

Возрастающие факториалы полуцелых чисел напрямую связаны с двойным факториалом : ${\begin{aligned}\left[{\frac {1}{2}}\right]^{(n)}={\frac {(2n-1)!!}{2^{n}}},\quad \left[{\frac {2m+1}{2}}\right]^{(n)}={\frac {(2(n+m)-1)!!}{2^{n}(2m-1)!!}}.\end{aligned}}$

Падающие и возрастающие факториалы можно использовать для выражения биномиального коэффициента : ${\begin{aligned}{\frac {(x)_{n}}{n!}}&={\binom {x}{n}},\\[6pt]{\frac {x^{(n)}}{n!}}&={\binom {x+n-1}{n}}.\end{aligned}}$

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

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

Действительные числа и отрицательное n

Падающий факториал можно расширить до реальных значений $x$ с помощью гамма-функции при условии, что $x$ и $x + n$ являются действительными числами, которые не являются отрицательными целыми числами: $(x)_{n}={\frac {\Gamma (x+1)}{\Gamma (x-n+1)}}\ ,$ то же самое может сделать и растущий факториал: $x^{(n)}={\frac {\Gamma (x+n)}{\Gamma (x)}}\ .$

Исчисление

Падающие факториалы появляются при многократном дифференцировании простых степенных функций: $\left({\frac {\mathrm {d} }{\mathrm {d} x}}\right)^{n}x^{a}=(a)_{n}\cdot x^{a-n}.$

Возрастающий факториал также является неотъемлемой частью определения гипергеометрической функции : Гипергеометрическая функция определена для $| г | < 1$ в степенном ряду ${}_{2}F_{1}(a,b;c;z)=\sum _{n=0}^{\infty }{\frac {a^{(n)}b^{(n)}}{c^{(n)}}}{\frac {z^{n}}{n!}}$ при условии, что $c \neq 0, -1, -2, ...$ . Однако обратите внимание, что в литературе по гипергеометрическим функциям обычно используется обозначение $(a) n$ для возрастающих факториалов.

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

Падающие и растущие факториалы тесно связаны с числами Стирлинга . Действительно, при разложении произведения появляются числа Стирлинга первого рода. ${\begin{aligned}(x)_{n}&=\sum _{k=0}^{n}s(n,k)x^{k}\\&=\sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}(-1)^{n-k}x^{k}\\x^{(n)}&=\sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}\\\end{aligned}}$

А для обратных соотношений используются числа Стирлинга второго рода. ${\begin{aligned}x^{n}&=\sum _{k=0}^{n}{\begin{Bmatrix}n\\k\end{Bmatrix}}(x)_{k}\\&=\sum _{k=0}^{n}{\begin{Bmatrix}n\\k\end{Bmatrix}}(-1)^{n-k}x^{(k)}.\end{aligned}}$

Падающие и возрастающие факториалы связаны друг с другом числами Лаха. ${\textstyle L(n,k)={\binom {n-1}{k-1}}{\frac {n!}{k!}}}$ : ^[9] ${\begin{aligned}(x)_{n}&=\sum _{k=0}^{n}L(n,k)x^{(k)}\\x^{(n)}&=\sum _{k=0}^{n}L(n,k)(-1)^{n-k}(x)_{k}\end{aligned}}$

Поскольку падающие факториалы являются основой кольца полиномов , произведение двух из них можно выразить как линейную комбинацию падающих факториалов: ^[10] $(x)_{m}(x)_{n}=\sum _{k=0}^{m}{\binom {m}{k}}{\binom {n}{k}}k!\cdot (x)_{m+n-k}\ .$

Коэффициенты ${\tbinom {m}{k}}{\tbinom {n}{k}}k!$ называются коэффициентами связи и имеют комбинаторную интерпретацию как количество способов идентифицировать (или «склеить») $k$ элементов каждый из набора размера $m$ и набора размера $n$ .

Существует также формула связи для отношения двух возрастающих факториалов, определяемая как ${\frac {x^{(n)}}{x^{(i)}}}=(x+i)^{(n-i)},\quad {\text{for }}n\geq i.$

Кроме того, мы можем расширить обобщенные законы экспоненты и отрицательные возрастающие и нисходящие степени с помощью следующих тождеств: ^[11]^{(стр. 52)}

${\begin{aligned}(x)_{m+n}&=(x)_{m}(x-m)_{n}=(x)_{n}(x-n)_{m}\\[6pt]x^{(m+n)}&=x^{(m)}(x+m)^{(n)}=x^{(n)}(x+n)^{(m)}\\[6pt]x^{(-n)}&={\frac {\Gamma (x-n)}{\Gamma (x)}}={\frac {(x-n-1)!}{(x-1)!}}={\frac {1}{(x-n)^{(n)}}}={\frac {1}{(x-1)_{n}}}={\frac {1}{(x-1)(x-2)\cdots (x-n)}}=(-n)!{\binom {x-n-1}{-n}}\\[6pt](x)_{-n}&={\frac {\Gamma (x+1)}{\Gamma (x+n+1)}}={\frac {x!}{(x+n)!}}={\frac {1}{(x+n)_{n}}}={\frac {1}{(x+1)^{(n)}}}={\frac {1}{(x+1)(x+2)\cdots (x+n)}}=(-n)!{\binom {x}{-n}}.\end{aligned}}$

Наконец, дублирования и формулы умножения падающих и возрастающих факториалов дают следующие соотношения: ${\begin{aligned}(x)_{k+mn}&=x^{(k)}m^{mn}\prod _{j=0}^{m-1}\left({\frac {x-k-j}{m}}\right)_{n}\,,&{\text{for }}m&\in \mathbb {N} \\[6pt]x^{(k+mn)}&=x^{(k)}m^{mn}\prod _{j=0}^{m-1}\left({\frac {x+k+j}{m}}\right)^{(n)},&{\text{for }}m&\in \mathbb {N} \\[6pt](ax+b)^{(n)}&=x^{n}\prod _{j=0}^{n-1}\left(a+{\frac {b+j}{x}}\right),&{\text{for }}x&\in \mathbb {Z} ^{+}\\[6pt](2x)^{(2n)}&=2^{2n}x^{(n)}\left(x+{\frac {1}{2}}\right)^{(n)}.\end{aligned}}$

Связь с теневым исчислением

Падающий факториал встречается в формуле, которая представляет полиномы с помощью оператора прямой разности. $\Delta f(x){\stackrel {\mathrm {def} }{=}}f(x{+}1)-f(x),$ и которая формально аналогична теореме Тейлора : $f(x)=\sum _{n=0}^{\infty }{\frac {\Delta ^{n}f(0)}{n!}}(x)_{n}.$

играет падающий факториал $(x) n$ в исчислении конечных разностей . В этой формуле и во многих других местах роль $x н$ в дифференциальном исчислении. Обратите внимание, например, на сходство $Δ (x) n = n (x) n -1$ с $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ д / д х ⁠ х н = nx п -1$ .

Аналогичный результат справедлив для возрастающего факториала и оператора обратной разности.

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

${\begin{aligned}(a+b)_{n}&=\sum _{j=0}^{n}{\binom {n}{j}}(a)_{n-j}(b)_{j}\\[6pt](a+b)^{(n)}&=\sum _{j=0}^{n}{\binom {n}{j}}a^{(n-j)}b^{(j)}\end{aligned}}$

где коэффициенты те же, что и в биномиальной теореме .

Точно так же производящая функция полиномов Поххаммера тогда равна теневой экспоненте:

$\sum _{n=0}^{\infty }(x)_{n}{\frac {t^{n}}{n!}}=\left(1+t\right)^{x},$

с

$\operatorname {\Delta } _{x}\left(1+t\right)^{x}=t\cdot \left(1+t\right)^{x}.$

Альтернативные обозначения

Альтернативное обозначение возрастающего факториала $x^{\overline {m}}\equiv (x)_{+m}\equiv (x)_{m}=\overbrace {x(x+1)\ldots (x+m-1)} ^{m{\text{ factors}}}\quad {\text{for integer }}m\geq 0$

и для падающего факториала $x^{\underline {m}}\equiv (x)_{-m}=\overbrace {x(x-1)\ldots (x-m+1)} ^{m{\text{ factors}}}\quad {\text{for integer }}m\geq 0$

восходит к А. Капелли (1893) и Л. Тоскано (1939) соответственно. ^[2] Грэм, Кнут и Паташник ^[11]^{(стр. 47, 48)}предлагаю произносить эти выражения как « $х$ к $м$ поднимается» и « $х$ к $м$ падает» соответственно.

Другие обозначения падающего факториала включают $P (x, n)$ , $х П н$ , $П х, п$ , $П н х$ , или $x P n$ . (См. перестановку и комбинацию .)

Альтернативное обозначение возрастающего факториала $x (н)$ является менее распространенным $(x) + н$ . Когда $(х) + n$ используется для обозначения возрастающего факториала, обозначение $(x) - n$ обычно используется для обычного падающего факториала, чтобы избежать путаницы. ^[3]

Обобщения

Символ Поххаммера имеет обобщенную версию, называемую обобщенным символом Поххаммера , используемую в многомерном анализе . Существует также $q$ -аналог , $q-$ символ Похгаммера .

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

$(x)_{n,f,t}:=\prod _{k=0}^{n-1}\left(x+{\frac {f(k)}{t^{k}}}\right)$

может быть изучено с точки зрения классов обобщенных чисел Стирлинга первого рода, определяемых следующими коэффициентами при степенях $x$ в разложениях $(x) n, f, t$ и затем следующим соответствующим треугольным рекуррентным соотношением :

${\begin{aligned}\left[{\begin{matrix}n\\k\end{matrix}}\right]_{f,t}&=\left[x^{k-1}\right](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{aligned}}$

Эти коэффициенты удовлетворяют ряду свойств, аналогичных свойствам чисел Стирлинга первого рода , а также рекуррентным соотношениям и функциональным уравнениям, связанным с $f$ -гармоническими числами: ^[12] $F_{n}^{(r)}(t):=\sum _{k\leq n}{\frac {t^{k}}{f(k)^{r}}}\,.$

См. также

Ссылки

^ Здесь части различны; например, когда $x = n = 2$ , $(2) (2) = 6$ разделов $(12,-)$ , $(21,-)$ , $(1,2)$ , $(2,1)$ , $(-,12)$ , и $(-,21)$ , где − обозначает пустую часть.

^ Перейти обратно: ^а ^б Стеффенсен, Дж. Ф. (17 марта 2006 г.). Интерполяция (2-е изд.). Дуврские публикации. п. 8. ISBN 0-486-45009-0 . - Перепечатка издания 1950 года издательством Chelsea Publishing.
^ Перейти обратно: ^а ^б ^с Кнут, Д.Э. Искусство компьютерного программирования . Том. 1 (3-е изд.). п. 50.
^ Перейти обратно: ^а ^б Кнут, DE (1992). «Две заметки об обозначениях». Американский математический ежемесячник . 99 (5): 403–422. arXiv : математика/9205211 . дои : 10.2307/2325085 . JSTOR 2325085 . S2CID 119584305 . Замечание о символе Поххаммера находится на странице 414.
^ Олвер, П.Дж. (1999). Классическая теория инвариантов . Издательство Кембриджского университета. п. 101. ИСБН 0-521-55821-2 . МР 1694364 .
^ Харрис; Херст; Моссингхофф (2008). Комбинаторика и теория графов . Спрингер. гл. 2. ISBN 978-0-387-79710-6 .
^ Абрамовиц, Милтон; Стегун, Ирен А., ред. (декабрь 1972 г.) [июнь 1964 г.]. Справочник по математическим функциям с формулами, графиками и математическими таблицами . Серия Национального бюро стандартов по прикладной математике . Том. 55. Вашингтон, округ Колумбия: Министерство торговли США . п. 256 экв. 6.1.22. LCCN 64-60036 .
^ Слейтер, Люси Дж. (1966). Обобщенные гипергеометрические функции . Издательство Кембриджского университета. Приложение I. МР 0201688 . — Дает полезный список формул для управления возрастающим факториалом в $обозначениях (x) n$ .
^ Феллер, Уильям. Введение в теорию вероятностей и ее приложения . Том. 1. Ч. 2.
^ «Введение в факториалы и биномы» . Сайт функций Wolfram .
^ Росас, Мерседес Х. (2002). «Специализации симметричных функций Мак-Магона и алгебра полиномов». Дискретная математика . 246 (1–3): 285–293. дои : 10.1016/S0012-365X(01)00263-1 . hdl : 11441/41678 .
^ Перейти обратно: ^а ^б Грэм, Рональд Л .; Кнут, Дональд Э. и Паташник, Орен (1988). Конкретная математика . Ридинг, Массачусетс: Аддисон-Уэсли. стр. 47, 48, 52. ISBN. 0-201-14236-8 .
^ Шмидт, Макси Д. (2018). «Комбинаторные тождества для обобщенных чисел Стирлинга, расширяющих $f$ -факториальные функции и $f$ -гармонические числа». Журнал целочисленных последовательностей . 21 (2) 18.2.7. arXiv : 1611.04708v2 . МР 3779776 .

Внешние ссылки

Вайсштейн, Эрик В. «Символ Поххаммера» . Математический мир .

[8] Здесь части различны; например, когда $x = n = 2$ , $(2) (2) = 6$ разделов $(12,-)$ , $(21,-)$ , $(1,2)$ , $(2,1)$ , $(-,12)$ , и $(-,21)$ , где − обозначает пустую часть.

[Steffensen-1] Перейти обратно: ^а ^б Стеффенсен, Дж. Ф. (17 марта 2006 г.). Интерполяция (2-е изд.). Дуврские публикации. п. 8. ISBN 0-486-45009-0 . - Перепечатка издания 1950 года издательством Chelsea Publishing.

[The_Art_of_Computer_Programming-2] Перейти обратно: ^а ^б ^с Кнут, Д.Э. Искусство компьютерного программирования . Том. 1 (3-е изд.). п. 50.

[Knuth-3] Перейти обратно: ^а ^б Кнут, DE (1992). «Две заметки об обозначениях». Американский математический ежемесячник . 99 (5): 403–422. arXiv : математика/9205211 . дои : 10.2307/2325085 . JSTOR 2325085 . S2CID 119584305 . Замечание о символе Поххаммера находится на странице 414.

[4] Олвер, П.Дж. (1999). Классическая теория инвариантов . Издательство Кембриджского университета. п. 101. ИСБН 0-521-55821-2 . МР 1694364 .

[5] Харрис; Херст; Моссингхофф (2008). Комбинаторика и теория графов . Спрингер. гл. 2. ISBN 978-0-387-79710-6 .

[6] Абрамовиц, Милтон; Стегун, Ирен А., ред. (декабрь 1972 г.) [июнь 1964 г.]. Справочник по математическим функциям с формулами, графиками и математическими таблицами . Серия Национального бюро стандартов по прикладной математике . Том. 55. Вашингтон, округ Колумбия: Министерство торговли США . п. 256 экв. 6.1.22. LCCN 64-60036 .

[7] Слейтер, Люси Дж. (1966). Обобщенные гипергеометрические функции . Издательство Кембриджского университета. Приложение I. МР 0201688 . — Дает полезный список формул для управления возрастающим факториалом в $обозначениях (x) n$ .

[Feller-9] Феллер, Уильям. Введение в теорию вероятностей и ее приложения . Том. 1. Ч. 2.

[Wolfram_functions-10] «Введение в факториалы и биномы» . Сайт функций Wolfram .

[11] Росас, Мерседес Х. (2002). «Специализации симметричных функций Мак-Магона и алгебра полиномов». Дискретная математика . 246 (1–3): 285–293. дои : 10.1016/S0012-365X(01)00263-1 . hdl : 11441/41678 .

[Graham-Knuth-Patashnik-1988-12] Перейти обратно: ^а ^б Грэм, Рональд Л .; Кнут, Дональд Э. и Паташник, Орен (1988). Конкретная математика . Ридинг, Массачусетс: Аддисон-Уэсли. стр. 47, 48, 52. ISBN. 0-201-14236-8 .

[13] Шмидт, Макси Д. (2018). «Комбинаторные тождества для обобщенных чисел Стирлинга, расширяющих $f$ -факториальные функции и $f$ -гармонические числа». Журнал целочисленных последовательностей . 21 (2) 18.2.7. arXiv : 1611.04708v2 . МР 3779776 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[а]

[8]

[9]

[10]

[11]

[12]