以前やったように封筒から取り出した回数で分類して速くならないでしょうか。
例えば、A3を使うとして状態が(0, 0, 1)だったとすると、取り出した回数が3回なので、A4までで考えると、(0, 0, 1, 3), (0, 0, 1, 2), (0, 0, 1, 1), (0, 0, 1, 0)の状態が考えられます。(0, 0, 1)には2つの手順が考えられます。この手順をPQRと書くとすると、(0, 0, 1, 1)になるにはこれにA4を取り出す操作Sを2つ付け加えた手順が必要です。考えられる手順は、
PSQSR PSQRS PQSSR PQSRS PQRSS
の5つが考えられます。SPQSRとかはダメです。最初のSのときに封筒にA4がないからです。この手順の種類の数をD(3, 2, 0)と書きましょう。3は元の操作回数、2はA4を取り出す回数、0はこの前の時点でのA4の枚数です。最初にどの操作をするかで次のように漸化式が書けます。
D(n, m, l) = D(n - 1, m, l + 1) + D(n, m - 1, l - 1)
ただし、nかmが0なら1、lが0なら右辺の第2項はありません。
(0, 0, 1)になる操作手順は2つだったので、(0, 0, 1, 3)になる操作手順は2D(3, 0, 0) = 2、以下、
(0, 0, 1, 2) : 2D(3, 1, 0) = 6
(0, 0, 1, 1) : 2D(3, 2, 0) = 10
(0, 0, 1, 0) : 2D(3, 3, 0) = 10
となります。取り出した回数だけが分かれば手順の数が決まることがわかるでしょう。
これを実行すると、
2 3.000000e+00 3 8.000000e+00 4 1.250000e+02 5 1.911700e+05 6 7.087287e+12 7 4.046345e+29 8 1.513483e+65 9 6.820949e+138 10 1.259179e+289
これ以上の計算は厳しいようです。
