生成関数

Knuthの論文「畳み込み多項式」^{[ 9 ]}では、次の形式の特別な生成関数によって、 畳み込み多項式列の一般化されたクラスが定義されています。$${\displaystyle F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n},}$$べき級数展開を持つ 解析関数Fに対して、 F (0) = 1となる。

多項式の族f ₀ , f ₁ , f ₂ , ...が畳み込み族を形成するとは、deg f _n ≤ nであり、かつすべてのx , yおよびすべてのn ≥ 0に対して次の畳み込み条件が成り立つ場合をいう。 $${\displaystyle f_{n}(x+y)=f_{n}(x)f_{0}(y)+f_{n-1}(x)f_{1}(y)+\cdots +f_{1}(x)f_{n-1}(y)+f_{0}(x)f_{n}(y).}$$

非同一ゼロ畳み込み族の場合、この定義は、数列が上記で示した最初の形式の通常の生成関数を持つことを要求することと同等であることがわかります。

上記の表記で定義された畳み込み多項式の列は、以下の性質を持つ。

• 数列n ! · f _n ( x )は二項型である
• 数列の特別な値には、f _n (1) = [ z ⁿ ] F ( z )およびf _n (0) = δ _{n ,0}が含まれます。
• 任意の（固定）${\displaystyle x,y,t\in \mathbb {C} }$これらの多項式は、次の形式の畳み込み公式を満たす。

$${\displaystyle {\begin{aligned}f_{n}(x+y)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(y)\\f_{n}(2x)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(x)\\xnf_{n}(x+y)&=(x+y)\sum _{k=0}^{n}kf_{k}(x)f_{n-k}(y)\\{\frac {(x+y)f_{n}(x+y+tn)}{x+y+tn}}&=\sum _{k=0}^{n}{\frac {xf_{k}(x+tk)}{x+tk}}{\frac {yf_{n-k}(y+t(n-k))}{y+t(n-k)}}.\end{aligned}}}$$

固定された非ゼロパラメータの場合${\displaystyle t\in \mathbb {C} }$我々は、これらの畳み込み多項式列の生成関数を修正しました。 $${\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n}\right]{\mathcal {F}}_{t}(z)^{x},}$$ ここで、𝓕 _t ( z )は、 𝓕 _t ( z ) = F ( x 𝓕 _t ( z ) ^t )の形の関数方程式によって暗黙的に定義されます。さらに、行列法（参考文献にあるように）を使用して、対応する生成関数F ( z ) ^xとG ( z ) ^xを持つ 2 つの畳み込み多項式列⟨ f _n ( x ) ⟩と⟨ g _n ( x ) ⟩が与えられた場合、任意のtに対して次の恒等式が成り立つことを証明できます。 $${\displaystyle \left[z^{n}\right]\left(G(z)F\left(zG(z)^{t}\right)\right)^{x}=\sum _{k=0}^{n}F_{k}(x)G_{n-k}(x+tk).}$$

畳み込み多項式列の例としては、二項べき級数𝓑 _t ( z ) = 1 + z 𝓑 _t ( z ) ^t、いわゆる木多項式、ベル数B ( n )、ラゲール多項式、スターリング畳み込み多項式などがあります。

通常の母関数の乗算は、数列の離散畳み込み（コーシー積）をもたらします。例えば、累積和の数列（やや一般的なオイラー・マクローリンの公式と比較してください） $${\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )}$$通常の生成関数G ( a _n ; x ) を持つ数列の生成関数は $${\displaystyle G(a_{n};x)\cdot {\frac {1}{1-x}}}$$ なぜなら、1 / 1 − xは数列(1, 1, ...)の通常の母関数だからです。母関数の畳み込みと解釈を用いた問題解決のさらなる例については、この記事の応用セクションにある畳み込みに関するセクションも参照してください。

整数m ≥ 1に対して、 ⟨ g _{n − m} ⟩および⟨ g _{n + m} ⟩のシフトされたシーケンスのバリアントを列挙する修正生成関数に対して、次の 2 つの類似した恒等式がそれぞれ存在します。 $${\displaystyle {\begin{aligned}&z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\\[4px]&{\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}=\sum _{n=0}^{\infty }g_{n+m}z^{n}.\end{aligned}}}$$

