母関数

Formal power series

数学において、生成関数とは、無限の数列を形式的な冪級数の係数として表現したものです。生成関数は、しばしば級数ではなく、形式的な級数に対する演算を含む何らかの式によって閉じた形で表現されます。

生成関数には、通常の生成関数、指数生成関数、ランバート級数、ベル級数、ディリクレ級数など、様々な種類があります。原理的には、すべての数列はそれぞれの種類の生成関数を持ちますが（ランバート級数とディリクレ級数では、添え字は0ではなく1から始まる必要があります）、それらの扱いやすさは大きく異なる場合があります。特定の状況において最も有用な生成関数（もし存在するとすれば）は、数列の性質と、扱われる問題の詳細によって異なります。

生成関数は生成級数と呼ばれることもあり、^[1]一連の項はその項係数の列の生成元であると言える。

歴史

生成関数は、一般線形回帰問題を解くために、1730年にアブラハム・ド・モアブルによって初めて導入されました。 ^[2]

ジョージ・ポリアは『数学ともっともらしい推論』の中でこう書いています。

「母関数」という名称はラプラスに由来する。しかし、ラプラスよりずっと以前、オイラーは母関数という概念を命名することなく用いていた[…]。彼はこの数学的手法を、組合せ解析学と数論におけるいくつかの問題に適用した。

意味

生成関数は、バッグに似た装置です。たくさんの小さな物をバラバラに持ち運ぶのは恥ずかしいかもしれませんが、代わりにそれらをすべてバッグに入れれば、持ち運ぶ物はバッグだけになります。

— ジョージ・ポリア『数学ともっともらしい推論』（1954年）

生成関数は、表示用に一連の数字を掛ける物干しロープです。

— ハーバート・ウィルフ、『生成機能学』（1994）

収束

通常の級数とは異なり、形式的 冪級数は収束する必要がない。実際、生成関数は関数とはみなされず、「変数」は不定値のままである。複数の不定値における形式的冪級数へと一般化することで、無限多次元の数配列に関する情報を符号化することができる。したがって、生成関数は、定義域から余定義域への写像という形式的な意味での関数ではない。

不定値 xを用いたこれらの式には、算術演算、 xに関する微分 、および他の生成関数との合成（すなわち代入）が含まれる場合があります。これらの演算は関数に対しても定義されているため、結果は xの関数のように見えます。実際、閉じた形式の式は、（十分に小さい）具体的なxの値で評価でき、その級数展開として形式級数を持つ関数として解釈できることがよくあります。これが「生成関数」という呼称の由来です。しかし、このような解釈は必ずしも可能である必要はありません。なぜなら、形式級数はxに非ゼロの数値を代入したときに 収束級数を与える必要はないからです。

制限事項

xの関数として意味のあるすべての式が、 形式級数を指定する式としても意味があるわけではありません。たとえば、  xの負の累乗と分数の累乗は、対応する形式級数を持たない関数の例です。

種類

通常生成関数（OGF）

生成関数という用語が修飾語なしで使用される場合、通常は通常の生成関数を意味します。数列a _nの通常の生成関数は次のとおりです。a n_が離散確率変数の確率質量関数である場合、その通常の生成関数は確率生成関数と呼ばれます。 $${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}$$

指数生成関数（EGF）

数列a _nの指数生成関数は $${\displaystyle \operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.}$$

一般に、ラベル付きオブジェクトを含む組み合わせ列挙問題では、指数生成関数は通常の生成関数よりも便利です。^[3]

指数母関数のもう一つの利点は、線形回帰関係を微分方程式の領域に応用できる点である。例えば、線形回帰関係f _{n +2} = f _{n +1} + f _nを満たすフィボナッチ数列 { f _n }を考えてみよう。これに対応する指数母関数は以下の形をとる 。 $${\displaystyle \operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}}$$

そして、その導関数は、上記の再帰関係と直接類似した微分方程式EF″( x ) = EF ′ ( x ) + EF( x )を満たすことが容易に示される。この見方では、階乗項n !は、 x ⁿに作用する微分演算子を正規化するための単なる逆項である。

ポアソン生成関数

数列a _nのポアソン生成関数は $${\displaystyle \operatorname {PG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}e^{-x}{\frac {x^{n}}{n!}}=e^{-x}\,\operatorname {EG} (a_{n};x).}$$

ランバート級数

数列a _nのランバート級数は、ランバート級数ではインデックスn は0 ではなく 1 から始まることに注意してください。そうでないと、最初の項が未定義になります。 $${\displaystyle \operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.}$$

整数n ≥ 1のべき級数展開におけるランバート級数の係数は、約数の和によって関係付けられる。本稿では、数論における特殊算術関数に関連した、より古典的な、あるいは少なくともよく知られた例をいくつか挙げている。本稿で示されていないランバート級数の恒等式の例として、 | x |、| xq | < 1に対して、次が成り立つことを示すことができる^[4]。 $${\displaystyle b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x)}$$ $${\displaystyle b_{n}=\sum _{d|n}a_{d}.}$$ $${\displaystyle \sum _{n=1}^{\infty }{\frac {q^{n}x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {q^{n}x^{n^{2}}}{1-qx^{n}}}+\sum _{n=1}^{\infty }{\frac {q^{n}x^{n(n+1)}}{1-x^{n}}},}$$

ここで、除数関数の生成関数d ( n ) ≡ σ ₀ ( n )の特別な場合の恒等式は次のように与えられる。 $${\displaystyle \sum _{n=1}^{\infty }{\frac {x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {x^{n^{2}}\left(1+x^{n}\right)}{1-x^{n}}}.}$$

ベルシリーズ

数列a _nのベル級数は不定数xと素数pの両方を用いた表現であり、次のように与えられる: ^[5] $${\displaystyle \operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.}$$

ディリクレ級数生成関数（DGF）

形式的ディリクレ級数は厳密には形式的冪級数ではないものの、しばしば生成関数として分類される。数列a _nのディリクレ級数生成関数は以下の通りである: ^[6] $${\displaystyle \operatorname {DG} (a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.}$$

ディリクレ級数生成関数は、_nが乗法関数である場合に特に有用であり、その場合には関数のベル級数に関してオイラー積表現^{[7]を持つ。} $${\displaystyle \operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,.}$$

n_がディリクレ指標である場合、そのディリクレ級数生成関数はディリクレL級数と呼ばれる。また、上記のランベルト級数展開における係数のペアとそのDGFの間には関係がある。すなわち、 ζ ( s )がリーマンゼータ関数である場合、かつその場合のみ、次の関係が証明できる。 [ ^8] $${\displaystyle [x^{n}]\operatorname {LG} (a_{n};x)=b_{n}}$$ $${\displaystyle \operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s),}$$

ディリクレ級数生成関数（DGF）によって生成されるシーケンスa _kは、次の通常の生成関数を持ちます。 $${\displaystyle \operatorname {DG} (a_{k};s)=\zeta (s)^{m}}$$ $${\displaystyle \sum _{k=1}^{k=n}a_{k}x^{k}=x+{\binom {m}{1}}\sum _{2\leq a\leq n}x^{a}+{\binom {m}{2}}{\underset {ab\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }}}x^{ab}+{\binom {m}{3}}{\underset {abc\leq n}{\sum _{a=2}^{\infty }\sum _{c=2}^{\infty }\sum _{b=2}^{\infty }}}x^{abc}+{\binom {m}{4}}{\underset {abcd\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }}}x^{abcd}+\cdots }$$

多項式列生成関数

生成関数の考え方は、他のオブジェクトの列にも拡張できます。例えば、二項式型の多項式列は次のように生成されます。ここで、 p _n ( x )は多項式の列、f ( t )は特定の形式の関数です。シェファー列も同様の方法で生成されます。詳細については、一般化されたアペル多項式に関するメイン記事を参照してください。 $${\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}}$$

より複雑な生成関数によって生成される多項式シーケンスの例には次のものがあります。

• アペル多項式
• チェビシェフ多項式
• 差分多項式
• 一般化アペル多項式
• q差分多項式

その他の生成関数

より複雑な生成関数によって生成される他のシーケンスには次のものがあります。

• 二重指数生成関数
• 生成関数と対角生成関数のアダマール積、およびそれに対応する積分変換

畳み込み多項式

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

deg f _n ≤ nかつすべてのx、yおよびすべてのn ≥ 0に対して次の畳み込み条件が成り立つ場合、多項式族f ₀、f ₁、f ₂、 ...は畳み込み族を形成すると言います。 $${\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 !· fn ( 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}}}$$

