高校数学解説

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

組み合わせ,母関数

2086

お久しぶりです。学校のレポートとして提出したものを記事にしておこうと思います。

問題の設定

今回、興味を引かれたのが次の問題1です。

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

上記の問題を考えついた時点ではその解答を知らなかったため、これを解決することをレポートの目標としました。この記事では、問題1の母関数を用いた解決を述べたいと思います。

なお、問題1の解答を数列として並べたものが、オンライン整数列大辞典における数列 A001499 に掲載されています。

結論

先に結論を述べてしまいましょう！

（問題1の解答）

$n \geq 2$ についての問題1の答えを $p_{n}$ で表す． $p_{0} = 1$ および $p_{1} = 0$ とすれば，形式的冪級数として以下の等式が成り立つ：
$\sum_{k \geq 0} \frac{p_{k}}{(k!)^{2}} x^{k} = \frac{e^{- \frac{1}{2} x}}{\sqrt{1 - x}} .$
また，
$p_{n} = (n!)^{2} \sum_{k = 0}^{n} ((- 1)^{k} \frac{1}{2^{2 n - k} \times k!} (\binom{2 n - 2 k}{n - k})) .$

わお。なかなかキモい冪級数が登場しましたね。では証明していきましょう。
まず簡単な準備をしておきます。

(準備)

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

前半の証明

前半を示すために（まあほとんど前半が本質なんですが）次の補題を用意します。

条件を満たすグラフであって，周期が $2 a_{1}$ のサイクルを $c_{1}$ 個， $2 a_{2}$ のサイクルを $c_{2}$ 個， $\dots$ ， $2 a_{k}$ のサイクルを $c_{k}$ 個持つようなものは
$(n!)^{2} \times \frac{1}{\prod_{i = 1}^{k} (2 a_{i})^{c_{i}} \times c_{i}!}$
個存在する．ここで， $a_{1} c_{1} + \dots + a_{k} c_{k} = n$ であり，各 $a_{i}$ は $2$ 以上で異なるとする．

(補題2)

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

これで準備ができたので、前半が証明できます。

(命題1の前半)

補題 2.1 の結論の式は次のように変形できる．
$\begin{matrix} (1) & \frac{(n!^{2})}{c!} \times \frac{1}{\prod_{i} (2 a_{i})^{c_{i}}} \times \frac{c!}{\prod_{i} c_{i}!} \end{matrix}$
ここで， $c = c_{1} + \dots + c_{n}$ と置いた．サイクルの周期によって場合分けすることを考えれば， $(1)$ の値を適切（※1）な $(a_{1}, \dots, a_{k}, c_{1}, \dots, c_{k})$ すべてに渡って足し合わせた値が問題1の解答となる．
$c$ を固定する． $\frac{c!}{\prod_{i} c_{i}!}$ が $c_{1}, c_{2}, \dots, c_{n}$ 個の区別されたものの並べ替えの総数であることを踏まえれば，(1) の値の総和は
$\frac{(n!)^{2}}{c!} {(\frac{x^{2}}{4} + \frac{x^{3}}{6} + \frac{x^{4}}{8} + \dots)}^{c}$
という形式的冪級数の $x^{n}$ の係数として与えられることが分かる． $c$ を動かすことで，求めるべき場合の数 $p_{n}$ は
$P (x) = \frac{x^{2}}{4} + \frac{x^{3}}{6} + \dots, Q (x) = 1 + \frac{P (x)}{1!} + \frac{P (x)^{2}}{2!} + \dots$
で表される $Q (x)$ の $x^{n}$ の係数に $(n!)^{2}$ を掛けたものとして与えられる．いま，これらは形式的冪級数として
$\begin{aligned} P (x) & = \frac{1}{2} (- \log (1 - x) - x), \\ Q (x) & = e^{P (x)} \\ = \frac{e^{- \frac{1}{2} 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^{- \frac{1}{2} x}}{\sqrt{1 - x}}$
が従う．よって，前半の主張が示された．

後半の証明

命題の後半を示すために、次の補題3(※3)を用意します。

形式的冪級数として，
$\frac{1}{\sqrt{1 - 4 x}} = \sum_{k \geq 0} (\binom{2 k}{k}) x^{k} .$

(補題3)

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

さあ、いよいよ命題の後半です。

(命題1の後半)

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

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

※印たち

※1　例えば、 $a_{i}$ のいずれかが $1$ である場合は不適切です。補題 2 が適切な組について常に正しいのは幸いなことです。

※2　本当は $\log$ や微分などの操作はより厳密に行わないといけないはずですが、ここでは割愛しています。これは知識不足によるもので、申し訳ないです。

※3　この補題に関しては、全面的に kaichou243 氏の結果を引用しました。ありがとうございました。

振り返って

これで命題1が示されました。どうだったでしょうか。母関数の議論の部分は、ごく、本当にごく一部の層には見覚えがあるかもしれません。
それは何かと言うと、 OMC074-E のユーザー解説です。読んでもらえば分かりますが、ほぼ同じ発想で示せるんですね。

問題1は，「どの行，列にもちょうど $1$ 個」の場合に比べると数え上げることが格段に困難な問題であったと思います。それを形式的冪級数を用いて解決することができたのは面白かったです。今後は、より発展的な形式的冪級数に関する知識（特に微分など）を深めていきたいと思います。（※2や※3など、知識不足が見られますからね...。）

読んでくれてありがとうございました。では、また会う日まで。

投稿日：2023年9月17日