生成関数の1階導関数とその積分について、それぞれ以下のべき級数展開が得られます。 $${\displaystyle {\begin{aligned}G'(z)&=\sum _{n=0}^{\infty }(n+1)g_{n+1}z^{n}\\[4px]z\cdot G'(z)&=\sum _{n=0}^{\infty }ng_{n}z^{n}\\[4px]\int _{0}^{z}G(t)\,dt&=\sum _{n=1}^{\infty }{\frac {g_{n-1}}{n}}z^{n}.\end{aligned}}}$$

2番目の恒等式の微分乗算演算をk回繰り返すと、数列にn ^kを掛けることができますが、そのためには微分と乗算を交互に行う必要があります。代わりにk回の微分を連続して行うと、 k番目の下降階乗を掛けることになります。 $${\displaystyle z^{k}G^{(k)}(z)=\sum _{n=0}^{\infty }n^{\underline {k}}g_{n}z^{n}=\sum _{n=0}^{\infty }n(n-1)\dotsb (n-k+1)g_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .}$$

第二種スターリング数を用いると、これは別の公式に変換して乗算することができる。${\displaystyle n^{k}}$以下に示します（生成関数変換に関するメイン記事を参照）。 $${\displaystyle \sum _{j=0}^{k}{\begin{Bmatrix}k\\j\end{Bmatrix}}z^{j}F^{(j)}(z)=\sum _{n=0}^{\infty }n^{k}f_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .}$$

繰り返し積分演算に対応するこの数列べき乗公式の負の次数反転は、ゼータ級数変換とその一般化によって定義され、生成関数の導関数に基づく変換として定義されるか、または項ごとに数列生成関数に積分変換を実行することによって定義されます。数列生成関数に分数積分を実行する関連演算については、ここで説明します。

このセクションでは、通常の生成関数F ( z )が与えられたときに、数列{ f _{an + b} }を列挙する生成関数の公式を示します。ここで、a ≥ 2、0 ≤ b < aであり、aとbは整数です (変換に関するメインの記事を参照してください)。a = 2の場合、これは単に関数を偶数部分と奇数部分(つまり、偶数乗と奇数乗) に分解するおなじみの方法になります。 $${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }f_{2n}z^{2n}&={\frac {F(z)+F(-z)}{2}}\\[4px]\sum _{n=0}^{\infty }f_{2n+1}z^{2n+1}&={\frac {F(z)-F(-z)}{2}}.\end{aligned}}}$$

より一般的に、a ≥ 3であり、ω _a = exp ⁠ 2 πi / a ⁠がa番目の原始根を表すと仮定します。すると、離散フーリエ変換の応用として、次の式が得られます^{[ 15 ]}$${\displaystyle \sum _{n=0}^{\infty }f_{an+b}z^{an+b}={\frac {1}{a}}\sum _{m=0}^{a-1}\omega _{a}^{-mb}F\left(\omega _{a}^{m}z\right).}$$

整数m ≥ 1の場合、各係数をm回繰り返すことで、やや逆の切り捨て算術数列を提供する別の有用な公式が恒等式^{[ 16 ]によって生成されます。}$${\displaystyle \sum _{n=0}^{\infty }f_{\left\lfloor {\frac {n}{m}}\right\rfloor }z^{n}={\frac {1-z^{m}}{1-z}}F(z^{m})=\left(1+z+\cdots +z^{m-2}+z^{m-1}\right)F(z^{m}).}$$

形式的なべき級数（または関数）F（z）は、次の形式の線形微分方程式を満たす場合にホロノミックであると言われます^{[ 17 ]}$${\displaystyle c_{0}(z)F^{(r)}(z)+c_{1}(z)F^{(r-1)}(z)+\cdots +c_{r}(z)F(z)=0,}$$

ここで、係数c _i ( z )は有理関数の領域に属し、${\displaystyle \mathbb {C} (z)}$同等に、${\displaystyle F(z)}$ベクトル空間がホロノミックである場合、${\displaystyle \mathbb {C} (z)}$そのすべての導関数の集合によって張られる空間は有限次元である。

前の式では必要に応じて分母を消去できるので、関数c _i ( z )はzの多項式であると仮定できます。したがって、生成関数の係数が次の形式の P漸化式を満たす場合、生成関数はホロノミックであるという同等の条件がわかります。$${\displaystyle {\widehat {c}}_{s}(n)f_{n+s}+{\widehat {c}}_{s-1}(n)f_{n+s-1}+\cdots +{\widehat {c}}_{0}(n)f_{n}=0,}$$

for all large enough n ≥ n₀ and where the ĉ_i(n) are fixed finite-degree polynomials in n. In other words, the properties that a sequence be P-recursive and have a holonomic generating function are equivalent. Holonomic functions are closed under the Hadamard product operation ⊙ on generating functions.

