ある数え上げの問題について

ある駒の配置に対して，駒の置いてあるマスを頂点とし，同じ行または列にある頂点の間に辺を張った無向グラフを考える．このようにしてできるグラフと駒の配置は1対1に対応するから，以下ではグラフに注目して数え上げを行う．グラフに対応する駒の配置が問題の条件を満たすとき，グラフが条件を満たすと呼ぶことにする．
このグラフの全ての頂点の次数は $2$ であるから，周期が $3$ 以上であるようないくつかのサイクルに分解することができる．それぞれのサイクルの周期は偶数である．

各サイクルに注目しよう．周期が $2a$ のサイクルの頂点は $a$ 行，$a$ 列にまたがり，それぞれの行，列に $2$ つずつの頂点を持つ．これらの行 $r_1, \cdots, r_a$ および列 $c_1, \cdots, c_a$ を固定するとき，サイクルは次のような順列
$$r_1，c_{i_1}，r_{j_1}， c_{i_2}， r_{j_2}， \cdots， r_{j_{a-1}}， c_{i_a} ， r_1$$
（ただし $i_1 < i_a$ ）と一対一に対応する．実際，上の順列において隣り合っている二つの行・列の交点を取り，それらを頂点とするようなサイクルが対応する．よって，この場合にサイクルは $\dfrac{a! \times (a-1)!}{2}$ 通り存在する．
一旦すべてのサイクルを区別して考える．異なるサイクルは異なる行，列にまたがることに注意すると，それぞれのサイクルに行・列を割り当てる方法は
$$\left(\frac{n!}{\prod_i (a_i)!^{c_i}}\right)^2$$
通りである．それぞれの割り当て方に対して，（サイクルの決め方が互いに干渉しないことから）
$$\prod_i \left(\frac{a_i! (a_i-1)!}{2}\right)^{c_i}$$
通りのグラフが存在するから，すべてのサイクルを区別するときのグラフの数は
$$\left(\frac{n!}{\prod_i (a_i)!^{c_i}}\right)^2 \times \prod_i \left(\frac{a_i! (a_i-1)!}{2}\right)^{c_i} = \frac{(n!)^2}{\prod_i (2a_i)^{c_i}}$$
通りである．同じ周期のサイクルの区別を無くすために $\prod_i (c_i)!$ で割れば，結論が得られる．（補題の証明終わり）

補題 2.1 の結論の式は次のように変形できる．
\begin{equation} \frac{(n!^2)}{c!} \times \frac{1}{\prod_i (2a_i)^{c_i}} \times \frac{c!}{\prod_i c_i!} \tag{1} \end{equation}
ここで，$c=c_1+\cdots+c_n$ と置いた．サイクルの周期によって場合分けすることを考えれば，$(1)$ の値を適切（※1）な $(a_1, \cdots, a_k, c_1, \cdots, c_k)$ すべてに渡って足し合わせた値が問題1の解答となる．
$c$ を固定する．$\dfrac{c!}{\prod_i c_i!}$ が $c_1, c_2, \cdots, c_n$ 個の区別されたものの並べ替えの総数であることを踏まえれば，(1) の値の総和は
$$\frac{(n!)^2}{c!} \left(\frac{x^2}{4} + \frac{x^3}{6} + \frac{x^4}{8} + \cdots \right)^c$$
という形式的冪級数の $x^n$ の係数として与えられることが分かる．$c$ を動かすことで，求めるべき場合の数 $p_n$ は
$$P(x) = \frac{x^2}{4} + \frac{x^3}{6}+ \cdots,　Q(x) = 1+\frac{P(x)}{1!}+\frac{P(x)^2}{2!}+\cdots$$
で表される $Q(x)$ の $x^n$ の係数に $(n!)^2$ を掛けたものとして与えられる．いま，これらは形式的冪級数として
$$ \begin{aligned} P(x) &= \frac12 \left(-\log(1-x)-x\right), \\ Q(x) &= e^{P(x)} \\ &= \frac{e^{-\frac12 x}}{\sqrt{1-x}} \end{aligned} $$
と計算できる(※2)．$Q(x)$ の定数項，$1$ 次の係数がそれぞれ $1,0$ であることから，
$$\sum_{k\geq 0} \frac{p_k}{(k!)^2} x^k = \frac{e^{-\frac12 x}}{\sqrt{1-x}}$$
が従う．よって，前半の主張が示された．

等式の右辺を $f(x)$ とおく．このとき，簡単な計算により
$$f^\prime (x) = \sum_{k\geq 0} (4k+2) \binom{2k}{k}x^k,　xf^\prime (x) = \sum_{k\geq 0} k \binom{2k}{k} x^k$$
を得る．これより，
$$\begin{aligned} (1-4x)f^\prime (x) &= 2f(x)\\ \frac{f^\prime(x)}{f(x)} &= \frac{2}{1-4x} \\ \int \frac{f^\prime(x)}{f(x)} dx &= \int \frac{2}{1-4x} dx\\ \log f(x) &= -\frac12 \log \frac{1}{1-4x} \end{aligned}$$
が順に従う．いま $f(x)$ の定数項は $1$ であるから，$f(x)=(1-4x)^{-1/2}$ を得る．（補題の証明終わり）

補題2.2より，
$$\begin{aligned} \frac{e^{-\frac12 x}}{\sqrt{1-x}} &= \left(\sum_{k\geq 0} \frac{(-x/2)^k}{k!}\right)\left(\sum_{k\geq 0} \binom{2k}{k} \left(\frac14 x\right)^k \right) \\ &= \sum_{n\geq 0} \sum_{k=0}^{n} \left((-1)^k \frac{1}{2^{2n-k}\times k!} \binom{2n-2k}{n-k}\right) x^n \end{aligned}$$

が成立する．前半の主張にこれを合わせることで，後半の主張を得る．（証明終わり）