固定された非ゼロパラメータに対して、これらの畳み込み多項式列に対する生成関数は次のように修正される。_{ここで、𝓕 t ( z ) は、𝓕 t ( z ) = F ( x𝓕 t} ( z ₎ t )という形式_の関数方程式によって暗黙的に定義される。^さらに、行列法（参考文献にあるように）を用いて、2つの畳み込み多項式列⟨ f _n ( x ) ⟩と⟨ g _n ( x ) ⟩が与えられ、それぞれに対応する生成関数F ( z ) ^xとG ( z ) ^xが与えられれば、任意のtに対して、次の恒等式が成り立つことを証明できる。 ${\displaystyle t\in \mathbb {C} }$ $${\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n}\right]{\mathcal {F}}_{t}(z)^{x},}$$ $${\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 )、ラゲール多項式、スターリング畳み込み多項式などがあります。

通常の生成関数

単純なシーケンスの例

多項式は通常の母関数の特殊なケースであり、有限列、あるいはある点以降は消滅する列に対応します。ポアンカレ多項式など、多くの有限列が母関数として解釈できることから、多項式は重要です。

基本的な生成関数は定数列1, 1, 1, 1, 1, 1, 1, 1, 1, ...の関数であり、その通常の生成関数は等比級数である。 $${\displaystyle \sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}.}$$

左辺は右辺のマクローリン級数展開である。あるいは、左辺の冪級数に1 − xを乗じ、その結果が定数冪級数 1 （つまり、x ⁰の係数を除くすべての係数が 0 に等しい）であることを確認することで、等式が成り立つことを証明できる。さらに、この性質を持つ冪級数は他に存在しない。したがって、左辺は冪級数環における1 − xの逆数を表す。

他の数列の通常の生成関数の式は、この式から容易に導出できます。例えば、x → axと代入すると、任意の定数aに対する等比数列 1, a , a ² , a ³ , ...の生成関数が得られます。 $${\displaystyle \sum _{n=0}^{\infty }(ax)^{n}={\frac {1}{1-ax}}.}$$

（この等式は、左辺が右辺のマクローリン級数展開であるという事実からも直接導かれる。）特に、 $${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}x^{n}={\frac {1}{1+x}}.}$$

xをxのべき乗で置き換えることで、シーケンスに規則的なギャップを導入することもできます。たとえば、シーケンス1、0、1、0、1、0、1、0、... （ x、x ³、x ⁵、...をスキップします）の場合、生成関数は次のようになります。 $${\displaystyle \sum _{n=0}^{\infty }x^{2n}={\frac {1}{1-x^{2}}}.}$$

初期生成関数を2乗するか、両辺のxに関する微分を求め、変数nをn + 1に変更すると、係数が1、2、3、4、5、…という数列を形成することがわかります。したがって、 $${\displaystyle \sum _{n=0}^{\infty }(n+1)x^{n}={\frac {1}{(1-x)^{2}}},}$$

そして、その３乗は、１、３、６、１０、１５、２１、…の三角数 を係数とし、その項nは二項係数である（ ^{n + 2}
₂）、 となることによって $${\displaystyle \sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{n}={\frac {1}{(1-x)^{3}}}.}$$

より一般的には、任意の非負整数kと非ゼロ実数値aに対して、 $${\displaystyle \sum _{n=0}^{\infty }a^{n}{\binom {n+k}{k}}x^{n}={\frac {1}{(1-ax)^{k+1}}}\,.}$$

以来 $${\displaystyle 2{\binom {n+2}{2}}-3{\binom {n+1}{1}}+{\binom {n}{0}}=2{\frac {(n+1)(n+2)}{2}}-3(n+1)+1=n^{2},}$$

二項係数生成列の線形結合によって、平方数列0、1、4、9、16、…の通常の生成関数を求めることができます。 $${\displaystyle G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {2}{(1-x)^{3}}}-{\frac {3}{(1-x)^{2}}}+{\frac {1}{1-x}}={\frac {x(x+1)}{(1-x)^{3}}}.}$$

交互に拡張して、同じ平方のシーケンスを、次の形式で等比級数の導関数の合計として生成することもできます。 $${\displaystyle {\begin{aligned}G(n^{2};x)&=\sum _{n=0}^{\infty }n^{2}x^{n}\\[4px]&=\sum _{n=0}^{\infty }n(n-1)x^{n}+\sum _{n=0}^{\infty }nx^{n}\\[4px]&=x^{2}D^{2}\left[{\frac {1}{1-x}}\right]+xD\left[{\frac {1}{1-x}}\right]\\[4px]&={\frac {2x^{2}}{(1-x)^{3}}}+{\frac {x}{(1-x)^{2}}}={\frac {x(x+1)}{(1-x)^{3}}}.\end{aligned}}}$$

帰納法により、正の整数m ≥ 1に対しても同様に証明できる^{[10] [11]} $${\displaystyle n^{m}=\sum _{j=0}^{m}{\begin{Bmatrix}m\\j\end{Bmatrix}}{\frac {n!}{(n-j)!}},}$$

どこ{ⁿ
_k}は第二種スターリング数を表し、生成関数は $${\displaystyle \sum _{n=0}^{\infty }{\frac {n!}{(n-j)!}}\,z^{n}={\frac {j!\cdot z^{j}}{(1-z)^{j+1}}},}$$

となるので、上記の平方根の場合の結果を一般化して、 m乗の整数に対する同様の生成関数を形成することができる。特に、 $${\displaystyle {\frac {z^{k}}{(1-z)^{k+1}}}=\sum _{i=0}^{k}{\binom {k}{i}}{\frac {(-1)^{k-i}}{(1-z)^{i+1}}},}$$

スターリング数を含むよく知られた有限和恒等式を適用して[ ^12] $${\displaystyle \sum _{n=0}^{\infty }n^{m}z^{n}=\sum _{j=0}^{m}{\begin{Bmatrix}m+1\\j+1\end{Bmatrix}}{\frac {(-1)^{m-j}j!}{(1-z)^{j+1}}}.}$$

有理関数

数列の通常の生成関数は、数列が定数係数の線型再帰数列である場合に限り、有理関数（2つの有限次多項式の比）として表すことができます。これは上記の例を一般化したものです。逆に、分数の多項式によって生成されるすべての数列は、定数係数の線型再帰を満たします。これらの係数は、分数の分母多項式の係数と同一です（したがって、直接読み取ることができます）。この観察は、定数係数の線型有限差分方程式によって定義される数列の生成関数を簡単に解くことができ、したがって、これらの生成関数の係数の明示的な閉じた形式の式を簡単に解くことができることを示しています。ここでの典型的な例は、生成関数の手法によってフィボナッチ数列のビネの式を導くことです。

また、有理生成関数のクラスは、次の形式の準多項式列を列挙する生成関数と正確に対応していることにも気づく^[13]。 $${\displaystyle f_{n}=p_{1}(n)\rho _{1}^{n}+\cdots +p_{\ell }(n)\rho _{\ell }^{n},}$$

ここで、逆根、は固定されたスカラーであり、p _i ( n )はすべての1 ≤ i ≤ ℓに対してnの多項式です。 ${\displaystyle \rho _{i}\in \mathbb {C} }$

一般に、有理関数のアダマール積は有理関数を生成する。同様に、 $${\displaystyle F(s,t):=\sum _{m,n\geq 0}f(m,n)w^{m}z^{n}}$$

が二変数有理数生成関数である場合、対応する対角生成関数は、 $${\displaystyle \operatorname {diag} (F):=\sum _{n=0}^{\infty }f(n,n)z^{n},}$$

は代数的である。例えば、^[14] $${\displaystyle F(s,t):=\sum _{i,j\geq 0}{\binom {i+j}{i}}s^{i}t^{j}={\frac {1}{1-s-t}},}$$

この生成関数の対角係数生成関数は、よく知られたOGF式で与えられる。 $${\displaystyle \operatorname {diag} (F)=\sum _{n=0}^{\infty }{\binom {2n}{n}}z^{n}={\frac {1}{\sqrt {1-4z}}}.}$$

この結果は、コーシーの積分公式や等高線積分、複素留数の取得、 2 つの変数の形式的なべき級数の直接操作など、さまざまな方法で計算されます。

生成関数の演算

掛け算は畳み込みを生み出す

通常の母関数の乗算は、列の離散畳み込み（コーシー積）となる。例えば、通常の母関数G ( a _n ; x )を持つ列の累積和の列（やや一般的なオイラー・マクローリンの公式と比較） は、以下の理由から母関数を持つ。⁠ $${\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )}$$ $${\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}}}$$

