Double factoriel - Double factorial

La factorielle double ne doit pas être confondue avec la fonction factorielle itérée deux fois (séquence A000197 dans l' OEIS ), qui s'écrit comme et non .${\style d'affichage (n !) !}$${\style d'affichage n!!}$

Les quinze diagrammes d'accords différents sur six points, ou de manière équivalente les quinze correspondances parfaites différentes sur un graphe complet à six sommets . Ceux-ci sont comptés par la factorielle double 15 = (6 − 1)‼ .

En mathématiques , la factorielle double ou semifactorielle d'un nombre n , notée n ‼ , est le produit de tous les entiers de 1 à n qui ont la même parité (impaire ou paire) que n . C'est-à-dire,

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

Pour n pair , la factorielle double est

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

et pour n impair c'est

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

Par exemple, 9‼ = 9 × 7 × 5 × 3 × 1 = 945 . Le double factoriel zéro 0‼ = 1 comme un produit vide .

La séquence de factorielles doubles pour n pair = 0, 2, 4, 6, 8,... commence comme

1, 2, 8, 48, 384, 3840, 46080, 645120,... (séquence A000165 dans l' OEIS )

La séquence de factorielles doubles pour n impair = 1, 3, 5, 7, 9,... commence comme

1, 3, 15, 105, 945, 10395, 135135,... (séquence A001147 dans l' OEIS )

Le terme factoriel impair est parfois utilisé pour le double factoriel d'un nombre impair.

Historique et utilisation

Dans un article de 1902, le physicien Arthur Schuster a écrit :

La représentation symbolique des résultats de cet article est grandement facilitée par l'introduction d'un symbole séparé pour le produit de facteurs alternatifs, , s'il est impair, ou s'il est impair [sic]. Je propose d'écrire pour de tels produits, et si un nom est requis pour le produit de l'appeler la « factorielle alternative » ou la « factorielle double ».${\displaystyle n\cdot n-2\cdot n-4\cdots 1}$${\style d'affichage n}$${\style d'affichage n\cdot n-2\cdots 2}$${\style d'affichage n}$${\style d'affichage n!!}$

Meserve (1948) déclare que la double factorielle a été introduite à l'origine afin de simplifier l'expression de certaines intégrales trigonométriques qui surviennent dans la dérivation du produit de Wallis . Les factorielles doubles apparaissent également dans l'expression du volume d'une hypersphère , et elles ont de nombreuses applications en combinatoire énumérative . Ils apparaissent dans la distribution t de Student (1908), bien que Gosset n'ait pas utilisé la notation à double point d'exclamation.

Relation avec la factorielle

Parce que la factorielle double n'implique qu'environ la moitié des facteurs de la factorielle ordinaire , sa valeur n'est pas sensiblement plus grande que la racine carrée de la factorielle n ! , et elle est bien plus petite que la factorielle itérée ( n !) ! .

La factorielle d'un n non nul peut s'écrire comme le produit de deux factorielles doubles :

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

et donc

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

où le dénominateur annule les facteurs indésirables dans le numérateur. (La dernière forme s'applique également lorsque n = 0 .)

Pour un entier pair non négatif n = 2 k avec k 0 , la factorielle double peut être exprimée comme

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

Pour n impair = 2 k − 1 avec k 1 , la combinaison des deux affichages ci-dessus donne

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

Pour un entier positif impair n = 2 k − 1 avec k 1 , la factorielle double peut être exprimée en termes de k -permutations de 2 k comme

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

Applications en combinatoire énumérative

Les quinze arbres binaires enracinés différents (avec des enfants non ordonnés) sur un ensemble de quatre feuilles étiquetées, illustrant 15 = (2 × 4 − 3)‼ (voir texte de l'article).

Les factorielles doubles sont motivées par le fait qu'elles surviennent fréquemment en combinatoire énumérative et dans d'autres contextes. Par exemple, n ! Pour les valeurs impaires de n chefs d' accusation

• Appariements parfaits du graphe complet K _{n + 1} pour n impair . Dans un tel graphe, un seul sommet v a n choix possibles de sommets auxquels il peut être apparié, et une fois ce choix fait, le problème restant est de sélectionner une correspondance parfaite dans un graphe complet avec deux sommets de moins. Par exemple, un graphe complet avec quatre sommets a , b , c et d a trois correspondances parfaites : ab et cd , ac et bd , et ad et bc . Les appariements parfaits peuvent être décrits de plusieurs autres manières équivalentes, y compris les involutions sans points fixes sur un ensemble de n + 1 éléments ( permutations dans lesquelles chaque cycle est une paire) ou les diagrammes d'accords (ensembles d'accords d'un ensemble de n + 1 points uniformément espacés sur un cercle de telle sorte que chaque point soit l'extrémité d'exactement une corde, également appelés diagrammes de Brauer ). Les nombres d'appariements dans les graphes complets, sans contraindre les appariements à être parfaits, sont plutôt donnés par les numéros de téléphone , qui peuvent être exprimés comme une sommation impliquant des factorielles doubles.
• Permutations de Stirling , permutations du multi - ensemble de nombres 1, 1, 2, 2, ..., k , k dans lesquelles chaque paire de nombres égaux n'est séparée que par des nombres plus grands, où k = n +1/2. Les deux copies de k doivent être adjacentes ; les retirer de la permutation laisse une permutation dans laquelle l'élément maximum est k − 1 , avec n positions dans lesquelles la paire adjacente de k valeurs peut être placée. De cette construction récursive, une preuve que les permutations de Stirling sont comptées par les doubles permutations suit par induction. Alternativement, au lieu de la restriction selon laquelle les valeurs entre une paire peuvent être plus grandes qu'elle, on peut également considérer les permutations de ce multi-ensemble dans lequel les premières copies de chaque paire apparaissent dans l'ordre trié ; une telle permutation définit un appariement sur les 2 k positions de la permutation, donc encore une fois le nombre de permutations peut être compté par les doubles permutations.
• Arbres classés par tas , arbres avec k + 1 nœuds étiquetés 0, 1, 2, ... k , tels que la racine de l'arbre a l'étiquette 0, chaque autre nœud a une étiquette plus grande que son parent, et tels que les enfants de chaque nœud ont un ordre fixe. Un tour Euler de l'arbre (avec des bords doublés) donne une permutation de Stirling, et chaque permutation de Stirling représente un arbre de cette manière.
• Arbres binaires non racinés avecn + 5/2feuilles étiquetées. Chacun de ces arbres peut être formé à partir d'un arbre avec une feuille de moins, en subdivisant l'un des n bords de l'arbre et en faisant du nouveau sommet le parent d'une nouvelle feuille.
• Arbres binaires enracinés avecn + 3/2feuilles étiquetées. Ce cas est similaire au cas sans racine, mais le nombre d'arêtes qui peuvent être subdivisées est pair, et en plus de subdiviser une arête, il est possible d'ajouter un nœud à un arbre avec une feuille de moins en ajoutant une nouvelle racine dont les deux enfants sont le plus petit arbre et la nouvelle feuille.

Callan (2009) et Dale & Moon (1993) répertorient plusieurs objets supplémentaires avec la même séquence de comptage , y compris les "mots trapézoïdaux" ( chiffres dans un système de base mixte avec des bases impaires croissantes), les chemins de Dyck étiquetés en hauteur, les arbres ordonnés étiquetés en hauteur , « chemins en surplomb » et certains vecteurs décrivant le descendant de feuille le plus petit de chaque nœud dans un arbre binaire enraciné. Pour des preuves bijectives que certains de ces objets sont équinumériques, voir Rubey (2008) et Marsh & Martin (2011) .

Les factorielles doubles paires donnent les nombres d'éléments des groupes hyperoctaédriques (permutations ou symétries signées d'un hypercube )

Rallonges

Arguments négatifs

La factorielle ordinaire, lorsqu'elle est étendue à la fonction gamma , a un pôle à chaque entier négatif, empêchant la factorielle d'être définie à ces nombres. Cependant, la double factorielle des nombres impairs peut être étendue à tout argument entier impair négatif en inversant sa relation de récurrence

${\style d'affichage n!!=n\fois (n-2)!!}$

donner

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

En utilisant cette récurrence inversée, (−1)‼ = 1, (−3)‼ = −1, et (−5)‼ = 1/3; les nombres impairs négatifs avec une plus grande amplitude ont des doubles factorielles fractionnaires. En particulier, cela donne, lorsque n est un nombre impair,

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

Arguments complexes

Abstraction faite de la définition ci - dessus n ! Pour les valeurs même de  n , le double factoriel pour les entiers impairs peut être étendu à la plupart réels et des nombres complexes z en notant que lorsque z est un nombre entier impair positif,

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

On peut en déduire une définition alternative de z ‼ pour les valeurs entières paires non négatives de  z :

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

avec la valeur pour 0‼ dans ce cas étant

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

L'expression trouvée pour z ‼ est définie pour tous les nombres complexes sauf les entiers pairs négatifs. En utilisant comme la définition, le volume de d'un n - dimensions hypersphère de rayon R peut être exprimé en

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

Identités supplémentaires

Pour les valeurs entières de 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{ est impair}}\\{\frac {\pi }{2}}&{\text{if }}n{\text{ est pair.}}\end{cases}}}$

En utilisant à la place l'extension de la factorielle double des nombres impairs aux nombres complexes, la formule est

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

Les factorielles doubles peuvent également être utilisées pour évaluer les intégrales de polynômes trigonométriques plus compliqués.

Les factorielles doubles des nombres impairs sont liées à la fonction gamma par l'identité :

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

Certaines identités supplémentaires impliquant des factorielles doubles de nombres impairs sont :

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

Une approximation du rapport de la factorielle double de deux entiers consécutifs est

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

Cette approximation devient plus précise lorsque n augmente.

Généralisations

Définitions

De la même manière que la factorielle double généralise la notion de factorielle simple , la définition suivante des fonctions factorielles multiples à valeurs entières ( multifactorielles ), ou fonctions α -factorielles, étend la notion de fonction factorielle double pour α ∈ ℤ ⁺ :

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

Extension alternative du multifactoriel

Alternativement, le multifactoriel n ! _{( Α )} peut être étendu à la plupart des nombres réels et complexes n en notant que , lorsque n est un de plus que un multiple positif de α , puis

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

Cette dernière expression est définie beaucoup plus largement que l'originale. De la même manière que n ! n'est pas défini pour les entiers négatifs, et n ‼ n'est pas défini pour les entiers pairs négatifs, n ! _{( α )} n'est pas défini pour les multiples négatifs de α . Cependant, il est défini pour tous les autres nombres complexes. Cette définition n'est cohérente avec la définition précédente que pour les entiers n satisfaisant  n 1 mod α .

En plus d'étendre n ! _{( Α )} à la plupart des nombres complexes  n , cette définition a la particularité de travailler pour toutes les valeurs réelles positives de  α . De plus, lorsque α = 1 , cette définition est mathématiquement équivalente à la fonction ( n ) décrite ci-dessus. Aussi, lorsque α = 2 , cette définition est mathématiquement équivalente à l' extension alternative de la factorielle double .

Nombres de Stirling généralisés développant les fonctions multifactorielles

Une classe de nombres de Stirling généralisés du premier type est définie pour α > 0 par la relation de récurrence triangulaire suivante :

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

Ces généralisée α coefficients -factorial génèrent ensuite les produits polynomiales symboliques distincts définissant les multiples factoriel, ou alpha fonctions -factorial, ( x - 1)! _{( α )} , comme

${\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{matrice}}\right](-\alpha )^{nk}(x-1)^{k}\\ &=\sum _{k=1}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]_{\alpha }(-1)^{nk}x ^{k-1}\,.\end{aligned}}}$

