モンモールの問題の応用

更新 2021/03/07

1987年国際数学オリンピックキューバ大会の第一問の2通りの解法を紹介します。

問題

$p_n(k)$ を不動点をちょうど $k$ 個持つ $n$ 次の置換の数とする。

このとき， $\displaystyle\sum_{k=0}^nk\cdot p_n(k)=n!$ を証明せよ。

ただし， $n$ 次の置換とは，集合 $S=\{1,2,\cdots,n\}$ から $S$ への一対一対応であり， $f(i)=i$ を満たすとき $i$ を置換 $f$ の不動点と呼びます。

1つめは double counting を用いた美しい方法。2つめは，攪乱順列（完全順列）の個数を求める公式を用いて計算でゴリ押す方法です。

なお，置換については置換の基礎（互換・偶置換・奇置換・符号の意味）もどうぞ。

とりあえず実験してみる

数学オリンピックの組み合わせの問題ではとりあえずnnn が小さい場合の実験をすることが重要です。
n=3n=3n=3
 で実験してみます。3次の置換を
(1,2,3)(1,2,3)(1,2,3)
 などと表します。
(1,2,3)(1,2,3)(1,2,3)
 →不動点3つ
(1,3,2),(3,2,1),(2,1,3)(1,3,2),(3,2,1),(2,1,3)(1,3,2),(3,2,1),(2,1,3)
 →不動点1つ
(2,3,1),(3,1,2)(2,3,1),(3,1,2)(2,3,1),(3,1,2)
 →不動点0
よって，示すべき式の左辺は，0⋅2+1⋅3+3⋅1=60\cdot 2+1\cdot 3+3\cdot 1=60⋅2+1⋅3+3⋅1=6
 となり確かに成立しています。
この実験を通じて，「左辺は全ての置換の不動点の数の和を表している」ということに気づければ以下のような美しい解答ができます。

方法1：double countingによる

同じ量を2通りの異なる方法で数えてそれらが等しいことから等式を示す方法を double counting method といいます。英語ではたいそうな名前がついていますが，原理は単純で，入試レベルでも自然に使っているテクニックです。

例えば，場合の数を2通りの方法で数えることで二項係数の関係式が導けます（二項係数の有名公式一覧と2つの証明方針の最後の方）。

解答1

示すべき式の左辺は「全ての置換の不動点の数の和」を表している。

一方任意の $i\:(1\leq i\leq n)$ に対して， $i$ が不動点となる置換の数は $(n-1)!$ 個あるので，「全ての置換の不動点の数の和」は， $n\cdot (n-1)!=n!$ とも数えられる。よって問題の等式は示された。

この問題は比較的単純ですが，double counting methodは数オリの問題では頻出なので頭の隅に置いておきましょう。

上記の解答1は多少発想力が必要ですが，次に紹介する解答2は攪乱順列の公式を知っていればほとんど機械的な計算で証明できます！

方法2：攪乱順列の公式による

以下の解答では計算を一部省略していますが，途中計算は（シグマ計算や二項係数の関係式の証明に慣れていれば）ほとんど機械的に行うことができます。

方針

モンモールの問題を知っていれば公式を用いて $p_n(k)$ を求めることができます。そうすればただの恒等式の証明問題に帰着されます。式がゴツくてしんどいですが数学的帰納法を用いて証明できます。

解答2

$p_n(n)=1,p_n(n-1)=0$ であり， $k\leq n-2$ のとき，

$p_n(k)={}_n\mathrm{C}_ka_{n-k}$

ただし， $a_{n-k}$ は長さ $n-k$ の攪乱順列の数（不動点の選び方が ${}_n\mathrm{C}_k$ 通りで残りの撹乱の仕方が $a_{n-k}$ 通りとなる）。

これに，攪乱順列の公式を用いると示すべき式の左辺は，

$n+\displaystyle\sum_{k=1}^{n-2}k\dfrac{n!}{k!(n-k)!}\left\{(n-k)!\sum_{t=2}^{n-k}\dfrac{(-1)^t}{t!}\right\}\\ =n+\displaystyle\sum_{k=1}^{n-2}\sum_{t=2}^{n-k}\dfrac{n!(-1)^t}{(k-1)!t!}$

これが $n!$ に等しいことを数学的帰納法で証明する。

計算の詳細は省略するが，

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

を証明する問題に帰着される。

この式は二項定理の展開式っぽいことに注意すると，

$0=(1-1)^n$ を展開することにより証明できる。

攪乱順列の公式は覚える必要はありません。試験場で導けばよいのです。数学オリンピックは1問にたっぷり時間をかけることができるので，なんやかんやでもし1時間程度かかったとしても，1問完答というのは大きな価値があります。

ごく一部の天才を除き，多くの人にとって，難しい発想なしで完答するための戦略をいかにたてられるかが勝負になります。そういう意味で解答2は解答1よりも優れています（少なくとも私は解答1の発想の方が難しいと感じました）。

美しい解答がいつも「優れている」とは限りません。

Tag:国際数学オリンピックの過去問

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！