第二恒等式の微分乗算を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​/1つの⁠は の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}).}$$

P-再帰的列とホロノミック生成関数

定義

形式的な冪級数（または関数）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,}$$

十分に大きいn ≥ n ₀に対して成り立ち、ĉ _i ( n )はnの固定された有限次多項式である。言い換えれば、列がP再帰的であることとホロノミックな生成関数を持つことは同値である。ホロノミック関数は、生成関数上のアダマール積演算⊙に関して閉じている。

例

関数e ^z、log z、cos z、arcsin z、、二重対数関数Li ₂ ( z )、一般化超幾何関数_p F _q (...; ...; z )、およびべき級数によって定義される関数 ${\displaystyle {\sqrt {1+z}}}$ $${\displaystyle \sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2}}}}$$

そして非収束なものはすべてホロノミックです。 $${\displaystyle \sum _{n=0}^{\infty }n!\cdot z^{n}}$$

ホロノミック生成関数を持つP再帰列の例としては、f _n ≔ ⁠などが挙げられる。1/n + 1⁠ （^{2 n}
_n)およびf _n ≔ ⁠2 ⁿ/n ² + 1⁠ 、およびlog nのような数列は、対応する生成関数の特異点の性質により、 P再帰的ではありません。同様に、 tan z、 sec z、 Γ( z )など、無限個の特異点を持つ関数はホロノミック関数ではありません。 ${\displaystyle {\sqrt {n}}}$

作業用ソフトウェアP-再帰的列とホロノミック生成関数

MathematicaにおけるP再帰列の処理および操作ツールには、RISC Combinatorics Group のアルゴリズム的組合せ論ソフトウェアサイトで非商用利用向けに提供されているソフトウェアパッケージが含まれます。これらのソフトウェアパッケージは大部分がクローズドソースですが、特に強力なツールとして、任意の入力列に対するP再帰を推測するパッケージ（実験数学や探究に有用）と、多くの和に対する P 再帰を見つけ、一般化調和数を含むP再帰の閉形式解を求めるパッケージが提供されています。^[18]この RISC サイトに掲載されている他のパッケージは、ホロノミック生成関数を扱うことに特化したものです。GuessSigma

離散時間フーリエ変換との関係

級数が絶対収束する場合、 は数列a ₀、a ₁、 ...の離散時間フーリエ変換です。 $${\displaystyle G\left(a_{n};e^{-i\omega }\right)=\sum _{n=0}^{\infty }a_{n}e^{-i\omega n}}$$

数列の漸近的成長

微積分学では、冪級数の係数の増加率を用いて、冪級数の収束半径を推定することがしばしばあります。逆もまた成り立ち、生成関数の収束半径を用いて、その基となる数列の漸近的増加を推定することもしばしばあります。

例えば、有限の収束半径rを持つ通常の生成関数G ( a _n ; x )は次のように書けます。 $${\displaystyle G(a_{n};x)={\frac {A(x)+B(x)\left(1-{\frac {x}{r}}\right)^{-\beta }}{x^{\alpha }}}}$$

ここで、 A ( x )とB ( x )はそれぞれ、収束半径がrより大きい（または完全）まで解析的な関数であり、 B ( r ) ≠ 0の場合には 、ガンマ関数、二項係数、または多重集合係数を使用します。n が無限大に近づくにつれて、これらの式のいずれかに対するa nの比の極限は 1 になることが保証されます。これは、 a _nが単にそれらに比例するという_意味ではありません。 $${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}\sim {\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}}\right)^{n}={\frac {B(r)}{r^{\alpha }}}\left(\!\!{\binom {\beta }{n}}\!\!\right)\left({\frac {1}{r}}\right)^{n}\,,}$$

_{このアプローチは、多くの場合、n}の漸近級数の複数の項を生成するために反復される。特に、 $${\displaystyle G\left(a_{n}-{\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}}\right)^{n};x\right)=G(a_{n};x)-{\frac {B(r)}{r^{\alpha }}}\left(1-{\frac {x}{r}}\right)^{-\beta }\,.}$$

この生成関数の係数の漸近的増加は、上記のように生成関数を記述するためのA、B、α、β、およびrを見つけることによって求めることができます。

指数生成関数についても同様の漸近解析が可能である。指数生成関数の場合、⁠1_つの/ん！⁠はこれらの漸近公式に従って増大します。一般的に、ある数列の生成関数から別の数列の生成関数を引いたときの収束半径が、個々の生成関数の収束半径よりも大きい場合、2つの数列は同じ漸近成長を示します。

正方形列の漸近的成長

上記で導出したように、正方形の列の通常の生成関数は次のようになります。 $${\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変数の場合は、これらはしばしば2変数母関数と呼ばれます。

二変量の場合

2次元配列a _{m , n}（nとmは自然数）の通常の生成関数は次の通りです。例えば、(1 + x ) ⁿは固定されたnに対する二項係数の通常の生成関数なので、二項係数を生成する二変数生成関数を求めることができます（ $${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.}$$ⁿ
_k)が成り立つ。これを行うには、(1 + x ) n 自体を n 内の数列とみなし、これらの数列^の値を係数とするy内の生成関数を求める。n の生成関数は次の通りであるので、二項係数の生成関数は次の通りである。^その他の例としては、二項係数、スターリング数、オイラー数に対する以下の2変数生成関数が挙げられるここで、ωとz は2つの変数を表す。 ^[19] $${\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}}.}$$ $${\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-分数)

定義

h次の有理収束が2 h次精度のべき級数を表す（形式的な）ヤコビ型連分数（それぞれJ分数とS分数）の展開は、多くの特殊な 1 変数および2変数 数列の典型的に発散する通常の生成関数を表現する別の方法です。ヤコビ型連分数（J分数）の特定の形式は、次の式のように展開され、いくつかの特定の、アプリケーション依存の成分数列{ab _i }および{ ci _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}}}$$

前の式でj _n ≔ [ z ⁿ ] J ^[∞] ( z )と略記されたの係数は、次の式の行列解に対応する。 ${\displaystyle z^{n}}$ $${\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、j _n = k _{0, n} ( n ≥ 1 )、k _r、s = 0 (r > sの場合)、すべての整数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収束関数

h ≥ 0（実際にはh ≥ 2 ）の場合、無限J分数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分数の一般展開によって生成された所定のシーケンスjnのいくつかの特殊なケースで計算的に見つかった（そして後に引用文献^{[22]で正しいことが証明された）成分シーケンスの閉じた形式の式の}_例を示しています。ここでは、0 < | a |、| b |、| q | < 1を定義し、パラメータとxはこれらの展開に関して不定であるとします。ここで、これらのJ分数の展開によって列挙された所定のシーケンスは、 q-ポッホハンマー記号、ポッホハンマー記号、および二項係数で定義されます。 ${\displaystyle R,\alpha \in \mathbb {Z} ^{+}}$

${\displaystyle j_{n}}$	${\displaystyle c_{1}}$	${\displaystyle c_{i}(i\geq 2)}$	${\displaystyle \mathrm {ab} _{i}(i\geq 2)}$
${\displaystyle q^{n^{2}}}$	${\displaystyle q}$	${\displaystyle q^{2h-3}\left(q^{2h}+q^{2h-2}-1\right)}$	${\displaystyle q^{6h-10}\left(q^{2h-2}-1\right)}$
${\displaystyle (a;q)_{n}}$	${\displaystyle 1-a}$	${\displaystyle q^{h-1}-aq^{h-2}\left(q^{h}+q^{h-1}-1\right)}$	${\displaystyle aq^{2h-4}\left(aq^{h-2}-1\right)\left(q^{h-1}-1\right)}$
${\displaystyle \left(zq^{-n};q\right)_{n}}$	${\displaystyle {\frac {q-z}{q}}}$	${\displaystyle {\frac {q^{h}-z-qz+q^{h}z}{q^{2h-1}}}}$	${\displaystyle {\frac {\left(q^{h-1}-1\right)\left(q^{h-1}-z\right)\cdot z}{q^{4h-5}}}}$
${\displaystyle {\frac {(a;q)_{n}}{(b;q)_{n}}}}$	${\displaystyle {\frac {1-a}{1-b}}}$	${\displaystyle {\frac {q^{i-2}\left(q+abq^{2i-3}+a(1-q^{i-1}-q^{i})+b(q^{i}-q-1)\right)}{\left(1-bq^{2i-4}\right)\left(1-bq^{2i-2}\right)}}}$	${\displaystyle {\frac {q^{2i-4}\left(1-bq^{i-3}\right)\left(1-aq^{i-2}\right)\left(a-bq^{i-2}\right)\left(1-q^{i-1}\right)}{\left(1-bq^{2i-5}\right)\left(1-bq^{2i-4}\right)^{2}\left(1-bq^{2i-3}\right)}}}$
${\displaystyle \alpha ^{n}\cdot \left({\frac {R}{\alpha }}\right)_{n}}$	${\displaystyle R}$	${\displaystyle R+2\alpha (i-1)}$	${\displaystyle (i-1)\alpha {\bigl (}R+(i-2)\alpha {\bigr )}}$
${\displaystyle (-1)^{n}{\binom {x}{n}}}$	${\displaystyle -x}$	${\displaystyle -{\frac {(x+2(i-1)^{2})}{(2i-1)(2i-3)}}}$	${\displaystyle {\begin{cases}-{\dfrac {(x-i+2)(x+i-1)}{4\cdot (2i-3)^{2}}}&{\text{for }}i\geq 3;\\[4px]-{\frac {1}{2}}x(x+1)&{\text{for }}i=2.\end{cases}}}$
${\displaystyle (-1)^{n}{\binom {x+n}{n}}}$	${\displaystyle -(x+1)}$	${\displaystyle {\frac {{\bigl (}x-2i(i-2)-1{\bigr )}}{(2i-1)(2i-3)}}}$	${\displaystyle {\begin{cases}-{\dfrac {(x-i+2)(x+i-1)}{4\cdot (2i-3)^{2}}}&{\text{for }}i\geq 3;\\[4px]-{\frac {1}{2}}x(x+1)&{\text{for }}i=2.\end{cases}}}$

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

例

平方数

平方数列 a _n = n ²の生成関数は次のとおりです。

生成関数型	方程式
通常の生成関数	${\displaystyle G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {x(x+1)}{(1-x)^{3}}}}$
指数生成関数	${\displaystyle \operatorname {EG} (n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}}$
ベルシリーズ	${\displaystyle \operatorname {BG} _{p}\left(n^{2};x\right)=\sum _{n=0}^{\infty }\left(p^{n}\right)^{2}x^{n}={\frac {1}{1-p^{2}x}}}$
ディリクレ級数	${\displaystyle \operatorname {DG} \left(n^{2};s\right)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2)}$

