重複組合せの数え上げの例

以下すべて ${}{N+K-1}C{K-1}$ 通り。${K}H{N}$ と書く。

• 区別できない $N$ 個のボールを区別できる $K$ 個の箱に入れる入れ方
• $K$ 個の区別できるものの中から重複を許して $N$ 個選ぶ選び方
• $\sum_{i=0}^{K-1} C_i = N$ となる、自然数列 $(C_i)_{i=0}^{K-1}$ の個数
• $0 \leq A_0 \leq A_1 \leq \cdots \leq A_{N-1} < K$ となる自然数列 $(A_i)_{i=0}^{N-1}$ の個数

これらの派生形は 初等組合せ論典型問題 に記載している

多重集合については 多重集合

全列挙

• sorted 列ベースでの全列挙
• 頻度分布ベースの全列挙

出題例

• ABC440 E - Cookies
• ABC458 E - Count 123

その他

• 重複組合せで「k個から」と言われたら、その段階でk-1個の仕切りをイメージするといいかも
• 負の二項分布
  • r回成功したら終わりとする。i回成功した状態を第iラウンドと呼ぶ。k回失敗した場合、r個のラウンドから失敗したときのラウンドをk回重複を許して選ぶときの組合せが……