Двойной факториал - Double factorial

Двойной факториал не следует путать с факториал функция повторяется дважды (последовательность A000197 в OEIS ), который записывается как ${\displaystyle (n!)!}$ и нет ${\displaystyle n!!}$.

Пятнадцать различных диаграмм аккордов на шести точках, или, что то же самое, пятнадцать различных идеальное соответствие на шестивершине полный график. Они подсчитываются двойным факториалом 15 = (6 − 1)‼.

В математика, то двойной факториал или же полуфакторный из числа п, обозначаемый п‼,^[1] это продукт всех целые числа от 1 до п которые имеют то же самое паритет (нечетное или четное) как п.^[2] То есть,

${\displaystyle n!!=\prod _{k=0}^{\left\lceil {\frac {n}{2}}\right\rceil -1}(n-2k)=n(n-2)(n-4)\cdots .}$

Даже для п, двойной факториал

${\displaystyle n!!=\prod _{k=1}^{\frac {n}{2}}(2k)=n(n-2)(n-4)\cdots 4\cdot 2\,,}$

и для нечетных п это

${\displaystyle n!!=\prod _{k=1}^{\frac {n+1}{2}}(2k-1)=n(n-2)(n-4)\cdots 3\cdot 1\,.}$

Например, 9‼ = 9 × 7 × 5 × 3 × 1 = 945. Нулевой двойной факториал 0‼ = 1 как пустой продукт.^[3][4]

В последовательность двойных факториалов для четных п = 0, 2, 4, 6, 8,... начинается как

1, 2, 8, 48, 384, 3840, 46080, 645120, ... (последовательность A000165 в OEIS )

Последовательность двойных факториалов для нечетных п = 1, 3, 5, 7, 9,... начинается как

1, 3, 15, 105, 945, 10395, 135135, ... (последовательность A001147 в OEIS )

Период, термин нечетный факториал иногда используется для двойного факториала нечетного числа.^[5][6]

История и использование

Месерв (1948)^[7] (возможно, самая ранняя публикация, использующая двойную факториальную нотацию)^[8] утверждает, что двойной факториал был первоначально введен для того, чтобы упростить выражение некоторых тригонометрические интегралы которые возникают при выводе Уоллис продукт. Двойные факториалы также возникают при выражении объема гиперсфера, и у них есть много приложений в перечислительная комбинаторика.^[2][9] Они происходят в Студенты т-распределение (1908), хотя Госсет не использовала нотацию с двойным восклицательным знаком.

Отношение к факториалу

Поскольку двойной факториал включает только половину множителей обычного факториал, его значение не намного больше квадратного корня из факториала п!, и он намного меньше повторного факториала (п!)!.

Факториал ненулевого п может быть записано как произведение двух двойных факториалов:^[3]

${\displaystyle n!=n!!\cdot (n-1)!!\,,}$

и поэтому

${\displaystyle n!!={\frac {n!}{(n-1)!!}}={\frac {(n+1)!}{(n+1)!!}}\,,}$

где знаменатель отменяет нежелательные множители в числителе. (Последняя форма также применяется, когда п = 0.)

Для четного неотрицательного целого числа п = 2k с k ≥ 0, двойной факториал может быть выражен как

${\displaystyle n!!=2^{k}k!\,.}$

Для нечетных п = 2k − 1 с k ≥ 1, объединение двух представленных выше дисплеев дает

${\displaystyle n!!={\frac {(2k)!}{2^{k}k!}}={\frac {(2k-1)!}{2^{k-1}(k-1)!}}\,.}$

Для нечетного положительного целого числа п = 2k − 1 с k ≥ 1, двойной факториал может быть выражен через k-перестановки 2k в качестве^[2][8]

${\displaystyle (2k-1)!!={\frac {_{2k}P_{k}}{2^{k}}}={\frac {(2k)^{\underline {k}}}{2^{k}}}\,.}$

Приложения в перечислительной комбинаторике

Пятнадцать разных корневые бинарные деревья (с неупорядоченными дочерними элементами) на наборе из четырех помеченных листьев, иллюстрирующих 15 = (2 × 4 − 3)‼ (см. текст статьи).