ここでζ ( s)はリーマンゼータ関数である。

アプリケーション

生成関数は次の目的で使用されます。

• フィボナッチ数などの再帰関係で与えられた数列の閉じた式を見つけます。
• シーケンスの再帰関係を見つけます。生成関数の形式から再帰式が推測される場合があります。
• シーケンス間の関係を見つけます。2 つのシーケンスの生成関数が類似した形式である場合、シーケンス自体が関連している可能性があります。
• シーケンスの漸近的な動作を調べます。
• シーケンスを含む同一性を証明します。
• 組合せ論における列挙問題を解き、その解を符号化します。ルーク多項式は組合せ論における応用例です。
• 無限和を評価します。

さまざまなテクニック：和の評価と生成関数を使ったその他の問題への取り組み

例1: 調和数の和の公式

生成関数を使用すると、合計を操作したり、合計間の同一性を確立したりするためのいくつかの方法が得られます。

最も単純なケースは、s _n = Σのときである。ⁿ
_{k = 0} a _k。すると、 S ( z ) = ⁠A ( z )/1 − z⁠対応する通常の生成関数の場合。

例えば、 H _k = 1 + ⁠を操作できる。 $${\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}\,,}$$1/2⁠ + ⋯ + ⁠1/け⁠は調和数である。調和数の通常の生成関数を とする。すると、したがって $${\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)\,.}$$

例2: 修正二項係数和と二項変換

生成関数を用いて列を関連付け、和を操作する別の例として、任意の列⟨ f _n ⟩に対して、すべてのn ≥ 0に対して2つの和の列を定義し、2つ目の和を1つ目の和で表すことを試みます。生成関数を用いたアプローチを提案します。 $${\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}}}$$

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

数列⟨ ( n + 1)( n + 2)( n + 3) f _n ⟩の生成関数は次のように与えられる ので、上で定義した2番目の和の生成関数は次の式で表すことができる。 $${\displaystyle 6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z)}$$ $${\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).}$$

特に、この修正された和生成関数は、 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 ) 3 = ¹ − 9 z + 27 z ² − 27 z 3） ）^の形式で表記できます。 $${\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),}$$

最後に、2 番目の合計から 1 番目の合計までを次の形式で表すことができます。 $${\displaystyle {\begin{aligned}{\tilde {s}}_{n}&=[z^{n}]\left(6(1-3z)^{3}\sum _{n=0}^{\infty }s_{n}z^{n}+18(1-3z)^{3}\sum _{n=0}^{\infty }ns_{n}z^{n}+9(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)s_{n}z^{n}+(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)(n-2)s_{n}z^{n}\right)\\[4px]&=(n+1)(n+2)(n+3)s_{n}-9n(n+1)(n+2)s_{n-1}+27(n-1)n(n+1)s_{n-2}-(n-2)(n-1)ns_{n-3}.\end{aligned}}}$$

例3: 相互再帰列の生成関数

この例では、 『Concrete Mathematics』のセクション 7.3 に示されている生成関数の例を再定式化します(生成関数級数のわかりやすい図については、同じ参考文献のセクション 7.1 も参照)。特に、マークされていない 2 バイ 1 のドミノ ピースで3 バイnの長方形を敷き詰める方法の総数 ( U _nで表記) を求めるとします。補助列V _nを、長方形全体の 3 バイn の角を除いた部分を覆う方法の数として定義します。これらの定義を使用して、垂直ドミノと水平ドミノの場合を扱うためにこの定義をさらに細分化することなく、 U _nの閉じた形式の式を求めます。2 つの列の通常の生成関数は、次の級数に対応することに注意してください。 $${\displaystyle {\begin{aligned}U(z)=1+3z^{2}+11z^{4}+41z^{6}+\cdots ,\\V(z)=z+4z^{3}+15z^{5}+56z^{7}+\cdots .\end{aligned}}}$$

3行n列の長方形の左端から始まる可能性のある構成を考慮すると、U 0 = 1、U ₁ = 0、V ₀ = 0、V ₁ = 1の場合、上記のように定義されるn ≥ 2のときの2つのシーケンスについて、次のような相互に依存する、または相互に再帰的な再帰関係を表すことが_できます。 $${\displaystyle {\begin{aligned}U_{n}&=2V_{n-1}+U_{n-2}\\V_{n}&=U_{n-1}+V_{n-2}.\end{aligned}}}$$

すべての整数m ≥ 0に対して、インデックスシフトされた生成関数は^[注1]を満たすので 、上で指定した初期条件と前の2つの再帰関係を使用して、これらのシーケンスの生成関数を関連付ける次の2つの式が得られます。これは、方程式のシステムを解くことによって（そしてこれがここでの私たちの方法の特別なトリックです）、次の式が成り立ちます。 $${\displaystyle z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\,,}$$ $${\displaystyle {\begin{aligned}U(z)&=2zV(z)+z^{2}U(z)+1\\V(z)&=zU(z)+z^{2}V(z)={\frac {z}{1-z^{2}}}U(z),\end{aligned}}}$$ $${\displaystyle U(z)={\frac {1-z^{2}}{1-4z^{2}+z^{4}}}={\frac {1}{3-{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2+{\sqrt {3}}\right)z^{2}}}+{\frac {1}{3+{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2-{\sqrt {3}}\right)z^{2}}}.}$$

したがって、前式の母関数の2次部分分数展開から得られる数列を代数的に簡略化すると、U _{2 n + 1} ≡ 0となり、すべての整数n ≥ 0に対して成立することが分かります。また、フィボナッチ数列の2次回帰式に適用された同じシフト母関数の手法は、上記の有理関数の節で既に説明した、あるいは少なくとも示唆した、1変数の回帰関係を母関数を用いて解く典型的な例であることにも留意してください。 $${\displaystyle U_{2n}=\left\lceil {\frac {\left(2+{\sqrt {3}}\right)^{n}}{3-{\sqrt {3}}}}\right\rceil \,,}$$

畳み込み（コーシー積）

2 つの形式的なべき級数の項の離散畳み込みにより、生成関数の積は、元の流れの項の畳み込み和を列挙する生成関数に変換されます (コーシー積を参照)。