Les expansions polynomiales distinctes dans les équations précédentes définissent en fait les alpha produits -factorial pour de multiples cas distincts des moindres résidus x ≡ n ₀ mod α pour n ₀ ∈ {0, 1, 2, ..., α - 1} .

La généralisée α polynômes -factorial, σ^{( Α )}
_n( X ) où σ⁽¹⁾
_m( X ) ≡ σ _n ( x ) , ce qui généralise les polynômes de convolution Stirling du cas factoriel unique pour les cas multifactorielles, sont définis par

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

pour 0 ≤ n ≤ x . Ces polynômes ont une fonction génératrice ordinaire de forme fermée particulièrement agréable donnée par

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

D' autres propriétés combinatoires et l' expansion de ces généralisée α -factorial triangles et des séquences polynôme sont considérés dans Schmidt (2010) .

Sommes finies exactes impliquant plusieurs fonctions factorielles

Supposons que n 1 et α ≥ 2 soient des valeurs entières. Ensuite, nous pouvons développer les prochaines sommes finies uniques impliquant les fonctions multifactorielles, ou α -factorielles, ( αn − 1) ! _{( α )} , en termes du symbole de Pochhammer et des coefficients binomiaux généralisés à valeur rationnelle comme

${\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 (nk-1)-1{\bigr )}!_{(\alpha )}\\&=\sum _{k=0}^{n-1}{\binom {n-1}{k+ 1}}(-1)^{k}\times {\binom {{\frac {1}{\alpha }}+kn}{k+1}}{\binom {{\frac {1}{\alpha }}-1}{k+1}}\times {\bigl (}\alpha (k+1)-1{\bigr )}!_{(\alpha )}{\bigl (}\alpha (nk- 1)-1{\bigr )}!_{(\alpha )}\,,\end{aligned}}}$

et de plus, nous avons de même des développements à double somme de ces fonctions donnés par

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

Les deux premières sommes ci-dessus sont de forme similaire à une identité combinatoire non ronde connue pour la fonction factorielle double lorsque α  := 2 donnée par Callan (2009) .

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

Expansions somme finie supplémentaires de congruence pour les alpha fonctions -factorial, ( aN - d )! _{( α )} , modulo tout entier prescrit h 2 pour tout 0 ≤ d < α sont donnés par Schmidt (2018) .

Les références