Двойные факториалы мотивированы тем фактом, что они часто встречаются в перечислительная комбинаторика и другие настройки. Например, п‼ для нечетных значений п считает

• Идеальное соответствие из полный график K_{п + 1} для нечетных п. В таком графе любая единственная вершина v имеет п возможен выбор вершины, с которой он может быть сопоставлен, и после того, как этот выбор сделан, остается проблема выбора идеального сопоставления в полном графе с двумя меньшими вершинами. Например, полный граф с четырьмя вершинами а, б, c, и d имеет три идеальных соответствия: ab и CD, ac и bd, и объявление и до н.э.^[2] Идеальное соответствие можно описать несколькими другими эквивалентными способами, включая инволюции без неподвижных точек на множестве п + 1 Предметы (перестановки в котором каждый цикл - пара)^[2] или хордовые диаграммы (наборы аккордов набора п + 1 точки, равномерно расположенные на окружности, так что каждая точка является концом ровно одной хорды, также называемой Брауэр диаграммы).^[9][10][11] Количество совпадений в полных графах, без ограничения совпадений, чтобы быть идеальным, вместо этого задается телефонные номера, которое может быть выражено как суммирование двойных факториалов.^[12]
• Перестановки Стирлинга, перестановки мультимножество чисел 1, 1, 2, 2, ..., k, k в котором каждая пара равных чисел разделена только большими числами, где k = п + 1/2. Две копии k должны быть смежными; удаление их из перестановки оставляет перестановку, в которой максимальный элемент k − 1, с п позиции, в которые соседняя пара k значения могут быть размещены. Из этой рекурсивной конструкции по индукции следует доказательство того, что перестановки Стирлинга подсчитываются двойными перестановками.^[2] В качестве альтернативы, вместо ограничения на то, что значения между парой могут быть больше, чем она, можно также рассмотреть перестановки этого мультимножества, в которых первые копии каждой пары появляются в отсортированном порядке; такая перестановка определяет соответствие на 2k позиции перестановки, так что снова количество перестановок может быть подсчитано с помощью двойных перестановок.^[9]
• Упорядоченные в куче деревья, деревья с k + 1 узлы помечены 0, 1, 2, ... k, так что корень дерева имеет метку 0, каждый другой узел имеет метку большего размера, чем его родительский, и так, что дочерние элементы каждого узла имеют фиксированный порядок. An Эйлер тур дерева (с удвоенными ребрами) дает перестановку Стирлинга, и каждая перестановка Стирлинга представляет дерево таким образом.^[2][13]
• Бинарные деревья без корней с п + 5/2 маркированные листья. Каждое такое дерево может быть образовано из дерева, у которого на один лист меньше, путем подразделения одного из п ребра дерева и сделав новую вершину родительской для нового листа.
• Бинарные деревья с корнями с п + 3/2 маркированные листья. Этот случай аналогичен случаю без корней, но количество ребер, которые могут быть подразделены, является четным, и в дополнение к подразделению ребра можно добавить узел к дереву с одним меньшим листом, добавив новый корень, два дочерних элемента которого меньшее дерево и новый лист.^[2][9]

Каллан (2009) и Дейл и Луна (1993) перечислить несколько дополнительных объектов с таким же последовательность подсчета, в том числе «трапециевидные слова» (цифры в смешанный корень система с увеличивающимися нечетными основаниями), с меткой высоты Дайковые тропы, упорядоченные деревья с пометкой высоты, «нависающие пути» и определенные векторы, описывающие листового потомка с наименьшим номером каждого узла в корневом двоичном дереве. За биективные доказательства что некоторые из этих объектов равны, см. Руби (2008) и Марш и Мартин (2011).^[14][15]

Четные двойные факториалы дают номера элементов гипероктаэдрические группы (знаковые перестановки или симметрии гиперкуб )

Расширения

Отрицательные аргументы

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

${\displaystyle n!!=n\times (n-2)!!}$

давать

${\displaystyle n!!={\frac {(n+2)!!}{n+2}}\,.}$

Используя эту обратную рекуррентность, (−1)‼ = 1, (−3)‼ = −1 и (−5)‼ =1/3; отрицательные нечетные числа с большей величиной имеют дробные двойные факториалы.^[2] В частности, это дает, когда п нечетное число,

