『アリさんの小さなナップザック』

アリさんは５つの小さなナップザックをもって出かけます。
これら５個を区別することはできません。

一つのナップザックには最大３個のナップザックを入れます。
ただし、入れるナップザックの中にあるナップザックの数は含みません。

アリさんは１つのナップザックしか背負えません。

【問題１】

アリさんが出かけるとき、５個の小さなナップザックのパッキングの方法は何通りあるでしょうか。

【問題２】

アリさんのＮ個の小さなナップザックのパッキングの方法の数を計算します。

Ｎ個のパッキングの数を　Pac(N)とし、これを係数とする整数係数多項式Ａ_nを次のように定義します。

Pac(0)=1 Pac(1)=1 Pac(2)=1
Pac(3)=2 Pac(4)=4 Pac(5)=問題１・・・・

Ａ_n(ｔ)= n
Σ
i=0 Ｐac(ｉ)ｔⁱ

このとき、下記の形式で多項式空間（環）におけるＡ_nの漸化式を見つけてください。

Ａ_n(ｔ)＝１＋Ｇ(ｔ，Ａ_n-1)　mod ｔⁱ⁺¹

注１）Ｇ(t,A)は汎関数であって、例えばｔ{Ａ(ｔ)²＋Ａ(ｔ²)}のようなものです。

注２）mod ｔⁱ⁺¹は「ｔのｉ＋１乗以上の項を無視する」程度の意味です。

【問題２　ヒント】

アリさんの背負っているナップザックの中の状態はつぎの３ケースの和で、
Ｎ－１以下の場合の数から漸化的に計算されます。

【問題３】

問題２の式をベースにＰac(Ｎ)を計算するアルゴリズムを考え、その計算量をＮの式でおよそ表してください。
およそとは±１の誤差とし、その代り、Nで場合分けしない１つの式としてください。
計算量は下記条件で求めるものとします。

【問題４】

１７個の小さなナップザックの場合の数　Ｐac(１７)　を計算してください。

【おまけ１】

問題３の答えはＮの２次式のオーダーで得られたと思いますが、
(1)～(5)の定義のアバウトな点をつくと、ここで言う「計算量」がＮの一次式のオーダーとなる方法があります。
それはどんな方法でしょうか。
（実際のプログラムでの計算量はＮの２次式以上になってしまいます。）

【おまけ２】

本当の意味で計算量がＮの一次式程度のアルゴリズム（問題２にこだわらない）はあるでしょうか。？？？
（cf. 『５つのナップザック』の問題では存在し、計算量はN－２　）

【うんちく】

アリさんをカルボキシル基（COOH）に、小さなナップザックを炭素（Ｃ）に置き換え、空いているところを水素（Ｈ）で埋めると、飽和脂肪酸の分子構造式になります。

つまり、Pac(Ｎ)は炭素数がN+1の飽和脂肪酸の族での構造異性体の数になります。

問題１に対応する物質は俗称でカプロン酸（C₅H₁₁COOH）、
問題４に対応してはステアリン酸（C₁₇H₃₅COOH）と呼ばれています。

因みに、N=1に対応するのは酢酸（＝酢）（CH₃COOH）であり、
N=０に対応するのは　蟻（ギ）酸（HCOOH）　です。