2014/05/17

モンモールの問題の応用

分野: 場合の数  レベル: 数学オリンピック

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つめは,攪乱順列の公式を用いて計算でゴリ押す方法です。

なお,置換については置換と偶置換・奇置換に関する基礎的なこともどうぞ。

とりあえず実験してみる

数学オリンピックの組み合わせの問題ではとりあえず $n$ が小さい場合の実験をすることが重要です。

$n=3$ で実験してみます。3次の置換を$(1,2,3)$ などと表します。
$(1,2,3)$ →不動点3つ
$(1,3,2),(3,2,1),(2,1,3)$ →不動点1つ
$(2,3,1),(3,1,2)$ →不動点0

よって,示すべき式の左辺は,$0\cdot 2+1\cdot 3+3\cdot 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)={}_nC_ka_{n-k}$
ただし,$a_{n-k}$ は長さ $n-k$ の攪乱順列の数。(不動点の選び方が${}_nC_k$ 通りで残りの撹乱の仕方が $a_{n-k}$ 通りとなる)
これに,攪乱順列の公式を用いると示すべき式の左辺は,
$n+\displaystyle\sum_{k=1}^{n-2}k\dfrac{n!}{k!(n-k)!}\{(n-k)!\sum_{t=2}^{n-k}\dfrac{(-1)^t}{t!}\}\\
=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: 国際数学オリンピックの過去問

分野: 場合の数  レベル: 数学オリンピック