${\displaystyle (-n)!!\times n!!=(-1)^{\frac {n-1}{2}}\times n\,.}$

Сложные аргументы

Игнорируя приведенное выше определение п‼ для четных значенийп, двойной факториал для нечетных целых чисел может быть расширен до большинства действительных и комплексных чисел z отмечая, что когда z является положительным нечетным целым числом, то^[16][17]

${\displaystyle {\begin{aligned}z!!&=z(z-2)\cdots 3\cdot 1\\&=2^{\frac {z-1}{2}}\left({\frac {z}{2}}\right)\left({\frac {z-2}{2}}\right)\cdots \left({\frac {3}{2}}\right)\\&=2^{\frac {z-1}{2}}{\frac {\Gamma \left({\frac {z}{2}}+1\right)}{\Gamma \left({\frac {1}{2}}+1\right)}}\\&={\sqrt {\frac {2^{z+1}}{\pi }}}\Gamma \left({\frac {z}{2}}+1\right)=\left({\frac {z}{2}}\right)!{\sqrt {\frac {2^{z+1}}{\pi }}}\,.\end{aligned}}}$

Отсюда можно вывести альтернативное определение z‼ для неотрицательных четных целых значенийz:

${\displaystyle (2k)!!={\sqrt {\frac {2}{\pi }}}\prod _{i=1}^{k}(2i)=2^{k}k!{\sqrt {\frac {2}{\pi }}}\,,}$

со значением 0‼ в этом случае

${\displaystyle 0!!={\sqrt {\frac {2}{\pi }}}\approx 0.797\,884\,5608\dots \,.}$

Найденное выражение для z‼ определен для всех комплексных чисел, кроме отрицательных четных целых чисел. Используя его как определение, объем из п-размерный гиперсфера радиуса р можно выразить как^[18]

${\displaystyle V_{n}={\frac {2(2\pi )^{\frac {n-1}{2}}}{n!!}}R^{n}\,.}$

Дополнительные удостоверения

Для целых значений п,

${\displaystyle \int _{0}^{\frac {\pi }{2}}\sin ^{n}x\,dx=\int _{0}^{\frac {\pi }{2}}\cos ^{n}x\,dx={\frac {(n-1)!!}{n!!}}\times {\begin{cases}1&{\text{if }}n{\text{ is odd}}\\{\frac {\pi }{2}}&{\text{if }}n{\text{ is even.}}\end{cases}}}$

Используя вместо этого расширение двойного факториала нечетных чисел до комплексных чисел, формула

${\displaystyle \int _{0}^{\frac {\pi }{2}}\sin ^{n}x\,dx=\int _{0}^{\frac {\pi }{2}}\cos ^{n}x\,dx={\frac {(n-1)!!}{n!!}}{\sqrt {\frac {\pi }{2}}}\,.}$

Двойные факториалы также могут использоваться для вычисления интегралов от более сложных тригонометрических полиномов.^[7][19]

Двойные факториалы нечетных чисел связаны с гамма-функция по личности:

${\displaystyle (2n-1)!!=2^{n}\cdot {\frac {\Gamma \left({\frac {1}{2}}+n\right)}{\sqrt {\pi }}}=(-2)^{n}\cdot {\frac {\sqrt {\pi }}{\Gamma \left({\frac {1}{2}}-n\right)}}\,.}$

Некоторые дополнительные тождества, включающие двойные факториалы нечетных чисел:^[2]

${\displaystyle {\begin{aligned}(2n-1)!!&=\sum _{k=1}^{n-1}{\binom {n}{k+1}}(2k-1)!!(2n-2k-3)!!\,,\\(2n-1)!!&=\sum _{k=0}^{n}{\binom {2n-k-1}{k-1}}{\frac {(2k-1)(2n-k+1)}{k+1}}(2n-2k-3)!!\,,\\(2n-1)!!&=\sum _{k=1}^{n}{\frac {(n-1)!}{(k-1)!}}k(2k-3)!!\,.\end{aligned}}}$

Приближение для отношения двойного факториала двух последовательных целых чисел:

