yukicoder No.741 AscNumber(Easy)

問題概要

0～9で構成されるN文字の文字列のうち、桁が昇順になるものはいくつか？

解説

もう少し問題を言い換えてみます．

• 10種類の数字が書き込まれたカードが無尽蔵にある
• N枚のカードを山から取り出して，昇順に並べる．
• 出来上がる数列は何通り存在するか？

重要な考察として，「昇順に並べているので，順列は関係ない」がある．

解に関係するのは，「N枚のカードを山から取り出したとき，どのカードを何枚持っているか」だけである．

よって，更に問題を言い換えることができて，

• 10種類の数字が書き込まれたカードが無尽蔵にある
• N枚のカードを山から取り出したときのカードの組み合わせの数は何通りか？

10種類のカードから重複を許してN枚取り出すので， *1を出力すれば良いです．

*1:重複組合せ