列挙的組合せ論

列挙的組合せ論は、特定のパターンを形成する方法の数を扱う組合せ論の分野です。この種の問題の 2 つの例は、組み合わせの数え上げと順列の数え上げです。より一般的には、自然数でインデックス付けされた有限集合S _iの無限のコレクションが与えられた場合、列挙的組合せ論は、各nについてS _n内のオブジェクトの数を数える計数関数を記述しようとします。集合内の要素の数を数えることはかなり広範な数学的問題ですが、応用で生じる問題の多くは、比較的単純な組合せ論的記述が可能です。12通りの方法は、順列、組み合わせ、および分割を数えるための統一されたフレームワークを提供します。

最も単純な関数は閉じた式で、階乗、累乗などの基本関数の組み合わせとして表現できます。たとえば、以下に示すように、n 枚のカードの異なる順序の可能な数はf ( n ) = nです。閉じた式を見つける問題は代数的列挙として知られており、多くの場合、再帰関係または生成関数を導出し、これを使用して目的の閉じた形式に到達することが関係します。

多くの場合、複雑な閉式では、カウントするオブジェクトの数が増えたときのカウント関数の挙動についてほとんど洞察が得られません。このような場合、単純な漸近近似が望ましい場合があります。関数は、 の場合に の漸近近似です。この場合、次のように書きます。${\displaystyle g(n)}$${\displaystyle f(n)}$${\displaystyle f(n)/g(n)\rightarrow 1}$${\displaystyle n\rightarrow \infty}$${\displaystyle f(n)\sim g(n).\,}$

生成関数は、組み合わせオブジェクトの族を記述するために使用されます。オブジェクトの族を表し、F ( x ) をその生成関数とします。 ${\displaystyle {\mathcal {F}}}$

${\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}}$

ここで はサイズnの組合せオブジェクトの数を表します。したがって、サイズnの組合せオブジェクトの数はの係数で与えられます。ここで、組合せオブジェクトの族に対する一般的な操作と、それが生成関数に与える影響について説明します。指数生成関数が使用される場合もあります。この場合、次の形式になります。 ${\displaystyle f_{n}}$${\displaystyle x^{n}}$

${\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}{\frac {x^{n}}{n!}}}$

生成関数が決定されると、これまでのアプローチで与えられた情報が得られます。さらに、加算、乗算、微分などの生成関数に対するさまざまな自然な演算には組み合わせ的な意味があり、これにより、1 つの組み合わせ問題の結果を拡張して他の問題を解決できます。

2つの組合せ族と、それぞれ生成関数F ( x )とG ( x )を持つ場合、 2つの族の非結合和集合( )は生成関数F ( x )+ G ( x )を持つ。 ${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {G}}}$${\displaystyle {\mathcal {F}}\cup {\mathcal {G}}}$

上記のような2つの組合せ族に対して、2つの族( )の直積(ペア)の生成関数はF ( x ) G ( x )となる。 ${\displaystyle {\mathcal {F}}\times {\mathcal {G}}}$

（有限）シーケンスは、上で定義したペアの考え方を一般化したものです。シーケンスは、組み合わせオブジェクトとそれ自身の任意の直積です。正式には、

${\displaystyle {\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \cdots }$

上記を言葉で表現すると、空のシーケンス、1 つの要素のシーケンス、2 つの要素のシーケンス、3 つの要素のシーケンスなどです。生成関数は次のようになります。

${\displaystyle 1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}.}$

上記の操作は、ツリー(バイナリとプレーン)、Dyck パス、サイクルなどの一般的な組み合わせオブジェクトを列挙するために使用できるようになりました。組み合わせ構造は原子で構成されています。たとえば、ツリーの場合、原子はノードになります。オブジェクトを構成する原子は、ラベル付きまたはラベルなしのいずれかです。ラベルなしの原子は互いに区別できませんが、ラベル付きの原子は区別できます。したがって、ラベル付き原子で構成される組み合わせオブジェクトの場合、2 つ以上の原子を交換するだけで新しいオブジェクトを形成できます。