${\displaystyle {\frac {(2n)!!}{(2n-1)!!}}\approx {\sqrt {\pi n}}.}$

Это приближение становится более точным, поскольку п увеличивается.

Обобщения

Определения

Точно так же, как двойной факториал обобщает понятие единственный факториал, следующее определение целочисленных множественных факториальных функций (многофакторность ), или же α-факториальные функции, расширяет понятие двойной факториальной функции для α ∈ ℤ⁺:

${\displaystyle n!_{(\alpha )}={\begin{cases}n\cdot (n-\alpha )!_{(\alpha )}&{\text{ if }}n>0\,;\\1&{\text{ if }}-\alpha <n\leq 0\,;\\0&{\text{ otherwise. }}\end{cases}}}$

Альтернативное расширение многофакторной

В качестве альтернативы многофакторный п!_(α) может быть расширен до большинства действительных и комплексных чисел п отмечая, что когда п на единицу больше, чем положительное кратное α тогда

${\displaystyle {\begin{aligned}n!_{(\alpha )}&=n(n-\alpha )\cdots (\alpha +1)\\&=\alpha ^{\frac {n-1}{\alpha }}\left({\frac {n}{\alpha }}\right)\left({\frac {n-\alpha }{\alpha }}\right)\cdots \left({\frac {\alpha +1}{\alpha }}\right)\\&=\alpha ^{\frac {n-1}{\alpha }}{\frac {\Gamma \left({\frac {n}{\alpha }}+1\right)}{\Gamma \left({\frac {1}{\alpha }}+1\right)}}\,.\end{aligned}}}$

Это последнее выражение имеет гораздо более широкое определение, чем исходное. Таким же образом п! не определен для отрицательных целых чисел, и п‼ не определен для отрицательных целых чисел, п!_(α) не определен для отрицательных кратных α. Однако он определен для всех других комплексных чисел. Это определение согласуется с более ранним определением только для тех целых чисел п удовлетворениеп ≡ 1 мод α.

В дополнение к расширению п!_(α) к самым сложным числамп, это определение работает для всех положительных действительных значенийα. Кроме того, когда α = 1, это определение математически эквивалентно Π (п) функция, описанная выше. Кроме того, когда α = 2, это определение математически эквивалентно альтернативное расширение двойного факториала.

Обобщенные числа Стирлинга, расширяющие многофакторные функции

Класс обобщенных Числа Стирлинга первого рода определяется для α > 0 следующим треугольным рекуррентным соотношением:

${\displaystyle \left[{\begin{matrix}n\\k\end{matrix}}\right]_{\alpha }=(\alpha n+1-2\alpha )\left[{\begin{matrix}n-1\\k\end{matrix}}\right]_{\alpha }+\left[{\begin{matrix}n-1\\k-1\end{matrix}}\right]_{\alpha }+\delta _{n,0}\delta _{k,0}\,.}$

Эти обобщенные α-факторные коэффициенты затем сгенерируйте различные символические полиномиальные произведения, определяющие множественный факториал, или α-факторные функции, (Икс − 1)!_(α), так как

${\displaystyle {\begin{aligned}(x-1|\alpha )^{\underline {n}}&:=\prod _{i=0}^{n-1}\left(x-1-i\alpha \right)=(x-1)(x-1-\alpha )\cdots {\bigl (}x-1-(n-1)\alpha {\bigr )}\\&=\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right](-\alpha )^{n-k}(x-1)^{k}\\&=\sum _{k=1}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]_{\alpha }(-1)^{n-k}x^{k-1}\,.\end{aligned}}}$

Различные полиномиальные разложения в предыдущих уравнениях фактически определяют α-факторные произведения для нескольких различных случаев наименьших остатков Икс ≡ п₀ мод α за п₀ ∈ {0, 1, 2, ..., α − 1}.

Обобщенный α-факторные полиномы, σ^(α)
_п(Икс) куда σ⁽¹⁾
_п(Икс) ≡ σ_п(Икс), которые обобщают Полиномы свертки Стирлинга от однофакторного случая к многофакторному, определяются как

${\displaystyle \sigma _{n}^{(\alpha )}(x):=\left[{\begin{matrix}x\\x-n\end{matrix}}\right]_{(\alpha )}{\frac {(x-n-1)!}{x!}}}$

