「写像12相」で典型的な数え上げ問題のパターン総整理

条件を満たすものが何通りあるか数える問題、すなわち数え上げ問題には様々なものがありますが、「\(n\) 個の玉を \(x\) 個の箱に分ける方法は何通りか」などといった、典型的なものはある程度パターン化して解くことができます。 この記事では、ある集合からある集合へのマッピングが何通り存在するのかを考えるときに便利な「写像12相（the twelvefold way）」について紹介し、これを通じて典

自然数nをk個の0以上の整数に分割する方法の総数を求めるアルゴリズム

以下の2つを混同しそうですが、ここでは \(p_{\leq k}(n)\) を求めることを考えます。 \(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) 個の要素を区別できない \(k\) 個ちょうどのブロックに分割する方法の数\(p_{\leq k}(n)\) : よく \(P(n,k)\) とも書く。自然

自然数nをk個の1以上の整数に分割する方法の総数を求めるアルゴリズム

以下の2つを混同しそうですが、ここでは \(p_k(n)\) を求めることを考えます。 \(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) 個の要素を区別できない \(k\) 個ちょうどのブロックに分割する方法の数\(p_{\leq k}(n)\) : よく \(P(n,k)\) とも書く。自然数 \(n\)

ベル数を求めるアルゴリズム：第2種スターリング数の和を効率的に計算する

ベル数とは ベル数とは「区別できる \(n\) 個の要素を区別できない \(k\) 個以下のブロックに分割する方法の数」のことです。 これは、第2種スターリング数を用いて表すことが可能です。 第2種スターリング数とは、区別できる \(n\) 個の要素を区別できない \(k\) 個のブロックに分割する方法の数のことで、\(S(n,k)\) などと表すことが多いです。 ベル数は、第2種スターリング数の

第2種スターリング数を求めるアルゴリズム

第2種スターリング数とは 第2種スターリング数 \(S(n,k)\) は、以下の3つの性質を持つ数です。 \(S(0,0)=1, ~ \forall i_{\geq 1}. S(i,0)=0\) として、\(S(n,k) = k S(n-1,k) + S(n-1, k-1)\) が成立する区別できる \(n\) 個の要素を区別できない \(k\) 個のブロックに分割する方法の数\(f_k(x)=x