\(M=0\) のとき答えは \(1\) です。以降 \(M \ge 1\) を仮定します。

実は、\(N\) を固定したとき答えが非零となるためには \(M \le 2N - 3\) が必要であることが証明できます。以降 \(M \le 2N - 3\) と仮定します。(円周上で隣り合っていない頂点を結ぶ辺を \(1\) 本取ると漸化式が立ち、帰納的に証明できます。)

多重辺を許容すると、以下のような手続きで全てのグラフを作ることが出来ます。

• 空の数列 $A$ を作り、以下を $v=1,2,\dots,N$ の順で行う。
• 「$A$ の末尾を $u$ とする。頂点 $u$ と頂点 $v$を結ぶ辺を追加し、$A$ から $u$ を削除する。」を好きな回数行う。
• $A$ に $v$ を好きな個数末尾に挿入する。

この手続きによって得られるグラフが条件を満たすこと、異なる手続きによって得られるグラフは異なること、条件を満たすグラフはこの手続きによって得られることが確認できます。

さて、多重辺を許容しない・したときの答えの母関数を \(F(x),G(x)\) とします。ここで、\(G_i = \sum_{j=0}^{i} \binom{i-1}{j-1} F_i\) が成り立ちます。つまり、\(F'(x) = \sum_{i=1}^{\infty} \frac{F_ix^{i-1}}{(i-1)!},G'(x) = \sum_{i=1}^{\infty} \frac{G_ix^{i-1}}{(i-1)!}\) 定義すると、\(F'(x)e^x = G'(x)\) が成り立ちます。よって、\(G'(x)e^{-x} = F'(x)\) より \(F_M= (M-1)! \sum_{i=0}^{M-1} \frac{(-1)^{M+i+1}G_{i+1}}{i!(M-1-i)!}\) が成り立ちます。

\(k=1,2,\dots,M\) に対して高速に \(G_k\) を求めることを考えます。\(G_k\) は、以下のような問題の答えに言い換えられます。

初め $(0,0)$ にいる。ここから $N$ 回、以下の移動を繰り返して $(k,k)$ にたどり着く方法の個数を求めよ。ただし、常に $x$ 座標 $\ge$ $y$ 座標である必要がある。

• 非負整数 $p$ を選び、$y$ 座標に $p$ を加える。
• 非負整数 $q$ を選び、$x$ 座標に $q$ を加える。

まず、\(1\) 回目の \(y\) 座標の移動と \(N\) 回目の \(x\) 座標の移動は必要ないため以下のように言い換えられます。

初め $(0,0)$ にいる。ここから $N-1$ 回、以下の移動を繰り返して $(k,k)$ にたどり着く方法の個数を求めよ。ただし、常に $x$ 座標 $\ge$ $y$ 座標である必要がある。

• 非負整数 $q$ を選び、$x$ 座標に $q$ を加える。
• 非負整数 $p$ を選び、$y$ 座標に $p$ を加える。

更に、\(x,y\) 座標それぞれの遷移を考えると以下のように言い換えられます。

長さ $N$ の非負整数列の組 $A=(A_0,A_1,\dots,A_{N-1}),B=(B_0,B_1,\dots,B_{N-1})$ であって以下の条件を満たすものの個数を求めよ。

• $0 = A_0 \le A_1 \le A_2 \le \dots \le A_{N-1} = k$
• $0 = B_0 \le B_1 \le B_2 \le \dots \le B_{N-1} = k$
• $A_i \ge B_i(0 \le i \le k')$

そして、\(A\) を \((0,0) \rightarrow (A_1,0) \rightarrow (A_1,1) \rightarrow (A_2,1) \rightarrow (A_2,2) \rightarrow \dots \rightarrow (A_{N-2},N-3) \rightarrow (A_{N-2},N-2) \rightarrow (A_{N-1},N-2)\) のようにプロットし、\(B\) も同様にすると更に以下のような問題に言い換えられます。

$(0,0)$ から $(k,N-2)$ まで右か上への移動を繰り返し行く方法の組 $(P,Q)$ のうち、$P$ が常に $Q$ の上にあるもの(重なってもよい)の個数を求めよ。

ここで、\(N+k-2\) 回の移動列のうち、\(P,Q\) の \(x\) 座標の変化が \((0,0),(0,+1),(+1,0),(+1,+1)\) となった回数をそれぞれ \(a,b,c,d\) と固定します。ここで、\(a,b,c,d\) は非負整数 \(i\) を用いて \((N-2-i,i,i,k-i)\) と表せます。そして、このとき条件を満たす \((P,Q)\) の個数は \(\frac{C_i(N+k-2)}{(N-2-i)!(2i)!(k-i)!}\) となります。(\(C_i\) はカタラン数)

よって、この問題の答えは \(\sum_{i=0}^{k} \frac{C_i(N+k-2)}{(N-2-i)!(2i)!(k-i)!} = \sum_{i=0}^{k} \frac{(N+k-2)!}{(N-2-i)i!(i+1)!(k-i)!}\) となります。

ここで突然ですが以下の問題を考えます。

$N+k-1$ 個のボールがある。ここから $N-2$ 個を赤色に塗り、$k$ 個を青色に塗る。両方の色で塗られたボールは紫色になる。色の塗り方の個数を求めよ。

この問題の答えは \(\binom{N+k-1}{N-1}\binom{N+k-1}{N-2}\) です。また、紫色のボールの個数を全探索することで \(\sum_{i=0}^{k} \frac{(N+k-1)!}{(N-2-i)i!(i+1)!(k-i)!}\) と表すこともできます。よって、\(\sum_{i=0}^{k} \frac{(N+k-1)!}{(N-2-i)i!(i+1)!(k-i)!} = \binom{N+k-1}{N-1}\binom{N+k-1}{N-2}\) が成り立ちます。

これを用いると、上記の式 \(\sum_{i=0}^{k} \frac{(N+k-2)!}{(N-2-i)i!(i+1)!(k-i)!}\) が \(\frac{\binom{N+k-1}{N-1}\binom{N+k-1}{N-2}}{N+k-1}\) と等しいことが分かります。よって、\(G_k = \frac{\binom{N+k-1}{N-1}\binom{N+k-1}{N-2}}{N+k-1}\) となります。

よって、答えは \((M-1)! \sum_{i=0}^{M-1} \frac{(-1)^{M+i+1}\binom{N+i}{N-1}\binom{N+i}{N-2}}{i!(M-1-i)!(N+i)}\) となります。この値は \(\mathrm{O}(N)\) で求めることが出来ます。