あれこれ考えたのですが。
例えば、必要な紙がA3だったとしましょう。すなわち、A4、A5まで紙は切られません。そうすると取りうる状態は、
(1, 0, 0), (0, 1, 1), (0, 1, 0), (0, 0, 2), (0, 0, 1), (0, 0, 0)
の6つになります。同じ手順でA4が必要だったとしましょう。そうすると、封筒から取り出した回数と同じ数だけA4の紙があることになります。例えば、(0, 1, 0)は2回取り出しているので、(0, 1, 0, 2)ということになります。また、(0, 1, 0, 1)、(0, 1, 0, 0)という状態も考えられます。このように何回取り出したかというのが重要になってきます。そして、(0, 1, 0, 2)は2回、(0, 1, 0, 1)は3回、(0, 1, 0, 0)は4回になります。状態を数えるだけならもうこの指標だけあればよいことが分かるでしょう。A3のときの各状態のこの指標を書いてみましょう。
(1, 0, 0) : 0, (0, 1, 1) : 1, (0, 1, 0) : 2, (0, 0, 2) : 2, (0, 0, 1) : 3, (0, 0, 0) : 4
もう具体的な情報は要りません。指標だけ要るのでこの指標を取る状態の数をだけ持つことにしましょう。そうすると、
(1, 1, 2, 1, 1)
となります。2回だけ2状態あり、他は1状態です。
さて、A3がこう表されるとき、A4はどうなるでしょう。例えば、先ほど見たように2回は、2回と3回と4回という状態に移行します。一般にm回はm回〜2m回という状態に移行します。ですから、Anがsと書けたらA(n+1)は次のように書けます。
def next(s): n = len(s) s1 = [ 0 ] * (n * 2) for m in xrange(n): for k in xrange(m, m * 2 + 1): s1[k] += s[m] return s1
これは素直に書いた場合で、逆から考えると次のように簡単に書けます。
def next(s): n = len(s) return [ sum(s[(k+1)/2:min(n,k)+1]) for k in xrange(n * 2) ]
A1のみのときは状態は(1)と(0)なので、(1, 1)と書けます。ここから始めて上の関数で次を求めていきます。そして全ての項を足し合わせれば全ての状態の数となります。
N = 15 s = [ 1, 1 ] for k in xrange(2, N + 1): s = next(s) print k, sum(s)
計算すると、
2 3 3 6 4 18 5 87 6 699 7 9552 8 226593 9 9471846 10 705154188 11 94285792212 12 22807963405044 13 10047909839840457 14 8110620438438750648 15 12062839548612627177591
これ以上は厳しそうです。
いろいろがんばってみたのですが、数学的に求めることはできませんでした。
