組合せ関数

Documentation MathematicaMathematicaブック Mathematicaを使った高等数学関数

3.2.5 組合せ関数

順列組合せの関数

階乗関数 n!は，個のものの並べ方の総数を与える．が整数でないとき，の数値は 3.2.10で説明するガンマ関数から求められる．

2項係数の関数 Binomial[n, m]は，と書ける．この関数は，並び順を考慮しないとき，個のものの中から個のものの取出し方の個数を与える．また，各種の木の枚挙問題に現れるカタラン(Catalan)数は，2項係数により，の関係式で与えられる．

多項係数 Multinomial[, , ... ]は，と書け，個の異なるものを個の組に分け，各組に含まれる要素の個数がとなるような分け方の総数を表す．

Mathematicaは，整数の階乗に対しては厳密な整数で結果を返す．

In[1]:= 30!

Out[1]=

非整数の階乗は，ガンマ関数で評価される．

In[2]:= 3.6!

Out[2]=

Mathematicaは，2項係数によっては，シンボル的な結果を返すこともできる．

In[3]:= Binomial[n, 2]

Out[3]=

個のものを6個と5個のものからなる組に分けるとき，分け方が何通りあるかを調べる．

In[4]:= Multinomial[6, 5]

Out[4]=

この結果は，と同じである．

In[5]:= Binomial[11, 6]

Out[5]=

フィボナッチの数 Fibonacci[n]は，および漸化式を満たす．この数は離散数学で広く使われる．を増加させると，は黄金比に近付く．

フィボナッチの多項式 Fibonacci[n, x]は，式の展開で得られる項の係数に当たる．

調和数HarmonicNumber[n]はで与えられる．次の調和数HarmonicNumber[n, r]はで与えられる．調和数は多くの組合せ論の推定問題で現れ，しばしば離散化された対数に相当する役割を演じる．

ベルヌーイの多項式 BernoulliB[n, x]は，母関数の関係式を満たす．また，ベルヌーイの多項式 BernoulliB[n]は，で与えられる．は，近似積分で使われるオイラー・マクローリン(Euler-Maclaurin)の和の式における項の係数にあたる．

ベルヌーイ数の近似値はさまざまな数値計算アルゴリズムで使われる．ベルヌーイ数の数値は，まず BernoulliB[n]を使い厳密な有理値として求めておき，それに Nを適用することで求められる．

オイラーの多項式 EulerE[n, x]は，母関数の関係式を満たす．また，オイラー数 EulerE[n]は，で与えられる．オイラー数は，の関係式によりジェノッチ(Genocchi)数に関連している．

ベルヌーイの多項式の第2項を求める．

In[6]:= BernoulliB[2, x]

Out[6]=

また，実際に母関数に対してベキ級数を計算してもベルヌーイの項は求めることができる．

In[7]:= Series[t Exp[x t]/(Exp[t] - 1), {t, 0, 4}]

Out[7]=

BernoulliB[n]は，ベルヌーイ数を厳密な有理数として返す．

In[8]:= BernoulliB[20]

Out[8]=

スターリング数は組合せ理論の枚挙問題によく現れる．第1種のスターリング数 StirlingS1[n, m]に対して，は，ちょうど回循環する要素の順列の個数を返す．スターリング数は，母関数の関係式を満たす．注意点として，の定義によっては，の係数が付くため Mathematicaの定義と異なる場合がある．

第2種のスターリング数 StirlingS2[n, m]は，個の要素を空でない組の部分集合に分ける上で何通りの分け方があるかを返す．第2種のスターリング数は，の関係式を満たす．

分割関数 PartitionsP[n]は，整数 nを正整数の和として順不同で組み合すとき，組合せ方が何通りあるかを返す． PartitionsQ[n]は，和を構成する整数成分が相異するとき，整数 nの組合せ方が何通りあるかを返す．

第1種のスターリング数の表を作る．

In[9]:= Table[StirlingS1[5, i], {i, 5}]

Out[9]=

積の展開項の係数がスターリング数にあたる．

In[10]:= Expand[Product[x - i, {i, 0, 4}]]

Out[10]=

100を何通りに分割できるかを調べる．最初は，項が相異なるとし，次は，制約を外した場合である．

In[11]:= {PartitionsQ[100], PartitionsP[100]}

Out[11]=

分割関数はに似た形で増加する．注意点として， PartitionsPのような整数だけを引数とする関数は， Plotでは直接プロットすることができない．

In[12]:= ListPlot[ Table[
N[Log[ PartitionsP[n] ]], {n, 100} ] ]

Out[12]=

本節で説明してきた関数は，各種の組合せの数を計算するのに使われる．これらとは違って， Permutationsのような関数は，要素の組合せそのもののリストを生成するために使われる．

符号関数 Signature[, , ... ]は順列の符号を返す．偶順列ならを返し，奇順列ならを返す．偶順列（もしくは，奇順列）とは順列が偶数回（奇数回）の互換（2つの要素の入れ替え）で得られることを指す．符号関数は，交代テンソルであるレビー・チビタ(Levi-Civita)の記号，または，イプシロン記号としてとらえることができる．