The functions e^z, log z, cos z, arcsin z, ${\displaystyle {\sqrt {1+z}}}$, the dilogarithm function Li₂(z), the generalized hypergeometric functions_pF_q(...; ...; z) and the functions defined by the power series $${\displaystyle \sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2}}}}$$

and the non-convergent $${\displaystyle \sum _{n=0}^{\infty }n!\cdot z^{n}}$$ are all holonomic.

Examples of P-recursive sequences with holonomic generating functions include f_n ≔ ⁠1/n + 1⁠(²ⁿ_n) and f_n ≔ ⁠2ⁿ/n² + 1⁠, where sequences such as ${\displaystyle {\sqrt {n}}}$ and log n are notP-recursive due to the nature of singularities in their corresponding generating functions. Similarly, functions with infinitely many singularities such as tan z, sec z, and Γ(z) are not holonomic functions.

MathematicaでP再帰シーケンスを処理および操作するためのツールには、RISC Combinatorics Group のアルゴリズム組み合わせソフトウェアサイトで非商用利用向けに提供されているソフトウェア パッケージが含まれます。ほとんどがクローズド ソースですが、このソフトウェア スイートの中で特に強力なツールは、任意の入力シーケンスのP再帰を推測するパッケージ(実験数学や探索に役立ちます) と、多数の和の P 再帰を見つけ、一般化された調和数を含むP再帰の閉形式解を求めることができるパッケージです。^{[ 18 ]}この特定の RISC サイトにリストされている他のパッケージは、特にホロノミック生成関数の操作を対象としています。GuessSigma

上記のように導出された、平方数列の通常の母関数は次のようになる。 $${\displaystyle G(n^{2};x)={\frac {x(x+1)}{(1-x)^{3}}}.}$$

r = 1、α = −1、β = 3、A ( x ) = 0、B ( x ) = x + 1の場合、正方形が予想どおりに成長することが確認できます。 $${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {1+1}{1^{-1}\,\Gamma (3)}}\,n^{3-1}\left({\frac {1}{1}}\right)^{n}=n^{2}.}$$

カタラン数の通常の母関数は $${\displaystyle G(C_{n};x)={\frac {1-{\sqrt {1-4x}}}{2x}}.}$$

r = 1 / 4、 α = 1、β = −1 / 2、 A ( x ) = 1 / 2 、 B ( x ) = −1/2の場合、カタラン数については次のことが 結論付けられます。$${\displaystyle C_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {-{\frac {1}{2}}}{\left({\frac {1}{4}}\right)^{1}\Gamma \left(-{\frac {1}{2}}\right)}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\,{\frac {1}{4}}\,}}\right)^{n}={\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}.}$$

2次元配列a _{m , n} ( nとmは自然数) の通常の母関数は次のとおりです。 $${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.}$$例えば、(1 + x ) ^{n は}固定されたnに対する二項係数の通常の生成関数であるため、すべてのkとnに対して二項係数( ⁿ _k )を生成する二変数生成関数を求めることができます。これを行うには、(1 + x ) ⁿ自体をnのシーケンスとみなし、これらのシーケンスの値を係数として持つyの生成関数を見つけます。n に対する生成関数は次のようになり^ます。 $${\displaystyle {\frac {1}{1-ay}},}$$二項係数の生成関数は次のとおりです。 $${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}.}$$他の例としては、二項係数、スターリング数、オイラー数に対する以下の2変数生成関数が挙げられる。ここでωとzは2つの変数を表す。^{[ 19 ]}$${\displaystyle {\begin{aligned}e^{z+wz}&=\sum _{m,n\geq 0}{\binom {n}{m}}w^{m}{\frac {z^{n}}{n!}}\\[4px]e^{w(e^{z}-1)}&=\sum _{m,n\geq 0}{\begin{Bmatrix}n\\m\end{Bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1}{(1-z)^{w}}}&=\sum _{m,n\geq 0}{\begin{bmatrix}n\\m\end{bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1-w}{e^{(w-1)z}-w}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}n\\m\end{matrix}}\right\rangle w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {e^{w}-e^{z}}{we^{z}-ze^{w}}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}m+n+1\\m\end{matrix}}\right\rangle {\frac {w^{m}z^{n}}{(m+n+1)!}}.\end{aligned}}}$$