1. A ( z )とB ( z )は通常の生成関数であるとします。 $${\displaystyle C(z)=A(z)B(z)\Leftrightarrow [z^{n}]C(z)=\sum _{k=0}^{n}{a_{k}b_{n-k}}}$$
2. A ( z )とB ( z )が指数生成関数であるとします。 $${\displaystyle C(z)=A(z)B(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}}\right]C(z)=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{n-k}}$$
3. 3つの通常の生成関数の積から得られる三重畳列を考える $${\displaystyle C(z)=F(z)G(z)H(z)\Leftrightarrow [z^{n}]C(z)=\sum _{j+k+l=n}f_{j}g_{k}h_{l}}$$
4. ある正の整数m≥1に対して、シーケンスのm倍畳み込みを考える（応用については以下の例を参照）。 $${\displaystyle C(z)=G(z)^{m}\Leftrightarrow [z^{n}]C(z)=\sum _{k_{1}+k_{2}+\cdots +k_{m}=n}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}}$$

生成関数の乗算、あるいはそれらの基礎となる列の畳み込みは、特定の計数および確率シナリオにおける独立事象の概念に対応する場合がある。例えば、確率変数Zの確率生成関数（pgf ）をG _Z ( z )と表記するという表記規則を採用すると、任意の2つの確率変数^[23]について 、XとYが独立であることを示すことができる。 $${\displaystyle G_{X+Y}(z)=G_{X}(z)G_{Y}(z)\,,}$$

例: 両替問題

コインの額面金額が{1, 5, 10, 25, 50} （つまり、ペニー、ニッケル、ダイム、クォーター、ハーフドル）の集合に含まれる場合、 n ≥ 0セントを支払う方法の数は、各コインの合計数に基づいてインスタンスを区別しますが、コインが提示される順序に基づいてインスタンスを区別しない場合、通常の生成関数によって与えられます。コインが提示される順序に基づいても区別する場合（たとえば、1ペニーの次に1ニッケルと、1ニッケルの次に1ペニーの場合とは異なります）、通常の生成関数は次のようになります。 $${\displaystyle {\frac {1}{1-z}}{\frac {1}{1-z^{5}}}{\frac {1}{1-z^{10}}}{\frac {1}{1-z^{25}}}{\frac {1}{1-z^{50}}}\,.}$$ $${\displaystyle {\frac {1}{1-z-z^{5}-z^{10}-z^{25}-z^{50}}}\,.}$$

nセントを任意の正の整数単位の硬貨で支払うことを許すと、分割関数の通常の生成関数を無限のq-ポッホハマー記号積で拡張したものに到達します 。硬貨の順序が重要な場合、通常の生成関数は次のようになります。 $${\displaystyle \prod _{n=1}^{\infty }\left(1-z^{n}\right)^{-1}\,.}$$ $${\displaystyle {\frac {1}{1-\sum _{n=1}^{\infty }z^{n}}}={\frac {1-z}{1-2z}}\,.}$$

例: カタラン数の生成関数

生成関数の畳み込みが有用な例として、カタラン数の通常の生成関数を表す特定の閉形式関数C _nを解くことができます。特に、この数列は、積x ₀ · x ₁ ·⋯· x _nに括弧を挿入して乗算の順序を完全に指定する方法の数として、組み合わせ論的に解釈できます。たとえば、C ₂ = 2は、2つの式x ₀ · ( x ₁ · x ₂ )と( x ₀ · x ₁ ) · x ₂に対応します。したがって、数列はで示される再帰関係を満たし、対応する畳み込み生成関数C ( z )は次式を満たします。 $${\displaystyle C_{n}=\sum _{k=0}^{n-1}C_{k}C_{n-1-k}+\delta _{n,0}=C_{0}C_{n-1}+C_{1}C_{n-2}+\cdots +C_{n-1}C_{0}+\delta _{n,0}\,,\quad n\geq 0\,,}$$ $${\displaystyle C(z)=z\cdot C(z)^{2}+1\,.}$$

C (0) = 1 ≠ ∞なので、この生成関数の式は次のようになる。 $${\displaystyle C(z)={\frac {1-{\sqrt {1-4z}}}{2z}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}z^{n}\,.}$$

上記のC ( z )を暗黙的に定義する最初の式は、この生成関数の別の「単純な」（形式の）連分数展開につながることを意味することに注意してください。 $${\displaystyle C(z)={\frac {1}{1-z\cdot C(z)}}\,,}$$

例: ファンの全域木と畳み込みの畳み込み

次数nのファンは、頂点{0, 1, ..., n }上のグラフで、2 n − 1本の辺が次の規則に従って接続されているものと定義されます。頂点 0 は、他のn個の頂点のそれぞれに単一の辺で接続されており、頂点は、常に1 ≤ k < nに対して、次の頂点k + 1に単一の辺で接続されています。^[24]次数 1 のファンは 1 つ、次数 2 のファンは 3 つ、次数 3 のファンは 8 つ、などとなります。全域木は、元の頂点がすべて含まれ、この部分グラフを接続するのに十分な辺を含みますが、部分グラフにサイクルが存在するほど多くの辺は含まないグラフの部分グラフです。各n ≥ 1に対して、次数nのファンの全域木f _nがいくつ存在するかを調べます。 ${\displaystyle k}$

観察として、隣接する頂点の集合を繋ぐ方法の数を数えることで、この問題にアプローチすることができます。例えば、n = 4 のとき、f ₄ = 4 + 3 · 1 + 2 · 2 + 1 · 3 + 2 · 1 · 1 + 1 · 2 · 1 + 1 · 1 · 2 + 1 · 1 · 1 · 1 = 21 となり、これはg _n = n = [ z ⁿ ] ⁠ のm重畳の和です。z/（1 − z）²⁠ m ≔ 1, 2, 3, 4の場合。より一般的には、この数列の式は次のように書けます。この数列の通常の生成関数は次の畳み込みの和で与えられ、最後の生成関数の部分分数展開をとることで数列の正確な式を抽出できます $${\displaystyle f_{n}=\sum _{m>0}\sum _{\scriptstyle k_{1}+k_{2}+\cdots +k_{m}=n \atop \scriptstyle k_{1},k_{2},\ldots ,k_{m}>0}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}\,,}$$ $${\displaystyle F(z)=G(z)+G(z)^{2}+G(z)^{3}+\cdots ={\frac {G(z)}{1-G(z)}}={\frac {z}{(1-z)^{2}-z}}={\frac {z}{1-3z+z^{2}}}\,,}$$

暗黙生成関数とラグランジュ逆関数公式

生成関数は、明示的な指定ではなく、関数方程式で指定されることがよくある。例えば、n個のノード（葉を含む）上の二分木の数を生成する関数T(z)は、次式を満たす。

$${\displaystyle T(z)=z\left(1+T(z)^{2}\right)}$$

ラグランジュの逆定理は、このような方程式の解を明示的に評価するために使用されるツールです。

ラグランジュ逆行列公式—を非零定数項を持つ形式的冪級数とする。すると、関数方程式はにおいて唯一の解を持ち、これは次式を満たす 。 ${\textstyle \phi (z)\in C[[z]]}$ $${\displaystyle T(z)=z\phi (T(z))}$$ ${\textstyle T(z)\in C[[z]]}$

${\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(\phi (z))^{n}}$

ここで、表記はにおけるの係数を返します。 ${\displaystyle [z^{n}]F(z)}$ ${\displaystyle z^{n}}$ ${\displaystyle F(z)}$

上記の定理を関数方程式に適用すると、次の式が得られます（）。 ${\textstyle \phi (z)=1+z^{2}}$

$${\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}}$$

二項定理展開により、 が偶数の場合、式は を返します。これは、二分木の葉の数は内部の節点の数より1つ多いことが証明されているため、総和は常に奇数になるはずであることから予想されることです。しかし、 が奇数の場合、 ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle n}$

${\displaystyle [z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}={\frac {1}{n}}{\dbinom {n}{\frac {n+1}{2}}}}$

を内部ノードの数とすると、式ははるかに簡潔になります。これで、式は単に^番目のカタラン数になります。 ${\displaystyle n}$ ${\displaystyle n}$

フリーパラメータの導入（スネークオイル法）

和s _nが複雑な場合、必ずしも簡単に評価できるとは限りません。「フリーパラメータ法」は、これらの和を評価する別の方法です（H. Wilf は「snake oil（蛇油）」と呼んでいます）。

これまで議論してきたどちらの手法も、n を総和の極限としています。n が総和に明示的に現れない場合は、n を「自由」なパラメータとみなし、s _{n を}F ( z ) = Σ s _n z ⁿの係数として扱い、 nとkの和の順序を変えて内部和を計算します。

例えば、計算したい場合、 nを「自由」なパラメータとして扱い、 $${\displaystyle s_{n}=\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\,,\quad m,n\in \mathbb {N} _{0}\,,}$$ $${\displaystyle F(z)=\sum _{n=0}^{\infty }{\left(\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\right)}z^{n}\,.}$$

