最近電車の中で考えているのは、
n個のものを分ける分け方は何通り？
言い換えれば。正の*1の整数のみを含む集合で、総和がnになるものは何種類ある？
例えば。
3個なら：{3},{2,1},{1,1,1}の3通り。
6個なら：{6},{5,1},{4,2},{4,1,1},{3,3},{3,2,1},{3,1,1,1},{2,2,2},{2,2,1,1},{2,1,1,1,1},{1,1,1,1,1,1} の11通り。
という、簡単そうな問題。
簡単そうなんだが、実は解けてない。
別の用事で列挙していたら、6個の場合に素数になったのがとても意外で、考えることにした。
36個の場合は、私の計算が間違えてなければ 17977通り。これも素数。漸化式にしかならないのかも。
オーダーは 2^(n/2) 弱っぽい。弱はだめですかそうですかすいません。
あと。ある数が素数かどうか知りたければ、google に当たるといい。前出の 17977 なら google:17977 primeで素数であることが確認（？）できる。素数表にないような大きな数は出ないが、百万ぐらいまでは大丈夫そうである。この方法ならプログラムを組む必要がないので、携帯電話でも調べられる。
私は ruby で書いたけど。
*1:最初は「非負の」と書いていたが、当然「正の」の間違いであった。とほほ
