数え上げを手法の側から並べ直す｜4 つの型と使いどころ
問題集は、円順列、重複順列、組分けと、問題の見た目で並んでいます。ところが解くときに使う道具は、それよりずっと少ない。
対応をつくる、余事象で引く、すき間へ入れる、重なりで割る。この 4 つを押さえれば、初めて見る問題でも手が動きます。
見た目ではなく手法で分ける
問題の姿は無数にあります。人、玉、カード、席、経路、塗り分け。覚えようとすると際限がない。
一方で手法は限られています。どの単元でも同じ 4 つが繰り返し出てくる。
対応をつくる
数えにくい集合を、数えやすい集合に 1 対 1 で結び付ける手法です。移した先で数えれば、もとの個数も分かる。
いちばん多く使われるのは、印と仕切りへの置きかえ。 の 0 以上の整数解を、印 10 個と仕切り 2 本の並べ替えに移します。
差の条件を消す置きかえも同じ形です。 から から差が 3 以上の 4 個を選ぶ問題は、2 番目から順に余分な間隔を引いて、 から からの選び方に移します。
格子の最短経路も、右と上の文字列への置きかえでした。移した先が階乗の割り算になる。
移す前と後で個数が変わらないことを、必ず確かめます。逆向きにも戻せるかを見るのが確実。
数えにくい形を書き出す
数えやすい形へ移す規則をつくる
逆向きにも戻せることを確かめる
余事象で引く
反対側を数えて全体から引く手法です。条件に「少なくとも」「〜でない」があれば、まずこれを試します。
サイコロ 3 個で少なくとも 1 個 6 が出るのは 通り。反対の「1 個も出ない」は 1 本の式で済みます。
条件が複数重なると、引きすぎたぶんを足し戻します。これが包除原理でした。
対角線を越えない経路も、越える道を引く形。空室を作らない部屋割りも、空室のある入れ方を引く形です。
そのまま引く。余事象の出番
引きすぎを足し戻す。包除原理の出番
すき間へ入れる
離したいものを後回しにして、関係のないものを先に並べる手法です。
男子 4 人を並べてから、そのすき間 5 か所に女子 3 人を入れる。こうすると、女子が隣り合う心配がそもそも生まれません。
同じ文字を離す問題、連続しない数を選ぶ問題も同じ形。離したいものが 1 種類ならこの手が最も速い。
2 種類以上を同時に離すときは使えません。そのときは余事象へ切り替えます。
重なりで割る
同じものを何度数えたかを調べて、その回数で割る手法です。
円順列で で割り、じゅず順列でさらに 2 で割り、組分けで階乗で割り、立体の塗り分けで置き直しの数で割る。どれも同じ操作です。
割れるのは、どの場合も同じ回数だけ重なっているときだけ。整数にならなければ、その時点で使えないと分かります。
同じものを含む順列も、区別してから重なりで割る形でした。
| 手法 | 代表的な場面 | 合図になる言葉 |
|---|---|---|
| 対応をつくる | 整数解、経路、差の条件 | 置きかえられないか |
| 余事象で引く | 少なくとも、〜でない | 反対は数えやすいか |
| すき間へ入れる | 隣り合わない | 離したいものは 1 種類か |
| 重なりで割る | 円順列、組分け、塗り分け | 同じものを何度数えたか |
1 つの問題に複数を使う
実際の問題では、2 つ以上を組み合わせることが多くなります。
から から 51 個を選ぶと一方が他方を割り切る 2 数がある、という問題では、まず対応をつくって奇数部分に移し、そのあと個数を比べます。
同じものを含む順列で 2 種類を離す問題では、まず重なりで割って全体を出し、そのあと余事象で引く。
どの手法から入るかは、条件の書かれ方で決まります。
手法が外れたときの切り替え方
最初に選んだ手法で詰まったら、次の手法へ移ります。手が止まる前に切り替える。
すき間法で離したいものが 2 種類あると気づいたら、余事象へ。割り算が整数にならなければ、書き出しへ。
対応をつくろうとして逆向きに戻せないと分かったら、その対応は使えません。別の移し方を探します。
どの手法でも進まないときは、数を小さくして書き出すのが最後の手です。小さい場合の答えから規則が見えることがある。
や で全部並べれば、漸化式の形や対応の作り方が浮かぶ。手を動かすほうが速い。
5 つ目の道具としての漸化式
4 つの手法が全部外れる問題もあります。条件が前の状態に依存する場合です。
同じ記号が続かない並べ方、階段の上り方、輪になった塗り分け。どれも「直前が何か」で選択肢が変わります。
このときは最後の 1 手で場合分けして、前の答えから次を作る。漸化式は、4 つの手法とは別の入口になります。
例：手法で読み替える
いくつかの問題を、手法の側から並べ直してみます。
同じ問題が 2 つの手法で解けることもあります。両方で解いて値が合えば、それが検算になる。
例：2 通りで解いて確かめる
男子 3 人と女子 2 人を並べ、女子が隣り合わない並べ方を数えます。
すき間法なら、男子を並べて 通り、すき間 4 か所に女子 2 人で 通り。掛けて 72 通り。
余事象なら、全体 から女子が隣り合う を引いて 72 通り。
一致しました。手法を 2 つ持っていると、検算までその場で済みます。
「同じ色の玉が隣り合わないように一列に並べる」という問題で、離したい色が 1 種類だけのとき、まず試す手法はどれですか。
- 重なりで割る
- すき間へ入れる
- 対応をつくる
よくある誤り
問題を見たら、まず条件の言葉を探す。「少なくとも」「隣り合わない」「区別しない」。その語が、使う手法をほとんど決めてくれます。
参考文献
[1] が置きかえによる数え方、[2] が引いて足し戻す形、[3] がすき間を使う数え方、[4] が重なりで割る一般論、[5] が各国語での整理です。
離したいものが 1 種類なら、それ以外を先に並べてすき間へ入れるのが最短です。2 種類以上を同時に離す場合は、すき間法では処理できないので余事象へ切り替えます。