合計を交換（「スネークオイル」）すると、 $${\displaystyle F(z)=\sum _{k=0}^{\infty }{{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-k}}\sum _{n=0}^{\infty }{{\binom {n+k}{m+2k}}z^{n+k}}\,.}$$

内部の合計は⁠z ^{m + 2 k}/(1 − z ) ^{m + 2 k + 1}⁠ . このように $${\displaystyle {\begin{aligned}F(z)&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-z}{(1-z)^{2}}}\right)^{k}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{C_{k}\left({\frac {-z}{(1-z)^{2}}}\right)^{k}}&{\text{where }}C_{k}=k{\text{th Catalan number}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}{\frac {1-{\sqrt {1+{\frac {4z}{(1-z)^{2}}}}}}{\frac {-2z}{(1-z)^{2}}}}\\[4px]&={\frac {-z^{m-1}}{2(1-z)^{m-1}}}\left(1-{\frac {1+z}{1-z}}\right)\\[4px]&={\frac {z^{m}}{(1-z)^{m}}}=z{\frac {z^{m-1}}{(1-z)^{m}}}\,.\end{aligned}}}$$

そして、 $${\displaystyle s_{n}={\begin{cases}\displaystyle {\binom {n-1}{m-1}}&{\text{for }}m\geq 1\,,\\{}[n=0]&{\text{for }}m=0\,.\end{cases}}}$$

同じ方法を再び合計に適用すると分かりやすいが、今回はnの代わりにmを自由パラメータとして用いる。つまり、 $${\displaystyle G(z)=\sum _{m=0}^{\infty }\left(\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}\right)z^{m}\,.}$$

合計を交換（「スネークオイル」）すると、 $${\displaystyle G(z)=\sum _{k=0}^{\infty }{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-2k}\sum _{m=0}^{\infty }{\binom {n+k}{m+2k}}z^{m+2k}\,.}$$

内部和は(1 + z ) ^{n + k}となる。したがって $${\displaystyle {\begin{aligned}G(z)&=(1+z)^{n}\sum _{k=0}^{\infty }{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-(1+z)}{z^{2}}}\right)^{k}\\[4px]&=(1+z)^{n}\sum _{k=0}^{\infty }C_{k}\,\left({\frac {-(1+z)}{z^{2}}}\right)^{k}&{\text{where }}C_{k}=k{\text{th Catalan number}}\\[4px]&=(1+z)^{n}\,{\frac {1-{\sqrt {1+{\frac {4(1+z)}{z^{2}}}}}}{\frac {-2(1+z)}{z^{2}}}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z{\sqrt {z^{2}+4+4z}}}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z(z+2)}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {-2z}{-2(1+z)}}=z(1+z)^{n-1}\,.\end{aligned}}}$$

したがって、 前と同じようにm ≥ 1が得られます。 $${\displaystyle s_{n}=\left[z^{m}\right]z(1+z)^{n-1}=\left[z^{m-1}\right](1+z)^{n-1}={\binom {n-1}{m-1}}\,,}$$

生成関数は合同性を証明する

2つの生成関数（べき級数）がm を法として合同であるとは、A ( z ) ≡ B ( z ) (mod m )と書き、それらの係数がn ≥ 0のすべてに対してm を法として合同である、すなわち、整数nのすべての関連するケースに対してa _n ≡ b _n (mod m )であることを意味します（ただし、ここではmが整数であると仮定する必要はありません。たとえば、不定なxにおいて多項式値​​になる可能性も十分にあります）。「より単純な」右辺生成関数B ( z )がzの有理関数である場合、この数列の形から、整数値m ≥ 2の特定のケースを法として、数列は最終的に周期的になることが示唆されます。たとえば、オイラー数 が3を法として次の合同性を満たすことを証明できます。^[25] $${\displaystyle \langle E_{n}\rangle =\langle 1,1,5,61,1385,\ldots \rangle \longmapsto \langle 1,1,2,1,2,1,2,\ldots \rangle {\pmod {3}}\,,}$$ $${\displaystyle \sum _{n=0}^{\infty }E_{n}z^{n}={\frac {1-z^{2}}{1+z^{2}}}{\pmod {3}}\,.}$$

任意の整数（すなわち、素数p ^kのべき乗に限らない）を法とする特殊生成関数によって列挙される数列の合同性を求める便利な方法の一つは、上記のJ分数による（収束しないものも含む）通常の生成関数の連分数表現に関する節に示されている。ランドーの『生成関数に関する講義』から、連分数による表現を通して展開された生成級数に関する具体的な結果を以下に引用する。

定理: 連分数の展開によって生成される級数の合同性—生成関数A ( z ) が形式の無限連分数で表され 、A _p ( z )がこの連分数展開のp次収束関数を表し、すべての0 ≤ n < 2 pに対してa _n = [ z ⁿ ] A _p ( z )が成り立つように定義されるとします。この場合、次のようになります。 $${\displaystyle A(z)={\cfrac {1}{1-c_{1}z-{\cfrac {p_{1}z^{2}}{1-c_{2}z-{\cfrac {p_{2}z^{2}}{1-c_{3}z-{\ddots }}}}}}}}$$

1. 関数A _p ( z )はすべてのp ≥ 2に対して有理数である。ここでp | p ₁ , p ₁ p ₂ , p ₁ p ₂ p ₃の割り切れる基準の1つが満たされると仮定する。つまり、あるk ≥ 1に対してp | p ₁ p ₂ ⋯ p _kが成り立つ。
2. 整数pが積p ₁ p ₂ ⋯ p _kを割り切る場合、 A ( z ) ≡ A _k ( z ) (mod p )が成り立ちます。

生成関数は、その係数の合同性を証明する際にも活用されます。次に、第一種スターリング数と分配関数p ( n )の特殊なケースの合同性を導出する2つの具体的な例を挙げます。これは、整数列を含む問題への対応において生成関数が汎用的であることを示しています。

小さな整数を法とするスターリング数

有限積によって生成されるスターリング数に関する主要記事 $${\displaystyle S_{n}(x):=\sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}=x(x+1)(x+2)\cdots (x+n-1)\,,\quad n\geq 1\,,}$$

ウィルフの参考文献Generatingfunctionologyの4.6節で述べられているように、これらの数の合同性は生成関数の性質から厳密に導かれる。基本的な議論を繰り返すと、2を法として約分するとき、これらの有限積生成関数はそれぞれ

$${\displaystyle S_{n}(x)=[x(x+1)]\cdot [x(x+1)]\cdots =x^{\left\lceil {\frac {n}{2}}\right\rceil }(x+1)^{\left\lfloor {\frac {n}{2}}\right\rfloor }\,,}$$

これは、これらのスターリング数の偶奇性が二項係数の偶奇性と一致する ことを意味する。

$${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}\equiv {\binom {\left\lfloor {\frac {n}{2}}\right\rfloor }{k-\left\lceil {\frac {n}{2}}\right\rceil }}{\pmod {2}}\,,}$$

そして、その結果、[ⁿ
_k]はk < ⌊ のときは常に偶数である⁠n/2⁠ ⌋。

同様に、スターリング数生成関数を定義する右辺の積を3を法として簡約し、より複雑な式を得ることができます。 $${\displaystyle {\begin{aligned}{\begin{bmatrix}n\\m\end{bmatrix}}&\equiv [x^{m}]\left(x^{\left\lceil {\frac {n}{3}}\right\rceil }(x+1)^{\left\lceil {\frac {n-1}{3}}\right\rceil }(x+2)^{\left\lfloor {\frac {n}{3}}\right\rfloor }\right)&&{\pmod {3}}\\&\equiv \sum _{k=0}^{m}{\begin{pmatrix}\left\lceil {\frac {n-1}{3}}\right\rceil \\k\end{pmatrix}}{\begin{pmatrix}\left\lfloor {\frac {n}{3}}\right\rfloor \\m-k-\left\lceil {\frac {n}{3}}\right\rceil \end{pmatrix}}\times 2^{\left\lceil {\frac {n}{3}}\right\rceil +\left\lfloor {\frac {n}{3}}\right\rfloor -(m-k)}&&{\pmod {3}}\,.\end{aligned}}}$$

分割関数の合同性

