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

180

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

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

$n \geq 2$ を整数とする． $n \times n$ のマス目にいくつかの駒を置く．一つのマスには $1$ つまでしか駒を置けないとき，どの行，どの列にもちょうど $2$ つの駒が置かれているような置き方は何通りあるか？

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

$n \times n$ のときの答えを $f (n)$ とおくと
$f (n) = (n!)^{2} \sum_{k = 0}^{n} (- 1)^{k} \frac{1}{2^{2 n - k} k!} (\binom{2 n - 2 k}{n - k})$

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

証明

前半

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

$n! \times 2^{n} \sum_{k = 0}^{n}_{n} C_{k} \times \frac{2^{k}}{k!} f (k) = (2 n)!$

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

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

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

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

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

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

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

$(_{n} C_{k})^{2} \times k! \times 2^{k} \times 2^{2 (n - k)} f (n - k)$

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

$\begin{aligned} (_{n} C_{k})^{2} \times (n - k)! \times 2^{n - k} \times 2^{2 k} f (k) & = \frac{(n!)^{2}}{(k!)^{2} {(n - k)!}^{2}} \times (n - k!) \times 2^{n + k} \times f (k) \\ = \frac{n! \times_{n} C_{k} \times 2^{n + k}}{k!} \times f (k) \end{aligned}$

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

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

　が成り立ちます．

後半

　 $F (x) = \frac{2^{k}}{k!} f (k), G (k) = \frac{(2 n)!}{n! \times 2^{n}} = (2 n - 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}$

　となります

$\sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (\binom{n}{k}) \times f (k) x^{n} = \sum_{k = 0}^{\infty} f (k) \times \frac{x^{k}}{(1 - x)^{k + 1}}$

また

$\sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) \times f (k + 1) x^{n + 1} = \sum_{k = 1}^{\infty} f (k) \times {(\frac{x}{1 + x})}^{k}$

$\begin{aligned} \sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (\binom{n}{k}) \times f (k) x^{n} & = \sum_{k = 0}^{\infty} f (k) \sum_{n = k}^{\infty} (\binom{n}{k}) x^{n} \\ = \sum_{k = 0}^{\infty} f (k) x^{k} \sum_{l = 0}^{\infty} (\binom{l + k}{k}) x^{l} \\ = \sum_{k = 0}^{\infty} F (k) \times \frac{x^{k}}{(1 - x)^{k + 1}} \end{aligned}$

　より第一式が示された．これを逆にたどる感じで

$\begin{aligned} \sum_{k = 1}^{\infty} f (k) \times {(\frac{x}{1 + x})}^{k} & = \sum_{k = 1}^{\infty} f (k) x^{k} \sum_{l = 0}^{\infty} (\binom{l + k - 1}{k - 1}) (- x)^{l} \\ = \sum_{k = 0}^{\infty} f (k + 1) x^{k + 1} \sum_{l = 0}^{\infty} (\binom{l + k}{k}) (- x)^{l} \\ = \sum_{k = 0}^{\infty} f (k + 1) \sum_{n = k}^{\infty} (\binom{n}{k}) x^{n + 1} \times (- 1)^{n - k} \\ = \sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) \times f (k + 1) x^{n + 1} \end{aligned}$

　も示された．

　補題より

$\begin{aligned} \sum_{k = 0}^{\infty} F (k) \times \frac{x^{k}}{(1 - x)^{k + 1}} & = \sum_{n = 0}^{\infty} G (n) x^{n} \\ \sum_{n = 0}^{\infty} F (n) \times {(\frac{x}{1 - x})}^{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}$

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

$\begin{aligned} \sum_{n = 0}^{\infty} F (n) y^{n} & = G (0) + \sum_{n = 1}^{\infty} (G (n) - G (n - 1)) {(\frac{y}{1 + y})}^{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) = \frac{n!}{2^{n}} \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) (2 k - 1)!!$

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

　これを更に変形すると

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