多変数生成関数は、行と列の合計が指定された非負整数の分割表の数を計算する際に実際に現れます。表がr行、c列を持ち、行の合計がt ₁、t ₂ ... t _r、列の合計がs ₁、s ₂ ... s _cであるとします。すると、IJ Good [ ^{20 ]}によれば、そのような表の数は、次の係数になります ^。$${\displaystyle x_{1}^{t_{1}}\cdots x_{r}^{t_{r}}y_{1}^{s_{1}}\cdots y_{c}^{s_{c}}}$$で：$${\displaystyle \prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}.}$$

（形式的な）ヤコビ型およびスティルチェス型の連分数（それぞれJ分数およびS分数）の展開は、 h次有理収束が2 h次精度のべき級数を表すものであり、多くの特殊な 1 変数および 2 変数のシーケンスに対して、通常発散する通常の生成関数を表現するもう 1 つの方法です。ヤコビ型の連分数（J分数）の特定の形式は、次の式のように展開され、特定のアプリケーション依存のコンポーネント シーケンス{ab _i }および{ c _i }に対して、 zに関する次の対応するべき級数展開を持ちます。ここで、z ≠ 0 は、以下に示す 2 番目のべき級数展開の形式変数を表します。^{[ 21 ]}$${\displaystyle {\begin{aligned}J^{[\infty ]}(z)&={\cfrac {1}{1-c_{1}z-{\cfrac {{\text{ab}}_{2}z^{2}}{1-c_{2}z-{\cfrac {{\text{ab}}_{3}z^{2}}{\ddots }}}}}}\\[4px]&=1+c_{1}z+\left({\text{ab}}_{2}+c_{1}^{2}\right)z^{2}+\left(2{\text{ab}}_{2}c_{1}+c_{1}^{3}+{\text{ab}}_{2}c_{2}\right)z^{3}+\cdots \end{aligned}}}$$

係数${\displaystyle z^{n}}$前述の式において 、 j _n ≔ [ z ⁿ ] J ^[∞] ( z )と略記されるものは、以下の式の行列解に対応する。$${\displaystyle {\begin{bmatrix}k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\k_{0,3}&k_{1,3}&k_{2,3}&k_{3,3}&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}={\begin{bmatrix}k_{0,0}&0&0&0&\cdots \\k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}\cdot {\begin{bmatrix}c_{1}&1&0&0&\cdots \\{\text{ab}}_{2}&c_{2}&1&0&\cdots \\0&{\text{ab}}_{3}&c_{3}&1&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}},}$$

ここで、j ₀ ≡ k _0,0 = 1、n ≥ 1の場合はj _n = k _{0, n}、r > sの場合はk _{r , s} = 0、そしてすべての整数p , q ≥ 0に対して、次の加法公式関係が成り立つ。 $${\displaystyle j_{p+q}=k_{0,p}\cdot k_{0,q}+\sum _{i=1}^{\min(p,q)}{\text{ab}}_{2}\cdots {\text{ab}}_{i+1}\times k_{i,p}\cdot k_{i,q}.}$$

h ≥ 0 の場合（実際にはh ≥ 2の場合）、無限分数J ^[∞] ( z )に収束する有理h次数を次のように 定義できます。$${\displaystyle \operatorname {Conv} _{h}(z):={\frac {P_{h}(z)}{Q_{h}(z)}}=j_{0}+j_{1}z+\cdots +j_{2h-1}z^{2h-1}+\sum _{n=2h}^{\infty }{\widetilde {j}}_{h,n}z^{n}}$$

再帰的に定義されるシーケンスP _h ( z )およびQ _h ( z )を介して、コンポーネントごとに以下を実行します。 $${\displaystyle {\begin{aligned}P_{h}(z)&=(1-c_{h}z)P_{h-1}(z)-{\text{ab}}_{h}z^{2}P_{h-2}(z)+\delta _{h,1}\\Q_{h}(z)&=(1-c_{h}z)Q_{h-1}(z)-{\text{ab}}_{h}z^{2}Q_{h-2}(z)+(1-c_{1}z)\delta _{h,1}+\delta _{0,1}.\end{aligned}}}$$

さらに、すべてのh ≥ 2に対する収束関数Conv _h ( z )の有理性は、j _nの列によって満たされる追加の有限差分方程式と合同性の性質を意味し、M _h ≔ ab ₂ ⋯ ab _{h + 1}の場合、 h ‖ M _hであれば、合同性が得られます。 $${\displaystyle j_{n}\equiv [z^{n}]\operatorname {Conv} _{h}(z){\pmod {h}},}$$