この例では、無限積の冪級数展開が多くの特殊関数の展開を生成するという仕組みの一部を取り入れ、分割関数を列挙する。特に、分割 関数 p ( n )は、次式で表される逆無限q-ポッホハンマー記号積（または場合によってはz-ポッホハンマー積）によって生成されることを思い出す。 $${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)z^{n}&={\frac {1}{\left(1-z\right)\left(1-z^{2}\right)\left(1-z^{3}\right)\cdots }}\\[4pt]&=1+z+2z^{2}+3z^{3}+5z^{4}+7z^{5}+11z^{6}+\cdots .\end{aligned}}}$$

この分割関数は多くの既知の合同性を満たしており、特に以下の結果が含まれるが、この関数の関連する整数合同性の形式についてはまだ多くの未解決の疑問が残っている。^[26] $${\displaystyle {\begin{aligned}p(5m+4)&\equiv 0{\pmod {5}}\\p(7m+5)&\equiv 0{\pmod {7}}\\p(11m+6)&\equiv 0{\pmod {11}}\\p(25m+24)&\equiv 0{\pmod {5^{2}}}\,.\end{aligned}}}$$

我々は、生成関数と合同式の操作を形式的な冪級数に対して使用して、上記に挙げた合同式の最初のものの非常に基本的な証明を与える方法を示します。

まず、二項係数生成関数において、 1、z ⁵、z ¹⁰、…のべき乗に対応する係数を除いて、すべての係数は5で割り切れることに気づく。さらに、それらの場合、係数の余りは5を法とした1となる。したがって、 あるいは等価的に、 $${\displaystyle {\frac {1}{(1-z)^{5}}}=\sum _{i=0}^{\infty }{\binom {4+i}{4}}z^{i}\,,}$$ $${\displaystyle {\frac {1}{(1-z)^{5}}}\equiv {\frac {1}{1-z^{5}}}{\pmod {5}}\,,}$$ $${\displaystyle {\frac {1-z^{5}}{(1-z)^{5}}}\equiv 1{\pmod {5}}\,.}$$ $${\displaystyle {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\left(1-z^{15}\right)\cdots }{\left((1-z)\left(1-z^{2}\right)\left(1-z^{3}\right)\cdots \right)^{5}}}\equiv 1{\pmod {5}}\,.}$$

その無限積展開を用いると、 z · ((1 − z )(1 − z ² )⋯) ⁴におけるz ^{5 m + 5}の係数は、すべてのmに対して 5 で割り切れることがわかります。^[27]最後に、 前の式のz ^{5 m + 5}の係数を等しくすることで、すべてのm ≥ 0に対してp (5 m + 4) ≡ 0 (mod 5) が成り立つという、望ましい合同の結果が証明されます。 $${\displaystyle z\cdot {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{\left(1-z\right)\left(1-z^{2}\right)\cdots }}=z\cdot \left((1-z)\left(1-z^{2}\right)\cdots \right)^{4}\times {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{\left(\left(1-z\right)\left(1-z^{2}\right)\cdots \right)^{5}}}\,,}$$ $${\displaystyle {\begin{aligned}\sum _{n=1}^{\infty }p(n-1)z^{n}&={\frac {z}{(1-z)\left(1-z^{2}\right)\cdots }}\\[6px]&=z\cdot {\frac {\left(1-z^{5}\right)\left(1-z^{10}\right)\cdots }{(1-z)\left(1-z^{2}\right)\cdots }}\times \left(1+z^{5}+z^{10}+\cdots \right)\left(1+z^{10}+z^{20}+\cdots \right)\cdots \end{aligned}}}$$

生成関数の変換

生成関数には、他の応用を可能にする変換が数多く存在します（メイン記事を参照）。列の通常生成関数（OGF）の変換は、ある列の生成関数を別の列を列挙する生成関数に変換する方法を提供します。これらの変換には、通常、列OGFを含む積分式（積分変換を参照）や、これらの関数の高階導関数の加重和（微分変換を参照）が含まれます。

生成関数変換は、和の生成関数を表現しようとするときに役立ちます。 $${\displaystyle s_{n}:=\sum _{m=0}^{n}{\binom {n}{m}}C_{n,m}a_{m},}$$

S ( z ) = g ( z ) A ( f ( z ))の形で、元となる数列生成関数を含む。例えば、和が の場合、修正された和式の生成関数は^{[28]で与えられる（}二項変換とスターリング変換も参照）。 $${\displaystyle s_{n}:=\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}a_{k}\,}$$ $${\displaystyle S(z)={\frac {z^{m}}{(1-z)^{m+1}}}A\left({\frac {z}{(1-z)^{2}}}\right)}$$

シーケンスのOGF、 F（z）とその指数生成関数、またはEGF、F̂（z）との間の変換を行う積分式もあり、その逆も同様です。 $${\displaystyle {\begin{aligned}F(z)&=\int _{0}^{\infty }{\hat {F}}(tz)e^{-t}\,dt\,,\\[4px]{\hat {F}}(z)&={\frac {1}{2\pi }}\int _{-\pi }^{\pi }F\left(ze^{-i\vartheta }\right)e^{e^{i\vartheta }}\,d\vartheta \,,\end{aligned}}}$$

ただし、これらの積分は適切なzの値に対して収束するものとする。

特殊生成関数の表

特殊な数学的級数の最初のリストはここにあります。いくつかの有用かつ特殊な数列生成関数は、『具体数学』の5.4節と7.4節、およびウィルフの『生成関数論』の2.5節に記載されています。その他の注目すべき特殊な生成関数には、次の表の項目が含まれますが、これは決して完全なものではありません。^[29]

形式冪級数	生成関数の式	注記
${\displaystyle \sum _{n=0}^{\infty }{\binom {m+n}{n}}\left(H_{n+m}-H_{m}\right)z^{n}}$	${\displaystyle {\frac {1}{(1-z)^{m+1}}}\ln {\frac {1}{1-z}}}$	${\displaystyle H_{n}}$は一次調和数である
${\displaystyle \sum _{n=0}^{\infty }B_{n}{\frac {z^{n}}{n!}}}$	${\displaystyle {\frac {z}{e^{z}-1}}}$	${\displaystyle B_{n}}$ベルヌーイ数である
${\displaystyle \sum _{n=0}^{\infty }F_{mn}z^{n}}$	${\displaystyle {\frac {F_{m}z}{1-(F_{m-1}+F_{m+1})z+(-1)^{m}z^{2}}}}$	${\displaystyle F_{n}}$フィボナッチ数であり ${\displaystyle m\in \mathbb {Z} ^{+}}$
${\displaystyle \sum _{n=0}^{\infty }\left\{{\begin{matrix}n\\m\end{matrix}}\right\}z^{n}}$	${\displaystyle (z^{-1})^{\overline {-m}}={\frac {z^{m}}{(1-z)(1-2z)\cdots (1-mz)}}}$	${\displaystyle x^{\overline {n}}}$上昇階乗、またはポッホハマー記号と整数 ${\displaystyle m\geq 0}$
${\displaystyle \sum _{n=0}^{\infty }\left[{\begin{matrix}n\\m\end{matrix}}\right]z^{n}}$	${\displaystyle z^{\overline {m}}=z(z+1)\cdots (z+m-1)}$
${\displaystyle \sum _{n=1}^{\infty }{\frac {(-1)^{n-1}4^{n}(4^{n}-2)B_{2n}z^{2n}}{(2n)\cdot (2n)!}}}$	${\displaystyle \ln {\frac {\tan(z)}{z}}}$
${\displaystyle \sum _{n=0}^{\infty }{\frac {(1/2)^{\overline {n}}z^{2n}}{(2n+1)\cdot n!}}}$	${\displaystyle z^{-1}\arcsin(z)}$
${\displaystyle \sum _{n=0}^{\infty }H_{n}^{(s)}z^{n}}$	${\displaystyle {\frac {\operatorname {Li} _{s}(z)}{1-z}}}$	${\displaystyle \operatorname {Li} _{s}(z)}$は多重対数関数であり、一般化された調和数である。 ${\displaystyle H_{n}^{(s)}}$ ${\displaystyle \Re (s)>1}$
${\displaystyle \sum _{n=0}^{\infty }n^{m}z^{n}}$	${\displaystyle \sum _{0\leq j\leq m}\left\{{\begin{matrix}m\\j\end{matrix}}\right\}{\frac {j!\cdot z^{j}}{(1-z)^{j+1}}}}$	${\displaystyle \left\{{\begin{matrix}n\\m\end{matrix}}\right\}}$は第二種スターリング数であり、展開の各項は ${\displaystyle {\frac {z^{i}}{(1-z)^{i+1}}}=\sum _{k=0}^{i}{\binom {i}{k}}{\frac {(-1)^{k-i}}{(1-z)^{k+1}}}}$
${\displaystyle \sum _{k<n}{\binom {n-k}{k}}{\frac {n}{n-k}}z^{k}}$	${\displaystyle \left({\frac {1+{\sqrt {1+4z}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {1+4z}}}{2}}\right)^{n}}$
${\displaystyle \sum _{n_{1},\ldots ,n_{m}\geq 0}\min(n_{1},\ldots ,n_{m})z_{1}^{n_{1}}\cdots z_{m}^{n_{m}}}$	${\displaystyle {\frac {z_{1}\cdots z_{m}}{(1-z_{1})\cdots (1-z_{m})(1-z_{1}\cdots z_{m})}}}$	2変数の場合は次のように表される。 ${\displaystyle M(w,z):=\sum _{m,n\geq 0}\min(m,n)w^{m}z^{n}={\frac {wz}{(1-w)(1-z)(1-wz)}}}$
${\displaystyle \sum _{n=0}^{\infty }{\binom {s}{n}}z^{n}}$	${\displaystyle (1+z)^{s}}$	${\displaystyle s\in \mathbb {C} }$
${\displaystyle \sum _{n=0}^{\infty }{\binom {n}{k}}z^{n}}$	${\displaystyle {\frac {z^{k}}{(1-z)^{k+1}}}}$	${\displaystyle k\in \mathbb {N} }$
${\displaystyle \sum _{n=1}^{\infty }\log {(n)}z^{n}}$	${\displaystyle \left.-{\frac {\partial }{\partial s}}\operatorname {{Li}_{s}(z)} \right|_{s=0}}$

