数え上げ組合せ論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/20 09:41 UTC 版)
組合せ論の始まりは特定のパターンが形成される場合の数を計算することだった。S を n 個の元からなる集合とすると、S から k 個のものを選ぶ組合せは S の部分集合で k 個の元を持つもの（要素が並ぶ順番は区別されない）に対応する。S から k 個のものを選んで並べることは k 個の相異なる S の元による順列（長さが違ったり、元が同じでも順番が違う順列は区別される）に対応する。組合せや順列の数の公式は簡単に見て取れるが組合せ論のいたるところで重要な役割を果たしている。 より一般的に、数え上げ組合せ論では、(通常、自然数全体の集合を添字集合とする) 有限集合の無限族 {Si} が与えられたとき、任意のnに対してSnの要素の数を数える数え上げ関数 f(n)を記述する様々な方法を探究している。集合の要素数を数えるという行為はかなり大きな数学的問題であるが、組合せ的な問題では集合S(n)は割と単純な組合せ的記述を持ち、付加的な構造が少ししかないことが普通である。 そのような関数で最も簡単なものは閉じた公式であり、階乗、べき乗のような単純な関数の合成で表現できるものである。例えば、上でも述べたように、n枚のトランプの異なる並べ方の数はf(n) = n!である。 このアプローチが常に満足いくもの (すなわち実用的なもの) であるとは限らない。例えば、f(n)を区間[1,n]における異なる整数から成る部分集合で連続する2つの整数を含まないものの数であるとする。例えば、n = 4の場合、{}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}という集合が得られるので、f(4) = 8である。実際、f(n)がn+2番目のフィボナッチ数F(n+2)であることが分かるので、 f ( n ) = ϕ n + 2 − ( 1 − ϕ ) n + 2 5 {\displaystyle f(n)={\frac {\phi ^{n+2}-(1-\phi )^{n+2}}{\sqrt {5}}}} という閉じた公式で表現できる。ここで、 ϕ = ( 1 + 5 ) / 2 {\displaystyle \phi =(1+{\sqrt {5}})/2} は黄金比である。しかしながら、ここでは数え上げ関数を見ているので、結果に 5 {\displaystyle {\sqrt {5}}} が現れていることは美的に好ましくないと考えられる。f(n)が正整数であることを確認する他の方法として、f(n)が f ( n ) = f ( n − 1 ) + f ( n − 2 ) {\displaystyle f(n)=f(n-1)+f(n-2)\,\!} という再帰関係で表現できることを考えることもできる。ただし、初期条件はf(1) = 1とf(2) = 1である。 他のアプローチには、漸近公式 f ( n ) ∼ g ( n ) {\displaystyle f(n)\sim g(n)\,} を見つけるというものがある。ここで、g(n)は「よく知られた」関数であり、nが無限に近づくときにf(n)がg(n)に近づくものとする。いくつかの場合では、漸近関数として複雑すぎる閉じた公式を使っても数える対象の振舞に関して何も感覚を得られないので、単純な漸近関数が好まれる。上の例では、nが大きいとき、 f ( n ) ∼ ϕ n + 2 5 {\displaystyle f(n)\sim {\frac {\phi ^{n+2}}{\sqrt {5}}}} となる漸近公式が導かれる。 最後に、f(n)を母関数と呼ばれる形式級数で表現することもできる。母関数は大抵の場合、通常母関数 ∑ n ≥ 0 f ( n ) x n {\displaystyle \sum _{n\geq 0}f(n)x^{n}} であるか、あるいは指数型母関数 ∑ n ≥ 0 f ( n ) x n n ! {\displaystyle \sum _{n\geq 0}f(n){\frac {x^{n}}{n!}}} である。母関数が一旦定まると、そこから今までに説明したアプローチで得られる全ての情報を抽出することができる。それに加えて、加算、乗算、微分などの自然な演算を母関数に施すことができることも組合せ的に意味深い。それによって、１つの組合せ的問題に対する結果を他の問題を解くために拡張することができるようになる。
※この「数え上げ組合せ論」の解説は、「組合せ数学」の解説の一部です。
「数え上げ組合せ論」を含む「組合せ数学」の記事については、「組合せ数学」の概要を参照ください。
- 数え上げ組合せ論のページへのリンク
