募集:いい考え方

小噺という建前で
アイデアがほしいという本音が丸見えなのは置いといて・・・

問題は
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008
のSum of 4 Integersという問題。
AOJの問題は簡単なのもあるのですが、結構骨のある問題がそろっています。
この問題は最初のほうなので、簡単な部類なりますかね。

ざっくり言うと・・・

0個以上36個以下の 「おまんじゅう」 と 3個の 「仕切り」 がある。
この「おまんじゅう」と「おまんじゅう」の間に「仕切り」を入れる。
ただし、「仕切り」と「仕切り」の間には1個も「おまんじゅう」が無くても構わないが、
10個以上「おまんじゅう」があってはならない。

わかりにくいので図で説明すると

仕切りの入れる場所をきめるので、

おまんじゅうの個数　と　36-おまんじゅうの個数　の小さいほうの数をAとすると、

_{A+3}C_{3}

で　仕切り方の通りの数が出る

と思うじゃん？

答えは　「出ないです」

なぜなら

4つ0-9の数字を選ぶ(同じ数を選んでもよい)通りは、

10＾4=10000通り

存在します。
しかし、

_{A+3}C_{3}

で答えを求めると、

2\sum_{A=0}^{17} (_{A+3}C_{3})=2(1+4+10+20+35+56+84+120+165+220+286+364+455+560+680+816+969+1140) ....①\\
_{18+3}C_{3}=1330....②\\
①+②＝13300

つまり　謎の組み合わせが　3300通り存在します。
この謎の組み合わせは
仕切りで区切った空間に10個以上「おまんじゅう」がある時。

これを数え内にはどうすればいいのだろう?

考え方をお待ちしております！

もちろん、執筆者本人も熱血考え中です。
アイデアが出次第、小噺2にでもそのアイデアを出したいと思います。
乞うご期待を！(誰得)

↓小噺2書きました！