数え上げにおける主客転倒
今回は、競技数学や競技プログラミングで頻出の数え上げの工夫、主客転倒について紹介していきます。 それでは、よろしくお願いします。
主客転倒とは？
主客転倒とは、数え上げの工夫のことです。具体的に言うと、「各事象がどれだけ合計に寄与、貢献しているかを考える」と言うことです。
以降の例題で十分に理解できると思いますが、動画を作成したのでもしよかったら見てみてください。
例題1
それでは、簡単な問題から主客転倒の利用例を見ていきましょう。
\((1,2, \cdots ,n)\)の並べ替え\((a_1,a_2, \cdots , a_n)\)に対して"スコア"を「\(a_i=i\)」なる\(i\)の個数（\(1 \le i \le n\)）で定める。このとき、\((a_1,a_2, \cdots , a_n)\)として有り得るもの全てについてそのスコアの総和を求めよ。
解答・解説
まずは、具体例を見てみましょう。
① \(n=3\) の場合
\[(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)\]の \(6\) 通りのスコアを計算することで \[3+1+1+0+0+1=6\] すなわちスコアの総和は \(6\) であるとわかります。
② \(n=4\) の場合
\[(1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2),(1,4,2,3),(1,4,3,2)\] \[(2,1,3,4),(2,1,4,3),(2,3,1,4),(2,3,4,1),(2,4,1,3),(2,4,3,1)\] \[(3,1,2,4),(3,1,4,2),(3,2,1,4),(3,2,4,1),(3,4,1,2),(3,4,2,1)\] \[(4,1,2,3),(4,1,3,2),(4,2,1,3),(4,2,3,1),(4,3,1,2),(4,3,2,1)\]の \(24\) 通りのスコアを計算することで \[4+2+2+1+1+2+2+0+1+0+0+1+1+0+2+1+0+0+0+1+1+2+0+0=24\] すなわちスコアの総和は \(24\) であるとわかります。
各並べ替えにおける一般式を立てて計算！といきたいところですが、残念ながら各並べ替えのスコアを一般式で表すのは難しそうです。そこで少し視点を変えて見てみましょう。
まずは手始めに「\(a_1=1\) となるケースが何通り存在するか。」を考えてみましょう。
\(a_1=1\)となるケースを数えるには、単純に \(a_1=1\) を固定して残りの並べ替えを考えれば良いですね。\(n-1\)個の数字を並べ替える方法なので \((n-1)!\) 通り存在しますね。
例：\(n=4\) の場合
\(1\) を固定すると以下の \(6\) 通りが考えられる。
\((1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2),(1,4,2,3),(1,4,3,2)\)
つまり、\(a_1=1\) がスコアに貢献する回数は \((n-1)!\) 回となります。同様に他の文字についても考えると、
\[\underbrace{(n-1)!+(n-1)!+\cdots+(n-1)!}_{n\text{個}}=n!\]
となるわけです。よって求めるスコアの総和は \(n!\) となるわけです。
\(\blacksquare\)
このように「貢献」を考えることを主客転倒と言います。とても便利な考え方です。次の例題にて、応用的な問題も考えてみましょう。
例題2
\((1,2, \cdots ,n)\) の並べ替え \((a_1,a_2, \cdots , a_n)\) に対して "スコア" を「\(a_i=i\) なる \(i\) の個数 (\(1 \le i \le n)\) 」で定める。この時、\((a_1,a_2, \cdots , a_n)\) としてあり得るもの全てについて、そのスコアの二乗の総和を求めよ。
解答・解説
まずは、具体例を見てみましょう。
① \(n=3\) の場合
\[(1,2,3)\,(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)\]
の \(6\) 通りのスコアを計算することで
\[3^2+1^2+1^2+0+0+1^2=12\]
すなわちスコアの二乗の総和は \(12\) であるとわかります。
② \(n=4\) の場合
\[(1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2),(1,4,2,3),(1,4,3,2)\]
\[(2,1,3,4),(2,1,4,3),(2,3,1,4),(2,3,4,1),(2,4,1,3),(2,4,3,1)\]
\[(3,1,2,4),(3,1,4,2),(3,2,1,4),(3,2,4,1),(3,4,1,2),(3,4,2,1)\]
\[(4,1,2,3),(4,1,3,2),(4,2,1,3),(4,2,3,1),(4,3,1,2),(4,3,2,1)\]
の \(24\) 通りのスコアを計算することで
\[4^2+2^2+2^2+1^2+1^2+2^2+2^2+0^2+1^2+0^2+0^2+1^2+1+^20+2^2+1^2+0^2+0^2+0^2+1^2+1+2^2+0^2+0^2=48\]
すなわちスコアの総和は \(48\) であるとわかります。
もちろん、各並べ替えに対して一般式を立てて計算することはできません。そこで、今回も主客転倒を使う必要があります。 ただし、二乗なのでかなりエレガントな工夫をする必要があります。 ポイントは「積→論理積」の変換です。これだけでは、全く意味が分からないと思うので、詳しく解説していきます。
まずは、軽く式を変形してみます。 使われている文字が \(i\) でも \(j\) でも言ってることは何も変わらないので (\(a_i = i\) なる \(i\) の個数) \(=\) (\(a_j = j\) なる \(j\) の個数) は当たり前に成り立ちますね。 よって、 \[(a_i = i なる i の個数)^2 = (a_i = i なる i の個数)\cdot (a_j = j なる j の個数)\] も当然成り立ちます。
ここで、\((1,2,4,3,5)\) という並び替えについて考えてみましょう。この並べ替えのスコアは \(3\) であり、その二乗は \(9\) です。 この並べ替えについて、(\(a_i = i\) なる \(i\) の個数) は \(i=1,2,5\) の \(3\) 回カウントされて、\(3\) となっています。 もちろん、(\(a_j = j\) なる \(j\) の個数) も \(j=1,2,5\) の \(3\) 回カウントされて、\(3\) となっています。 ここで、\(i,j\) をそれぞれ \(1～5\) へと増やしていって全探索的なことをしてみると、以下の \(9\) パターンで (\(a_i = i\) なる \(i\) の個数) \(\cdot\) (\(a_j = j\) なる \(j\) の個数) が増えることが分かります。
- \(i = 1\) かつ \(j = 1\)
- \(i = 1\) かつ \(j = 2\)
- \(i = 1\) かつ \(j = 5\)
- \(i = 2\) かつ \(j = 1\)
- \(i = 2\) かつ \(j = 2\)
- \(i = 2\) かつ \(j = 5\)
- \(i = 5\) かつ \(j = 1\)
- \(i = 5\) かつ \(j = 2\)
- \(i = 5\) かつ \(j = 5\)
これをよく見てみると、論理積になっていることが分かります。すなわち、(\(a_i = i)\) であり、\((a_j = j)\) であるようなケースを考えればよいのです。あとは、先ほどと同じように主客転倒を用いて数えていきましょう！
①AA型
「\(a_i=a_j=i=j\) であるケース」について考えます。これは例1そのまんまですね。\(n!\) 通りです。
②AB型
「\(a_i=i\) かつ \(a_j=j\) であり \(i \neq j\) なケース」について考えます。 これは \(a_i\) と \(a_j\) の二つを固定して主客転倒をしてあげれば良いです。\(_nC_2\cdot 2\cdot (n-2)!=n!\) 通りです。
よって、上記の二通りを足し合わせれば \(2\cdot n!\) 通りであるとわかります。\(\blacksquare\)
論理積に分解→場合分け+主客転倒 という流れになっていました。
演習問題
\((1,2, \cdots ,n)\) の並び替え \((a_1,a_2, \cdots ,a_n)\) に対して "スコア" を \(a_i=i\) なる \(i\)（\(1 \le i \le n\)）の総和で定める。このとき、\(n!\) 通り全ての並べ替えの "スコア" の総和を求めよ。
\(\)
スコアの例
\((1,2,5,3,4,6)\) と言う並べ替えの場合 "スコア" は \(1+2+6=9\) となります。
\( n \ge 2 \) とする。\( (1,2, \cdots ,n) \) の並び替え \( (a_1,a_2, \cdots ,a_n) \) に対して"スコア"を \( a_i=i, a_{i+1}=i+1 \) なる \( i \) (\( 1 \le i \le n \)) の個数で定める。 (ただし、\( n+1=1 \) とみなす。) このとき、\( n! \) 通り全ての並べ替えの"スコア"の総和を求めよ。
スコアの例
\( (1,2,5,3,4,6) \) の並べ替えの場合"スコア"は 2 です。
\(f(x)\) を \(x\) の \(200\) 以上の約数の個数とする。このとき以下の値を計算せよ。 \[f(1)+f(2)+\cdots+f(1000)\]
\(n \times n\)のマス目を白と黒の2色で塗り分ける。黒いマスと白いマスの両方に隣接している辺を"境界辺"と呼ぶ。このとき、\(2^{n^{2}}\)通り全ての塗り分けについて"境界辺"の個数の総和を求めよ。
\(N\)以下の順序付き正整数の組\((a, b, c)\)全てについて、\(max(a, b, c)\)の総和を計算したものを\(f(N)\)とおきます。このとき、\(4f(10^{2021})\)の各桁の総和を求めてください。
\(272\)項からなる数列\(\{a_i\}_{i=1,2,\cdots,272}\)の"スコア"を以下で定めます。 \[\sum_{i=1}^{256}\left|a_{i}-a_{i+16}\right|\] \(1,2,\cdots,272\)を並び替えてできる整数列は\(272!\)通り考えられますが、それらのスコアの平均値を求めてください。
Nを 99,100,101 で割った余りのうち最小のものを \( f(N) \) について、以下の総和を求めてください。 \[ f(1) + f(2) + \cdots + f(99 \times 100 \times 101) \]
\(\displaystyle 1,2,\cdots,1000\) の置換 \(a_1,a_2,\cdots,a_{1000}\) について、 \(a_i < a_{i+1}\) を満たす正整数 \(i\) の個数を \(N\) とします。 \(1000!\) 通りある全ての置換に対して \(N^2\) の(相加)平均 \(M\) を求めてください。
\(\displaystyle 1,2,\cdots,2017\) の並べ替え \(\displaystyle \sigma = (\sigma(1),\sigma(2),\cdots,\sigma(2017))\) について，\(\displaystyle \sigma(i)=i\) となる \(1 \le i \le 2017\) の個数を \(F(\sigma)\) とする。全ての並べ替え \(\displaystyle \sigma\) について \(F(\sigma)^4\) を足し合わせた値を求めよ。
さらに追加で演習したい方に向けて僕が良問だなと感じた問題のリストを下に置いておきます。 JMO2021-11に関しては、とても面白かったので別で解説を書くかもしれません。
- JJMO2018-7
- JMO2021-11
- JMO2017-6
- OMC136-F