よくある問題1

• $\sum_{i=0}^{N-1} A_i = M$ となる、自然数列 $(A_i)_{i=0}^{N-1}$ の個数
• $\sum_{i=0}^{N-1} A_i = M$ となる、$1$ 以上の整数の列 $(A_i)_{i=0}^{N-1}$ の個数
• $\sum_{i=0}^{N-1} A_i = M$, $A_i \geq X_i$ となる整数列 $(A_i)_{i=0}^{N-1}$ の個数
• $\sum_{i=0}^{N-1} A_i = M$, $A_i \leq X_i$ となる整数列 $(A_i)_{i=0}^{N-1}$ の個数
• $\sum_{i=0}^{N-1} A_i \leq M$ となる自然数列 $(A_i)_{i=0}^{N-1}$ の個数
• $0 \leq A_0 < A_1 < \cdots < A_{N-1} < M$ となる自然数列 $(A_i)_{i=0}^{N-1}$ の個数
• $0 \leq A_0 \leq A_1 \leq \cdots \leq A_{N-1} < M$ となる自然数列 $(A_i)_{i=0}^{N-1}$ の個数

だいたいアルゴ式が出典

重複組合せ にもいくつか記載している。

よくある問題2

• 男子が4人、女子が3人いる。女子が隣り合わないのは何通り？
• a,b,c,d,e の5文字を並べて作った120個の文字列のうち、”cbdea” は何番目？94番目の文字列は何？
  • 解法
  • 一般化すると文字数×長さくらいの計算量で計算できるはず
  • 類題: ABC363 D - Palindromic Number
• 男子2人が隣り合う→男子2人をひとかたまりとして考える
  • 円順列の公式と2通りの考え方 | 高校数学の美しい物語