за 0 ≤ п ≤ Икс. Эти многочлены имеют особенно красивую замкнутую форму обычная производящая функция данный

${\displaystyle \sum _{n\geq 0}x\cdot \sigma _{n}^{(\alpha )}(x)z^{n}=e^{(1-\alpha )z}\left({\frac {\alpha ze^{\alpha z}}{e^{\alpha z}-1}}\right)^{x}\,.}$

Другие комбинаторные свойства и разложения этих обобщенных α-факторные треугольники и полиномиальные последовательности рассматриваются в Шмидт (2010).^[20]

Точные конечные суммы с участием нескольких факториальных функций

Предположим, что п ≥ 1 и α ≥ 2 целочисленные. Затем мы можем разложить следующие одиночные конечные суммы, включающие многофакторную, или α-факторные функции, (αn − 1)!_(α), с точки зрения Символ Поххаммера и обобщенные рациональнозначные биномиальные коэффициенты в качестве

${\displaystyle {\begin{aligned}(\alpha n-1)!_{(\alpha )}&=\sum _{k=0}^{n-1}{\binom {n-1}{k+1}}(-1)^{k}\times \left({\frac {1}{\alpha }}\right)_{-(k+1)}\left({\frac {1}{\alpha }}-n\right)_{k+1}\times {\bigl (}\alpha (k+1)-1{\bigr )}!_{(\alpha )}{\bigl (}\alpha (n-k-1)-1{\bigr )}!_{(\alpha )}\\&=\sum _{k=0}^{n-1}{\binom {n-1}{k+1}}(-1)^{k}\times {\binom {{\frac {1}{\alpha }}+k-n}{k+1}}{\binom {{\frac {1}{\alpha }}-1}{k+1}}\times {\bigl (}\alpha (k+1)-1{\bigr )}!_{(\alpha )}{\bigl (}\alpha (n-k-1)-1{\bigr )}!_{(\alpha )}\,,\end{aligned}}}$

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

${\displaystyle {\begin{aligned}(\alpha n-1)!_{(\alpha )}&=\sum _{k=0}^{n-1}\sum _{i=0}^{k+1}{\binom {n-1}{k+1}}{\binom {k+1}{i}}(-1)^{k}\alpha ^{k+1-i}(\alpha i-1)!_{(\alpha )}{\bigl (}\alpha (n-1-k)-1{\bigr )}!_{(\alpha )}\times (n-1-k)_{k+1-i}\\&=\sum _{k=0}^{n-1}\sum _{i=0}^{k+1}{\binom {n-1}{k+1}}{\binom {k+1}{i}}{\binom {n-1-i}{k+1-i}}(-1)^{k}\alpha ^{k+1-i}(\alpha i-1)!_{(\alpha )}{\bigl (}\alpha (n-1-k)-1{\bigr )}!_{(\alpha )}\times (k+1-i)!.\end{aligned}}}$

Первые две суммы выше по форме похожи на известные некруглый комбинаторное тождество для двойной факториальной функции, когда α := 2 данный Каллан (2009).

${\displaystyle (2n-1)!!=\sum _{k=0}^{n-1}{\binom {n}{k+1}}(2k-1)!!(2n-2k-3)!!.}$

Дополнительные разложения по конечной сумме сравнений для α-факторные функции, (αn − d)!_(α), по модулю любого заданного целого числа час ≥ 2 для любого 0 ≤ d < α даны Шмидт (2017).^[21]

Рекомендации

