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

　お久しぶりです　ぴーです
　作問をしていたらいい感じの進捗が生まれたので共有します

　今回は下の問題を考えていきます．

　もしかしたら見たことある人もいるかも知れませんね
　この問題については lockerさんが記事を書いており 、以下のように既に結果が出ています．

　この記事では別のアプローチで答えを導出していきます

証明

前半

　前半では以下の式を示します

　証明：各行・列にちょうど$2$個置かれている$n\times n$ のマス目を用意します

　このマス目の各マス(大マスとします)をさらに四分割し、それぞれの駒を四つの小マスのうちの一つに配置することで、どの行・列にもちょうど$1$個置かれているような$2n\times 2n$マスを作ることを考えます

　このとき、元の$n\times n$マスの配置から$2n\times 2n$マスの配置を作る方法は各列の$2$個の左右、各行の$2$個の上下を決めればよいので$2^{2n}$個あります．

　逆に$2n\times 2n$の配置を決めれば$n\times n$の配置が存在する、と言いたいところですが、$1$マスに$2$個駒が入ってしまうような並び方が当然存在します

　ここで、各大マスにちょうど$1$個の駒が置かれている配置を良い配置とします

　このとき、駒が$2$個入ってしまった大マスが$k$個あるとすると、その$k$組の行・列を無視した$(n-k)\times (n-k)$マスは良い配置です

　$k$個の大マスの位置は$({}_n\mathrm{C}_k)^2\times k!$通り、各大マスで$2$個の駒の配置が$2$通り存在するので、駒が$2$個入ってしまった大マスが$k$個あるような配置は

$$ ({}_n\mathrm{C}_k)^2\times k!\times 2^k\times 2^{2(n-k)}f(n-k)$$

　通りあります．ただし$f(0) = 1$です．
　$k\rightarrow n-k$とすると

$$ \begin{aligned} ({}_n\mathrm{C}_k)^2\times (n-k)!\times 2^{n-k}\times 2^{2k}f(k) &=\dfrac{(n!)^2}{(k!)^2\{(n-k)!\}^2}\times (n-k!)\times 2^{n+k}\times f(k)\\ &=\dfrac{n!\times {}_n\mathrm{C}_k\times 2^{n+k}}{k!}\times f(k) \end{aligned}$$

　これを$0\leq k\leq n$で和を取ると、$2n\times 2n$で各行・列にちょうど$1$つあるような並べ方の総数になるので

$$ n!\times 2^n\sum_{k=0}^n\binom{n}{k}\times \dfrac{2^k}{k!}f(k) = (2n)!$$

　が成り立ちます．

後半

　$F(x) = \dfrac{2^k}{k!}f(k),\space G(k) = \dfrac{(2n)!}{n!\times 2^n} = (2n-1)!!$ とおけば($(-1)!! = 1$)

$$ \sum_{k = 0}^n\binom{n}{k}\times F(k) = G(n)$$

　となるので、これを満たす$F(n)$を形式的冪級数で求めます
　まず、両辺の母関数をとって

$$\sum_{n = 0}^\infty \sum_{k = 0}^n\binom{n}{k}\times F(k)x^n = \sum_{n = 0}^\infty G(n)x^n$$

　となります

　補題より

$$ \begin{aligned} \sum_{k = 0}^\infty F(k)\times \dfrac{x^k}{(1-x)^{k + 1}} &= \sum_{n = 0}^\infty G(n)x^n\\ \sum_{n = 0}^\infty F(n)\times \left(\dfrac{x}{1 - x}\right)^n &= (1 - x)\sum_{n = 0}^\infty G(n)x^n\\ &= G(0) + \sum_{n = 1}^\infty (G(n) - G(n - 1))x^n \end{aligned}$$

　となります．
　ここで$\dfrac{x}{1-x} = y$とおくと、$x = \dfrac{y}{1 + y}$なので

$$\begin{aligned} \sum_{n = 0}^\infty F(n)y^n &= G(0) + \sum_{n = 1}^\infty (G(n) - G(n - 1))\left(\dfrac{y}{1 + y}\right)^n\\ &= G(0) + \sum_{n = 0}^\infty\sum_{k = 0}^n (-1)^{n - k}\binom{n}{k}\times (G(k + 1) - G(k))y^{n + 1} \end{aligned}$$

　$2$行目への変形は補題$4$の$2$式目を使っています．
　$y^n(n\geq 1)$の係数を比較すると

$$\begin{aligned} F(n)&= \sum_{k = 0}^{n - 1}(-1)^{n - k - 1}\binom{n - 1}{k}\times (G(k + 1) - G(k))\\ &= \sum_{k = 1}^n (-1)^{n - k}\binom{n-1}{k - 1}G(k) - \sum_{k = 0}^{n - 1}(-1)^{n - k - 1}\binom{n-1}{k}G(k)\\ &= \sum_{k = 1}^{n - 1}(-1)^{n - k}\binom{n}{k}G(k) + (-1)^{n - 1} - G(n)\\ &= \sum_{k = 0}^n(-1)^{n - k}\binom{n}{k}G(k) \end{aligned}$$

　ということで

$$ f(n) = \dfrac{n!}{2^n}\sum_{k = 0}^n (-1)^{n - k}\binom{n}{k}(2k - 1)!!$$

　が示されました(個人的にはこっちの形のほうが好きです)

　これを更に変形すると

$$ \begin{aligned} \dfrac{n!}{2^n}\sum_{k = 0}^n (-1)^{n - k}\binom{n}{k}(2k - 1)!! &= \dfrac{n!}{2^n}\sum_{k = 0}^n (-1)^{n - k}\dfrac{n!}{k!(n - k)!}\times \dfrac{(2k)!}{2^kk!}\\ &= (n!)^2\sum_{k = 0}^n(-1)^{n - k}\dfrac{1}{2^{n + k}(n - k)!}\times \dfrac{(2k)!}{(k!)^2}\\ &= (n!)^2\sum_{k = 0}^n(-1)^{k}\dfrac{1}{2^{2n - k}k!}\binom{2n - 2k}{n - k} \end{aligned}$$

　となり、冒頭に乗せた結果と一致しました！

おわりに

　僕の今までの記事に比べたらめっちゃ真面目になってしまいました
　真面目じゃない記事も一応書き進めているので許してください

　最初に書いた通り、始めはただ作問をしていて
　「マス目を$2\times 2$でまとめれば一列に$2$個置く問題ができるじゃん！」
　と思いつき、考察を進めていくうちにこの結果が出たという感じです

　個人的にこの「各マスを更に分割する」アイデアはかなり気に入っています．しかし「$1$マスに$3$個」などの一般化は厳しそうなので、あまり汎用性はない気がします

　逆に、後半の議論で使った逆関数を取る部分は結構使えそうです(大丈夫な気はしますが、この議論をするものを他に見ないので危ない操作だったら教えてください)

　最後まで読んでいただきありがとうございました．