h ≥ 2の場合、つまり、これらのシーケンスが、_以下の表に含まれる例のように_、 q、x、またはRなどの補助パラメータに暗黙的に依存しない場合、非記号的で確定的なパラメータシーケンス { ab i } および{ c i }の選択について。

次の表は、最初の小節で定義されたJ分数の一般展開によって生成される所定のシーケンスj _nのいくつかの特殊なケースにおいて、計算によって見出された（そして引用文献^{[ 22 ]}で正しさが証明された）成分シーケンスの閉形式公式の例を示しています。ここでは、0 < | a |、| b |、| q | < 1とパラメータを定義します。${\displaystyle R,\alpha \in \mathbb {Z} ^{+}}$また、x はこれらの展開に関して不定であり、これらのJ分数の展開によって列挙される所定の数列は、 q - ポッホハマー記号、ポッホハマー記号、および二項係数によって定義される。

上記のヤコビ型J分数の定義に対応するこれらの級数の収束半径は、一般に、これらの数列の通常の母関数を定義する対応するべき級数展開の収束半径とは異なります。

生成関数を用いることで、和を操作したり、和間の恒等式を確立したりするための様々な方法が得られる。

最も単純なケースは、s _n = Σ ⁿ _{k = 0} a _kの場合です。この場合、対応する通常の母関数については、 S ( z ) = ⁠ A ( z ) / 1 − z ⁠であることがわかります。

例えば、私たちは操作することができます $${\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}\,,}$$ ここで、H k ₌ 1 + 1 / 2 + ⋯ + 1 / kは調和数である。 $${\displaystyle H(z)=\sum _{n=1}^{\infty }{H_{n}z^{n}}}$$ 調和数の通常の母関数とする。すると $${\displaystyle H(z)={\frac {1}{1-z}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,,}$$ そしてこうして $${\displaystyle S(z)=\sum _{n=1}^{\infty }{s_{n}z^{n}}={\frac {1}{(1-z)^{2}}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,.}$$

使用 $${\displaystyle {\frac {1}{(1-z)^{2}}}=\sum _{n=0}^{\infty }(n+1)z^{n}\,,}$$分子との 畳み込みにより、$${\displaystyle s_{n}=\sum _{k=1}^{n}{\frac {n+1-k}{k}}=(n+1)H_{n}-n\,,}$$ これは次のように書くこともできます $${\displaystyle \sum _{k=1}^{n}{H_{k}}=(n+1)(H_{n+1}-1)\,.}$$

生成関数を使用して数列を関連付け、和を操作する別の例として、任意の数列⟨ f _n ⟩に対して、 2 つの和の数列を定義します。 $${\displaystyle {\begin{aligned}s_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}f_{m}3^{n-m}\\[4px]{\tilde {s}}_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}(m+1)(m+2)(m+3)f_{m}3^{n-m}\,,\end{aligned}}}$$すべてのn ≥ 0 に対して、2 番目の和を最初の和で表すことを目指します。生成関数によるアプローチを提案します。

まず、二項変換を用いて、最初の和の母関数を次のように書きます。 $${\displaystyle S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}}\right).}$$

数列⟨ ( n + 1)( n + 2)( n + 3) f _n ⟩の母関数は次のように与えられる。 $${\displaystyle 6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z)}$$ 上記で定義した2番目の和の母関数は、次の形式で記述できます。 $${\displaystyle {\tilde {S}}(z)={\frac {6}{(1-3z)}}F\left({\frac {z}{1-3z}}\right)+{\frac {18z}{(1-3z)^{2}}}F'\left({\frac {z}{1-3z}}\right)+{\frac {9z^{2}}{(1-3z)^{3}}}F''\left({\frac {z}{1-3z}}\right)+{\frac {z^{3}}{(1-3z)^{4}}}F'''\left({\frac {z}{1-3z}}\right).}$$

特に、この修正された和生成関数は、次の形式で表すことができます。 $${\displaystyle a(z)\cdot S(z)+b(z)\cdot zS'(z)+c(z)\cdot z^{2}S''(z)+d(z)\cdot z^{3}S'''(z),}$$ a ( z ) = 6(1 − 3 z ) ³、b ( z ) = 18(1 − 3 z ) ³、c ( z ) = 9(1 − 3 z ) ³、 およびd ( z ) = (1 − 3 z ) ^{3 の}場合、(1 − 3 z ) ³ = 1 − 9 z + 27 z ² − 27 z ^{3 です}。