参照

• モーメント生成関数
• 確率生成関数
• 生成関数変換
• スタンレーの相互性定理
• 整数分割
• 組み合わせ原理
• 循環ふるい分け
• Z変換
• アンブラル計算
• 噴水のコイン

注記

1. m < 0の場合の対応する式も次のように表される。 $${\displaystyle \sum _{n=0}^{\infty }g_{n+m}z^{n}={\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}\,.}$$

参考文献

1. この代替用語は、EN Gilbert (1956)「Enumeration of Labeled graphs」、Canadian Journal of Mathematics 3、p. 405–411 にすでに見られますが、2000 年以前にはまれでしたが、それ以降は増加しているようです。
2. Knuth, Donald E. (1997). 「§1.2.9 生成関数」. 『基礎アルゴリズム』 . 『コンピュータプログラミングの技法』 . 第1巻（第3版）. Addison-Wesley. ISBN 0-201-89683-4。
3. フラジョレット＆セジウィック 2009、95ページ
4. 「ランバート級数の恒等式」Math Overflow . 2017年。
5. アポストル、トム・M.（1976）、解析的数論入門、数学の学部テキスト、ニューヨーク-ハイデルベルク：シュプリンガー・フェアラーク、ISBN 978-0-387-90163-3、MR  0434929、Zbl  0335.1000142～43ページ
6. ウィルフ 1994、56ページ
7. ウィルフ 1994、59ページ
8. ハーディ, GH; ライト, EM; ヒース＝ブラウン, DR; シルバーマン, JH (2008). 『数論入門』（第6版）. オックスフォード大学出版局. p. 339. ISBN 9780199219858。
9. Knuth, DE (1992). 「畳み込み多項式」. Mathematica J. 2 : 67–78 . arXiv : math /9207221 . Bibcode :1992math......7221K.
10. Spivey, Michael Z. (2007). 「組み合わせ和と有限差分」.離散数学. 307 (24): 3130– 3146. doi : 10.1016/j.disc.2007.03.052 . MR  2370116.
11. Mathar, RJ (2012). 「もう一つの積分表」. arXiv : 1207.5845 [math.CA].v4 等式 (0.4)
12. Graham、Knuth、Patashnik 1994、§6.1の表265、スターリング数三角形を含む有限和恒等式。
13. ランド 2003、§2.4
14. リチャード・P・スタンリー、セルゲイ・フォミン (1997)「§6.3」による例。列挙的組合せ論：第2巻。ケンブリッジ高等数学研究第62巻。ケンブリッジ大学出版局。ISBN 978-0-521-78987-5。
15. クヌース 1997, §1.2.9
16. Graham, Knuth & Patashnik 1994, p. 569、演習7.36の解答
17. フラジョレット＆セジウィック 2009、§B.4
18. Schneider, C. (2007). 「記号的総和は組合せ論を支援する」. Sém. Lothar. Combin . 56 : 1–36 .
19. これらの用語の使用法については、Graham、Knuth、Patashnik 1994、§7.4 の特殊シーケンス生成関数に関する項を参照してください。
20. Good, IJ (1986). 「対称ディリクレ分布とその混合分布の分割表への応用について」Annals of Statistics . 4 (6): 1159–1189 . doi : 10.1214/aos/1176343649 .
21. J分数の特性に関するより詳しい情報については以下を参照してください。
    • Flajolet, P. (1980). 「連分数の組合せ論的側面」(PDF) .離散数学. 32 (2): 125– 161. doi :10.1016/0012-365X(80)90050-3.
    • ウォール、HS（2018）[1948]. 連分数の解析理論. ドーバー. ISBN 978-0-486-83044-5。
22. 以下の記事を参照してください。
    • Schmidt, Maxie D. (2016). 「平方級数生成関数の連分数」arXiv : 1612.02778 [math.NT].
    • — (2017). 「一般化階乗関数の常数生成関数に対するヤコビ型連分数」. Journal of Integer Sequences . 20 . arXiv : 1610.09691 . 17.3.4.
    • — (2017). 「 h ≥ 2を法とする二項係数のヤコビ型連分数と合同式」. arXiv : 1702.01374 [math.CO].
23. グレアム、クヌース、パタシュニク、1994 年、§8.3
24. Graham, Knuth & Patashnik 1994, §7.3の例6に、別の手法と生成関数を用いたこの問題の完全な設定が記載されています。このより「複雑な」アプローチは、同文献のセクション7.5に記載されています。
25. ランド 2003、§5
26. ハーディ他 2008, §19.12
27. ハーディ、GH; ライト、EM 『数論入門』。288ページ、361ページ
28. グラハム、クヌース、パタシュニク 1994、p. 535、演習5.71
29. Plouffe, Simon (1992)にある1031 の生成関数も参照してください。近似関数といくつかの推測[母関数の近似といくつかの推測] (修士) (フランス語)。ケベック大学モントリオール。arXiv : 0911.4975。

引用

• アイグナー、マーティン（2007年）『列挙論講座』数学大学院テキスト第238巻、シュプリンガー、ISBN 978-3-540-39035-0。
• デュビレ, ピーター;ロータ, ジャン＝カルロ;スタンレー, リチャード(1972). 「組合せ理論の基礎について VI. 母関数の考え方」第6回バークレー数理統計・確率シンポジウム議事録. 2 : 267–318 . Zbl  0267.05002.Rota, Gian-Carlo ( 1975). 「3. 生成関数の考え方」『有限作用素計算』に再録。P. Doubilet、C. Greene、D. Kahaner、 A. Odlyzko、R. Stanleyとの共著。Academic Press。83–134 ページ。ISBN 0-12-596650-4. Zbl  0328.05007。
• フラジョレ, フィリップ;セジウィック, ロバート(2009).解析的組合せ論. ケンブリッジ大学出版局. ISBN 978-0-521-89806-5. Zbl  1165.05001。
• グールデン、イアン・P.;ジャクソン、デイビッド・M. (2004).組み合わせ列挙法.ドーバー出版. ISBN 978-0486435978。
• グラハム、ロナルド・L. ;クヌース、ドナルド・E. ;パタシュニク、オーレン(1994). 「第7章 生成関数」.具体数学 コンピュータサイエンスの基礎(第2版). アディソン・ウェスレー. pp.  320– 380. ISBN 0-201-55802-5. Zbl  0836.00001.
• ランドー、セルゲイ・K. (2003). 『生成関数に関する講義』アメリカ数学会. ISBN 978-0-8218-3481-7。
• ウィルフ、ハーバート・S. (1994). ジェネレーティングファンクションロジー（第2版）. アカデミック・プレス. ISBN 0-12-751956-4. Zbl  0831.05001。

外部リンク

• ヨーク大学数学・統計学科マイク・ザブロッキによる「通常の生成関数入門」
• 「生成関数」、数学百科事典、EMSプレス、2001 [1994]
• 生成関数、べき乗指数、そして結び目の切り取りにおけるコインの変化
• 「Generating Functions」、Ed Pegg Jr.著、Wolfram Demonstrations Project、2007 年。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Generating_function&oldid=1318448174"