「写像12相」を総整理！ 〜 数え上げ問題の学びの宝庫 〜 #AtCoder - Qiita

写像12相

• 玉の数: n

• 箱の数: k

• 依存関係

  

  画像の出典: 「写像12相」を総整理！ 〜 数え上げ問題の学びの宝庫 〜 #AtCoder - Qiita

[1] 玉区別あり・箱区別あり・1個まで

• 箱をn個選んで並べる

[2] 玉区別あり・箱区別あり・制限なし

• 重複順列

[3] 玉区別あり・箱区別あり・1個以上

• 包除原理をする

[4] 玉区別なし・箱区別あり・1個まで

• 箱をn個選ぶ

[5] 玉区別なし・箱区別あり・制限なし

• 玉を棒で区切って箱に入れる

[6] 玉区別なし・箱区別あり・1個以上

• 箱に玉を1つずつ入れた状態で[5]を行う

[7] 玉区別あり・箱区別なし・1個まで

• 0 or 1 (玉が多いと1個までの制約に引っかかる)

[8] 玉区別あり・箱区別なし・制限なし