各種分割の数え上げ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/23 09:56 UTC 版)
n個の元を持つ集合の分割の総数はベル数 Bn である。n の小さいベル数を列挙すると、B0 = 1、B1 = 1、B2 = 2、B3 = 5、B4 = 15、B5 = 52、B6 = 203 となっている。ベル数は次の漸化式で表される。 B n + 1 = ∑ k = 0 n ( n k ) B k {\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}} そして、次のような指数型母関数が存在する。 ∑ n = 0 ∞ B n n ! z n = e e z − 1 {\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}} n個の元を持つ集合をk個のブロックに分ける分割の総数は、第2種スターリング数 S(n, k) である。 n個の元を持つ集合の非交差な分割の総数はカタラン数 Cn であり、次の式で表される。 C n = 1 n + 1 ( 2 n n ) {\displaystyle C_{n}={1 \over n+1}{2n \choose n}}
※この「各種分割の数え上げ」の解説は、「集合の分割」の解説の一部です。
「各種分割の数え上げ」を含む「集合の分割」の記事については、「集合の分割」の概要を参照ください。
ウィキペディア小見出し辞書の「各種分割の数え上げ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 各種分割の数え上げのページへのリンク
