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

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

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

В математике двойной факториал числа n , обозначаемый n ‼ , представляет собой произведение всех натуральных чисел до n , которые имеют ту же четность (нечетную или четную), что и n . То есть,

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

Перефразируя, это говорит о том, что для четного n двойной факториал равен

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

в то время как для нечетного n это

$$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 как пустое произведение .

Последовательность начинается двойных факториалов для четных n = 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 )

Термин «нечетный факториал» иногда используется для обозначения двойного факториала нечетного числа.

Термин полуфакториал также используется Кнутом как синоним двойного факториала.

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

В статье 1902 года физик Артур Шустер писал:

Символическое представление результатов данной работы значительно облегчается введением отдельного символа для произведения альтернативных множителей: $n\cdot n-2\cdot n-4\cdots 1$, если $n$ быть странным, или $n\cdot n-2\cdots 2$ если $n$ быть странным [так в оригинале]. предлагаю написать $n!!$ для таких продуктов, и если для продукта требуется название, чтобы называть его «альтернативным факториалом» или «двойным факториалом».

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

Связь с факториалом

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

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

$$n!=n!!\cdot (n-1)!!\,,$$

и поэтому

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

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

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

$$(2k)!!=2^{k}k!\,.$$

Для нечетного n = 2 k − 1 с k ≥ 1 объединение двух предыдущих формул дает

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

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

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

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

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

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

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

Каллан (2009) и Дейл и Мун (1993) перечисляют несколько дополнительных объектов с той же последовательностью счета , включая «трапециевидные слова» ( числа в смешанной системе счисления с меткой высоты с увеличением нечетных оснований), пути Дика , упорядоченные деревья с меткой высоты. , «навесные пути» и определенные векторы, описывающие потомка листа с наименьшим номером каждого узла в корневом двоичном дереве. Биективные доказательства того, что некоторые из этих объектов равночисленны, см. в Rubey (2008) и Marsh & Martin (2011) .

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

Асимптотика

Приближение Стирлинга для факториала можно использовать для получения асимптотического эквивалента двойного факториала. В частности, поскольку $n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n},$ у одного есть как $n$ стремится к бесконечности, что

$$n!!\sim {\begin{cases}\displaystyle {\sqrt {\pi n}}\left({\frac {n}{e}}\right)^{n/2}&{\text{if }}n{\text{ is even}},\\[5pt]\displaystyle {\sqrt {2n}}\left({\frac {n}{e}}\right)^{n/2}&{\text{if }}n{\text{ is odd}}.\end{cases}}$$

Расширения

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

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

$$n!!=n\times (n-2)!!$$

дать

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

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

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

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

Не обращая внимания на приведенное выше определение n !! для четных значений n двойной факториал для нечетных целых чисел можно расширить до большинства действительных и комплексных чисел z, отметив, что когда z является положительным нечетным целым числом, тогда

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

где $\Gamma (z)$ это гамма-функция .

Окончательное выражение определено для всех комплексных чисел, кроме отрицательных четных целых чисел, и удовлетворяет условию ( z + 2)!! = ( z + 2) · z !! везде это определено. Как и гамма-функция, расширяющая обычную факториальную функцию, эта двойная факториальная функция является логарифмически выпуклой в смысле теоремы Бора – Моллерупа . Асимптотически ${\textstyle n!!\sim {\sqrt {2n^{n+1}e^{-n}}}\,.}$

Обобщенная формула ${\sqrt {\frac {2}{\pi }}}2^{\frac {z}{2}}\Gamma \left({\tfrac {z}{2}}+1\right)$ не согласуется с предыдущей формулой произведения для z !! для неотрицательных четных целых значений z . Вместо этого эта обобщенная формула подразумевает следующую альтернативу:

$$(2k)!!={\sqrt {\frac {2}{\pi }}}2^{k}\Gamma \left(k+1\right)={\sqrt {\frac {2}{\pi }}}\prod _{i=1}^{k}(2i)\,,$$

со значением 0!! в этом случае являющийся

• $0!!={\sqrt {\frac {2}{\pi }}}\approx 0.797\,884\,5608\dots$ (последовательность A076668 в OEIS ).

Используя эту обобщенную формулу в качестве определения, n - гиперсферы мерной объем радиуса R можно выразить как

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

Дополнительные личности

Для целочисленных значений n ,

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

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

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

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

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

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

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

$${\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)!!\\&=\sum _{k=0}^{n}{\binom {2n-k-1}{k-1}}{\frac {(2k-1)(2n-k+1)}{k+1}}(2n-2k-3)!!\\&=\sum _{k=1}^{n}{\frac {(n-1)!}{(k-1)!}}k(2k-3)!!\,.\end{aligned}}$$

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

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

Это приближение становится более точным по мере увеличения n , что можно увидеть в результате интеграла Уоллиса .

Обобщения

Определения

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

$$n!_{(\alpha )}={\begin{cases}n\cdot (n-\alpha )!_{(\alpha )}&{\text{ if }}n>\alpha \,;\\n&{\text{ if }}1\leq n\leq \alpha \,;{\text{and}}\\(n+\alpha )!_{(\alpha )}/(n+\alpha )&{\text{ if }}n\leq 0{\text{ and is not a negative multiple of }}\alpha \,;\end{cases}}$$

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

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

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

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

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

расширяющие многофакторные

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

$$\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)! _{( α )} , как

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

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

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

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

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

суммы, включающие несколько

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

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

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

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

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

Подобные тождества можно получить с помощью контекстно-свободных грамматик. Дополнительные разложения сравнений в конечную сумму для α -факториальных функций ( αn − d )! _{( α )} по модулю любого предписанного целого числа h ≥ 2 для любого 0 ≤ d < α даны Шмидтом (2018) .