列挙的組合せ論

4638576個中3個^{[ 1 ]}または580717個中^{[ 2 ]}、回転と反射を別個に数えない場合、正方格子グラフ8х8上のハミルトン閉路

列挙的組合せ論は、特定のパターンが形成できる方法の数を扱う組合せ論の一分野です。この種の問題の例としては、組み合わせの数え上げと順列の数え上げが挙げられます。より一般的には、自然数でインデックス付けされた有限集合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!}}}$

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

連合

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

組み合わせ構造

上記の操作は、木（二元および平面）、ディック路、閉路などの一般的な組み合わせオブジェクトを列挙するために使用できます。組み合わせ構造は原子で構成されています。例えば、木の場合、原子はノードになります。オブジェクトを構成する原子は、ラベル付きまたはラベルなしのいずれかになります。ラベルなしの原子は互いに区別できませんが、ラベル付き原子は互いに区別できます。したがって、ラベル付き原子で構成される組み合わせオブジェクトの場合、2つ以上の原子を交換するだけで新しいオブジェクトを形成できます。

二分木と平面木

二分木と平面木は、ラベルなしの組み合わせ構造の例です。木は、循環がないように辺で結ばれたノードで構成されます。一般的に、ルートと呼ばれるノードがあり、ルートには親ノードがありません。平面木では、各ノードは任意の数の子を持つことができます。平面木の特殊なケースである二分木では、各ノードは2つの子を持つか、または0つの子を持つことができます。すべての平面木の族を とします。この族は次のように再帰的に定義できます。 ${\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}}}$

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

${\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)^番目のカタラン数に等しい。したがって、p _n = c _{n −1 と}なる。

参照

• 代数的組合せ論
• 漸近的組合せ論
• バーンサイドの補題
• 組み合わせ爆発
• 組み合わせゲーム理論
• 組み合わせ原理
• 組み合わせ種
• 包含・排除原則
• 区別要素の方法
• ポリア列挙定理
• ふるい理論

参考文献

1. ( OEISの配列A003763 )
2. ( OEISの配列A209077 )

• ツァイルバーガー、ドロン、『列挙的および代数的組合せ論』
• ビョルナー、アンダース、スタンレー、リチャード 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。
• ローア、ニコラス・A. (2011). 全単射的組合せ論. CRC Press . ISBN 143984884X、 ISBN 978-1439848845。
• スタンリー、リチャード・P. (1997, 1999). 列挙的組合せ論第1巻および第2巻.ケンブリッジ大学出版局. ISBN 0-521-55309-1、ISBN 0-521-56069-1。
• グールデン、イアン・P.、ジャクソン、デイビッド・M. (2004). 組み合わせ列挙法.ドーバー出版. ISBN 0486435970。
• ジョン・リオーダン（1958年）『組合せ解析入門』Wiley & Sons, New York（再版）
• ジョン・リオーダン（1968年）『組み合わせ恒等式』Wiley & Sons, New York（再出版）。
• ウィルフ、ハーバート・S. (1994).ジェネレーティングファンクションロジー（第2版）. ボストン、マサチューセッツ州: アカデミック・プレス. ISBN 0-12-751956-4. Zbl  0831.05001 .