トーナメント表とシフト表を数えてみる（教科書の外の題材）

8 チームのトーナメントは、優勝が決まるまでに 7 試合。総当たりなら 28 試合です。

教科書の題材は人と玉とサイコロとカードに寄りがちですが、使う道具は変わりません。身近な場面で同じ考え方を当ててみます。

トーナメントの試合数

8 チームが勝ち抜き戦をします。全部で何試合になるか。

1 回戦が 4 試合、2 回戦が 2 試合、決勝が 1 試合。足して 7 試合です。

もっと速い数え方があります。1 試合につき 1 チームが負けて姿を消す。最後に残るのは優勝の 1 チームだけなので、負けたチームは 7 つ。

つまり試合数は $n-1$ です。チーム数がいくつでも、この 1 行で出ます。

総当たりとの違い

同じ 8 チームで総当たり戦をすると、どの 2 チームも 1 回ずつ当たります。

2 チームを選ぶ選び方なので ${}_8{\mathrm{C}}_2=28$ 試合。勝ち抜き戦の 4 倍になります。

方式が違うだけで試合数が大きく変わる。日程を組む前に、この差を出しておくと見通しが立ちます。

組み合わせ表の作り方

8 チームを 1 回戦の 4 試合に振り分けます。何通りの組み合わせ表ができるか。

まず 8 チームから 2 チームを選び、次に残り 6 から 2、その次に 4 から 2、最後に 2 から 2。

$${}_8{\mathrm{C}}_2\times {}_6{\mathrm{C}}_2\times {}_4{\mathrm{C}}_2\times {}_2{\mathrm{C}}_2=28\times 15\times 6\times 1=2520$$

ただし 4 つの試合に順序はありません。並べ替えた $4!=24$ 通りが重なります。

$$\frac{2520}{24}=105$$

105 通りです。組分けの問題とまったく同じ形になっています。

シフト表を組む

7 日間の当番を、3 人で回します。1 日に 1 人で、同じ人が 2 日続けて入らないようにする。

初日は 3 通り。2 日目以降は前の日と違う人なので 2 通りずつです^[3]。

$$3\times 2^6=192$$

192 通り。塗り分けの問題と同じ形で、日が領域、人が色にあたります。

全員が最低 1 日は入る条件

192 通りの中には、2 人だけで回している表が混ざっています。そこを引きます。

2 人だけで 7 日を回すなら、連続を避けるには交互しかありません。1 組につき 2 通り。組は ${}_3{\mathrm{C}}_2=3$ なので 6 通り。

1 人だけで回すのは、連続してしまうので 0 通りです。

$$192-6=186$$

186 通りになります^[4]。

暗証番号の強さ

4 桁の数字の暗証番号は $10^4=10000$ 通り。総当たりで試せば、すぐに開いてしまいます。

英小文字と数字を使い、4 文字にすると $36^4=1679616$ 通り。167 倍に増えます。

さらに文字数を伸ばすと、増え方が急になります。

数字だけの 8 桁が $10^8$ で 1 億通り。英小文字と数字の 6 文字は $36^6$ で約 21 億通りです。

文字数が 2 つ少なくても、文字の種類が多いほうが上回る。ただし文字数を増やすほうが、増え方としては強い。

$36^8$ は約 2.8 兆通り。2 文字増やすだけで 1000 倍以上になります。

座席を割り当てる

12 人が 4 人がけのテーブル 3 卓に分かれます。テーブルに番号があるとして、分かれ方は何通りか。

$${}_{12}{\mathrm{C}}_4\times {}_8{\mathrm{C}}_4\times {}_4{\mathrm{C}}_4=495\times 70\times 1=34650$$

34650 通り。テーブルに番号がなければ、$3!=6$ で割って 5775 通りになります。

さらに各テーブルで座る位置まで区別するなら、円順列の $3!=6$ を 3 卓ぶん掛けます。

献立を組む

主菜 5 種類、副菜 4 種類、汁物 3 種類から 1 つずつ選び、1 週間ぶんの献立を作ります。

1 日の組み合わせは $5\times 4\times 3=60$ 通り。7 日間で同じ献立を繰り返してよいなら $60^7$ 通りです。

同じ献立を 2 度出さないなら ${}_{60}{\mathrm{P}}_7$ 通り。条件の 1 語で式が変わります。

現実の条件を式に落とすとき

身近な題材では、問題文が曖昧なことがあります。数えはじめる前に、次の 3 つを自分で決めます。

決めた内容は答案に書きます。前提が違えば答えも変わるので、そこを明示しておく。

例：前提で答えが変わる

「8 チームの組み合わせ表は何通りか」という問いには、少なくとも 2 つの読み方があります。

1 回戦の組み分けだけを問うなら 105 通り。トーナメント表の位置まで区別するなら、もっと多くなる。

どちらを聞かれているかは問題文からしか分かりません。分からなければ、前提を書いて答えます。

よくある誤り

身近な題材でも、使う道具は教科書と同じです。条件を順序と重複と隣接の言葉に直せば、あとは型に当てはまります。

参考文献

^[1] が段ごとに掛ける数え方、^[2] が組合せの公式、^[3] が隣を違うものにする数え方、^[4] が引いて足し戻す形、^[5] が各国語での整理です。