写像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)\)

参考ページ