二分木と平面木は、ラベルなしの組み合わせ構造の例です。木は、循環がないようにエッジでリンクされたノードで構成されます。通常、ルートと呼ばれるノードがあり、これには親ノードがありません。平面木では、各ノードは任意の数の子を持つことができます。平面木の特殊なケースである二分木では、各ノードは 2 つの子を持つか、子を持たないかのいずれかです。すべての平面木のファミリーを で表します。このファミリーは、次のように再帰的に定義できます。 ${\displaystyle {\mathcal {P}}}$

${\displaystyle {\mathcal {P}}=\{\bullet \}\times \,{\mbox{Seq}}({\mathcal {P}})}$

この場合は、1 つのノードで構成されるオブジェクトのファミリを表します。これは生成関数xを持ちます。P ( x ) は生成関数を表します。上記の説明を言葉で表すと、平面木は、任意の数のサブツリーが接続されたノードで構成され、各サブツリーも平面木です。前に開発した組み合わせ構造のファミリに対する操作を使用すると、これは再帰生成関数に変換されます。 ${\displaystyle \{\bullet \}}$${\displaystyle {\mathcal {P}}}$

${\displaystyle P(x)=x\,{\frac {1}{1-P(x)}}}$

P ( x )を解いた後:

${\displaystyle P(x)={\frac {1-{\sqrt {1-4x}}}{2}}}$

サイズnのプラタナスの木の数の明示的な式は、x ⁿの係数を抽出することによって決定できます。

${\displaystyle {\begin{aligned}p_{n}&=[x^{n}]P(x)=[x^{n}]{\frac {1-{\sqrt {1-4x}}}{2}}\\[6pt]&=[x^{n}]{\frac {1}{2}}-[x^{n}]{\frac {1}{2}}{\sqrt {1-4x}}\\[6pt]&=-{\frac {1}{2}}[x^{n}]\sum _{k=0}^{\infty }{{\frac {1}{2}} \choose k}(-4x)^{k}\\[6pt]&=-{\frac {1}{2}}{{\frac {1}{2}} \choose n}(-4)^{n}\\[6pt]&={\frac {1}{n}}{2n-2 \choose n-1}\end{aligned}}}$

注: 表記法 [ x ⁿ ] f ( x ) は、 f ( x )におけるx ⁿの係数を表します。平方根の級数展開は、ニュートンの二項定理の一般化に基づいています。4 行目から 5 行目を取得するには、一般化された二項係数を使用した操作が必要です。

最後の行の式は( n  −1)番目^の カタラン数に等しい。したがって、pn = cn _{− 1である}。

• ツァイルバーガー、ドロン、列挙的および代数的組合せ論
• ビョルナー、アンダース、スタンレー、リチャード P.、組み合わせ雑集
• Graham、Ronald L.、 Grötschel M.、およびLovász、László編。 （1996年）。Handbook of Combinatorics、第 1 巻および第 2 巻。Elsevier (北オランダ)、アムステルダム、および MIT Press、ケンブリッジ、マサチューセッツ州、ISBN  0-262-07169-X。
• ジョセフ、ジョージ・ゲヴェルゲーゼ (1994) [1991]。『孔雀の紋章：非ヨーロッパの数学のルーツ（第2版）』ロンドン：ペンギンブックス。ISBN 0-14-012529-9。
• Loehr, Nicholas A. (2011). 全単射組合せ論. CRC Press. ISBN 143984884X , ISBN 978-1439848845 .  
• スタンレー、リチャード P. (1997、1999)。列挙的組合せ論、第 1 巻および第 2 巻。ケンブリッジ大学出版局。ISBN 0-521-55309-1、ISBN 0-521-56069-1。  
• Goulden, Ian P.およびJackson , David M. ( 2004)。組み合わせ列挙。Dover Publications。ISBN 0486435970。  
• リオーダン、ジョン(1958)。『組合せ分析入門』、Wiley & Sons、ニューヨーク (再出版)。
• リオーダン、ジョン（1968年）。『組み合わせ的恒等式』、ワイリー・アンド・サンズ、ニューヨーク（再出版）。
• ウィルフ、ハーバート S. (1994)。Generatingfunctionology (第 2 版)。ボストン、マサチューセッツ州: Academic Press。ISBN 0-12-751956-4.ZBL0831.05001  。​