写像12相 (Twelvefold way)
概要
\(N\) 個のボールを \(K\) 個の箱に分けるときの通り数について
-
ボールの区別する/しない
-
箱の区別する/しない
-
箱に入れる制約なし/全ての箱にボール1個以下(単射)/全ての箱にボール1個以上(全射)
の条件で12通りの問題が考えられ、写像12相と呼ばれる。
ボールの区別 |
箱の区別 |
制約なし |
各箱一個以下 (\(N \le K\)) |
各箱一個以上 (\(K \le N\)) |
あり |
あり |
\(N^K\) |
\(_KP_N\) |
\(\displaystyle \sum_{k=1}^K (-1)^{K-k} {}_KC_k k^N\) |
なし |
あり |
\({}_{N+K-1}C_N (= {}_KH_N)\) |
\({}_KC_N\) |
\(_{N-1}C_{K-1}\) |
あり |
なし |
\(B(N, K)\) |
1 |
\(S(N, K)\) |
なし |
なし |
\(P(N+K, K)\) |
1 |
\(P(N, K)\) |
分割数 (partition number)
\(N\) を \(K\) 個の数に区別なく分割する時の通り数: \(P(N, K)\)
-
\(P(i, 1) = P(i, i) = 1\)
-
\(P(N, K) = P(N-K, K) + P(N-1, K-1)\)
実装
-
AOJ: "DPL_5_L: Probability - Ball and Boxes 12": source (Python3, 0.38sec)
N, K = map(int, input().split())
MOD = 10**9 + 7
D = [[0]*(K+1) for i in range(N+1)]
for i in range(1, N+1):
D[i][1] = 1
for i in range(1, min(N, K)+1):
D[i][i] = 1
for n in range(1, N+1):
for k in range(2, min(n-1, K)+1):
D[n][k] = (D[n-k][k] + D[n-1][k-1]) % MOD
print(D[N][K] % MOD)第2種スターリング数 (Stirling number of the second kind)
区別される \(N\) 個の要素を \(K\) 個のグループに分割する時の通り数: \(S(N, K)\)
-
\(S(0, 0) = 1\)
-
\(S(N, K) = S(N-1, K-1) + K * S(N-1, K)\)
実装
-
AOJ: "DPL_5_I: Probability - Ball and Boxes 9": source (Python3, 0.55sec)
N, K = map(int, input().split())
MOD = 10**9 + 7
D = [[0]*(K+1) for i in range(N+1)]
D[0][0] = 1
for n in range(1, N+1):
D0 = D[n-1]
for k in range(1, K+1):
D[n][k] = (D0[k-1] + k * D0[k]) % MOD
print(D[N][K])ベル数 (Bell number)
区別される \(N\) 個の要素を \(K\) 個以下のグループに分割する時の通り数: \(B(N, K)\)
-
\(\displaystyle B(N, K) = \sum_{k=0}^K S(N, k)\)