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

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

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

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

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

Для четных n двойной факториал равен

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

а для нечетных n это

${\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 )

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

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

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

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

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

Отношение к факториалу [ править ]

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

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

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

и поэтому

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

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

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

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

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

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

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

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

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

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

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

Callan (2009) и Dale & Moon (1993) список несколько дополнительных объектов с одной и той же последовательности подсчета , в том числе «трапециевидных слова» ( цифры в смешанной поразрядной системы с увеличением нечетные radixes), высота меченных путей Дейка , высота меченных упорядоченных деревьев , «нависающие пути» и определенные векторы, описывающие конечный потомок с наименьшим номером каждого узла в корневом двоичном дереве. Для биективных доказательств , что некоторые из этих объектов являются equinumerous см Rubey (2008) и Marsh & Martin (2011) . ^{[14] [15]}

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

Расширения [ править ]

Отрицательные аргументы [ править ]

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

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

дать

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

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

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

Сложные аргументы [ править ]

Игнорируя приведенное выше определение n ‼ для четных значений  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 ‼, определено для всех комплексных чисел, кроме отрицательных четных чисел. Использование его в качестве определения, то объем из п - мерная гиперсферы радиуса R может быть выражен как ^[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=0}^{n-1}{\binom {n}{k+1}}(2k-1)!!(2n-2k-3)!!=\sum _{k=1}^{n}{\binom {n}{k}}(2k-3)!!(2(n-k)-1)!!\,,\\(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}}.}$

Это приближение становится более точным с увеличением 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}}}$

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

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

${\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}}}$

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

В дополнение к расширению n ! _{( α )} для большинства комплексных чисел  n , это определение работает для всех положительных действительных значений  α . Кроме того, когда α = 1 , это определение математически эквивалентно функции Π ( n ) , описанной выше. Кроме того, когда α = 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}\,.}$

Эти обобщенные α -факториальные коэффициенты затем генерируют различные символические полиномиальные произведения, определяющие множественные факториалы, или α -факториальные функции, ( x - 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}}}$

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

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

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

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

${\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}\,.}$

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

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

Предположим, что n ≥ 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 )! _{( α )} по модулю любого заданного целого числа h ≥ 2 для любого 0 ≤ d < α даны Шмидтом (2017) . ^[21]

Ссылки [ править ]