1. «Список вероятностных и статистических символов». Математическое хранилище. 2020-04-26. Получено 2020-09-10.
2. Каллан, Дэвид (2009). «Комбинаторный обзор тождеств для двойного факториала». arXiv:0906.1317 [math.CO ].
3. Вайсштейн, Эрик В. «Двойной Факториал». mathworld.wolfram.com. Получено 2020-09-10.
4. "Двойные факториалы и мультифакториалы | Блестящая вики по математике и науке". brilliant.org. Получено 2020-09-10.
5. Хендерсон, Дэниел Дж .; Парметр, Кристофер Ф. (2012). «Канонические ядра высшего порядка для оценки производной плотности». Письма о статистике и вероятности. 82 (7): 1383–1387. Дои:10.1016 / j.spl.2012.03.013. МИСТЕР  2929790.
6. Нильсен, Б. (1999). «Тест отношения правдоподобия для ранжирования в двумерном каноническом корреляционном анализе». Биометрика. 86 (2): 279–288. Дои:10.1093 / biomet / 86.2.279. МИСТЕР  1705359.
7. Месерв, Б. Э. (1948). «Классные заметки: двойные факториалы». Американский математический ежемесячник. 55 (7): 425–426. Дои:10.2307/2306136. JSTOR  2306136. МИСТЕР  1527019.
8. Гулд, Генри; Причудливый, Джоселин (2012). «Двойное развлечение с двойными факториалами». Математический журнал. 85 (3): 177–192. Дои:10.4169 / math.mag.85.3.177. МИСТЕР  2924154.
9. Дейл, М. Р. Т .; Мун, Дж. У. (1993). «Переставленные аналоги трех каталонских сетов». Журнал статистического планирования и вывода. 34 (1): 75–87. Дои:10.1016/0378-3758(93)90035-5. МИСТЕР  1209991.
10. Китаев, Сергей (2011). Паттерны в перестановках и словах. Монографии EATCS по теоретической информатике. Springer. п. 96. ISBN  9783642173332.
11. Дейл, М. Р. Т .; Нараяна, Т. В. (1986). «Раздел каталонских переставленных последовательностей с приложениями». Журнал статистического планирования и вывода. 14 (2): 245–249. Дои:10.1016/0378-3758(86)90161-8. МИСТЕР  0852528.
12. Тихи, Роберт Ф .; Вагнер, Стефан (2005). «Экстремальные задачи для топологических индексов комбинаторной химии» (PDF). Журнал вычислительной биологии. 12 (7): 1004–1013. Дои:10.1089 / cmb.2005.12.1004. PMID  16201918.
13. Янсон, Сванте (2008). «Плоские рекурсивные деревья, перестановки Стирлинга и модель урны». Пятый коллоквиум по математике и информатике. Дискретная математика. Теор. Comput. Sci. Proc., AI. Доц. Дискретная математика. Теор. Comput. Наук, Нэнси. С. 541–547. arXiv:0803.1129. Bibcode:2008arXiv0803.1129J. МИСТЕР  2508813.
14. Рубей, Мартин (2008). «Вложения совпадений и перестановок и северных ступеней в PDSAW». 20-я ежегодная международная конференция по формальным степенным рядам и алгебраической комбинаторике (FPSAC 2008). Дискретная математика. Теор. Comput. Sci. Proc., AJ. Доц. Дискретная математика. Теор. Comput. Наук, Нэнси. С. 691–704. МИСТЕР  2721495.
15. Марш, Роберт Дж .; Мартин, Пол (2011). «Тайлинг биекций между путями и диаграммами Брауэра». Журнал алгебраической комбинаторики. 33 (3): 427–453. arXiv:0906.0912. Дои:10.1007 / s10801-010-0252-6. МИСТЕР  2772541.
16. Хассани, Садри (2000). Математические методы: для студентов, изучающих физику и смежные специальности. Тексты для бакалавриата по математике. Springer. п. 266. ISBN  9780387989587.
17. «Двойной факториал: конкретные значения (формула 06.02.03.0005)». Wolfram Research. 2001-10-29. Получено 2013-03-23.
18. Мези, Пол Г. (2009). «Некоторые проблемы размерности в молекулярных базах данных». Журнал математической химии. 45 (1): 1–6. Дои:10.1007 / s10910-008-9365-8.
19. Дассиос, Джордж; Кириаки, Кириаки (1987). «Полезное приложение теоремы Гаусса». Bulletin de la Société Mathématique de Grèce. 28 (А): 40–43. МИСТЕР  0935868.
20. Шмидт, Макси Д. (2010). "Обобщенный j-Факторные функции, многочлены и приложения ». J. Целочисленная последовательность. 13.
21. Шмидт, Макси Д. (2017). «Новые сравнения и конечно-разностные уравнения для обобщенных факторных функций». arXiv:1701.04741 [math.CO ].