数学IAの場合の数・確率問題のテクニック3選
概要
場合の数・確率の問題に関して, かなり苦手意識を持つ者が多いようだが（私も含めて）その原因の多くは, 場合の数・確率に関する問題はアドホックな解法がかなり多く, 機械的でないように思えるからだと思う. そこでこの記事では, 場合の数・確率に関する難問の解き方をいくつかに分けて, できる限り体系化していきたいと思う. この記事の内容は, 競技数学の数学コンテストに対しても十分有用な可能性がある.
前提条件
この記事を読むにあたって, 以下のことは理解しておいてほしい.
・集合に関するある程度の知識
・補集合や余事象で考えるテクニック
・順列（円, 数珠, P, 重複順列）
・組み合わせ（C, 文字重複ありのアルファベットの並び替え問題, 重複組み合わせ（よく棒で仕切るイメージで習うもの））
・確率（独立試行・反復試行・期待値・条件付確率）
A - 主客転倒（のようなもの）
A-1 項の数
$(1 + x + x ^ 2)(1 + y + y ^ 2 + y^3) $を展開したときの項の数を求めよ.
これは, 「$x$を何個使うか, $y$を何個使うか」を考えればよいので, 簡単である.
$3 * 4 = 12$ …(A)
これを利用して, 以下の問題を考えてみる.
A-2 約数の総和
45の約数の総和を求めよ.
この問題は, いったんゴリ押ししてみると以下のようになる.
＜解法＞
$ 45 = 3 ^ 2 ・ 5 ^ 2 $
45の約数の総和は,
AA : $ 3^0 ・ 5 ^ 0 +$
AB : $ 3^0 ・ 5 ^ 1 +$
AC : $ 3^0 ・ 5 ^ 2 +$
BA : $ 3^1 ・ 5 ^ 0 +$
BB : $ 3^1 ・ 5 ^ 1 +$
BC : $ 3^1 ・ 5 ^ 2 +$
CA : $ 3^2 ・ 5 ^ 0 +$
CB : $ 3^2 ・ 5 ^ 1 +$
CC : $ 3^2 ・ 5 ^ 2 $
今すべての足すべき数をタテに並べたのは, その指数を見たかったからである. また, 上から規則正しく, AA - CCの番号を振った.
ここで気づくことがあるだろう. 一文字目がA, B, Cになっているもののそれぞれ3つの$5 ^ n $の指数が, どれも$n = 0, 1, 2$と動いていることである.
ここで, 頭の中に分配法則がよぎってほしい.分配法則を用いて, この式は以下のようにまとめられる.
$3^0 (5^0 + 5^1 + 5^2) + 3^1(5^0 + 5^1 + 5^2) + 3^2(5^0 + 5^1 + 5^2) $
$=(3^0 + 3^1 + 3^2)(5^0 + 5^1 + 5^2)$
ここまでくると, あとはこれを計算するだけである. (簡単な計算処理によって求まるので, 解答は省略する）
この問題は, 実は項の数を求める問題の逆から考えることで解答することが可能であったのである.
このように, 数を足す順番を変えて数え上げを楽にするテクニックを, 主客転倒という. (厳密には若干定義が違う。あと公式じゃない)
では, ここで簡単な問題をもう一問解いておこう.
九九表に描かれる数の総和を求めてください.
$1×1, 1×2$... から, $9×9 $までの総和のことです.
この問題もとりあえずごり押してみる.
$ 1 × 1 + 1 × 2 + 1 × 3 ... +1×9 $
$ 2 × 1 + 2 × 2 + 2 × 3 ... +2×9 $
$ 2 × 1 + 2 × 2 + 2 × 3 ... +3×9 $
（中略）
$ 9 × 1 + 9 × 2 + 9 × 3 ... +9×9 $
となる.これも, 例えば$1 × n$の部分に関して（常に）$n = 1, 2, 3, ... 9$となっているので,
以下のように分配法則が用いれる.
$ 1 × (1 + 2 + 3 ... 9) +$
$ 2 × (1 + 2 + 3 ... 9) +$
$ 3 × (1 + 2 + 3 ... 9) +$
（中略）
$ 9 × (1 + 2 + 3 ... 9)$
ここから, まだ分配法則を用いることが可能である.
$ (1 + 2 + 3 ... 9) × (1 + 2 + 3 ... 9)$
$= 45 × 45 = 2025$ …(A)
練習問題です. 若干むずめ.
$ f(x) $を$x$の$100$以上の約数の個数とする.このとき以下の値を求めよ.
$f(1) + f(2) + f(3) + ... f(1000) $
B - えふ式さいころ問題ぶっ殺しテク
6面さいころを$n$回振るとき, その積が6の倍数となる確率を求めよ.
実は, 「さいころの積」と言われた瞬間やることがほぼ決まっている. 以下の解き方を見てほしい.
求める確率は,
1 - (積が6の倍数とならない確率)
である.（余事象の利用）
そこで, 以下のように事象を分ける.A = {2, 4}, B = {3}, C = {6}, D = {1, 5} （さいころを振ったとき, これらが出るということ）
それぞれの事象が起こる確率は,
A = $\frac{1}{3}$ , B = $\frac{1}{6}$, C = $\frac{1}{6}$, D = $\frac{1}{6}$
※ここでは, $ 6 = 2 * 3 $より, 「その数の中に2と3をどのように含むか」という観点で集合に分けた.
Aは2の倍数（3の倍数ではない）
Bは3の倍数（2の倍数ではない）
Cは2の倍数かつ3の倍数（つまり6の倍数）
Dはそれ以外
としてグループ分けしている.
この中で, 6の倍数にならないパターンは,
・Aがk回とDがn - k回出る. …①
・Bがk回とDがn - k回出る. …②
・Dがn回出る. …③の3つなので, ①と②の中に③が含まれることに注意すると,
（6の倍数にならない確率）= (①の確率)＋(②の確率) - (③の確率)
である.
これらは反復試行及び独立試行の計算によって求まる.
中略計算
① 「AとDだけで構成される」確率
$n$ 回すべてにおいて, A または D の目が出る（つまり $A \cup D = \{1, 2, 4, 5\}$ の4つの目が出る）確率に等しくなる.
$$ \left( \frac{1}{3} + \frac{1}{3} \right)^n = \left( \frac{2}{3} \right)^n $$
② 「BとDだけで構成される」確率
$n$ 回すべてにおいて、B または D の目が出る（つまり $B \cup D = \{1, 3, 5\}$ の3つの目が出る）確率に等しくなる.
$$ \left( \frac{1}{6} + \frac{1}{3} \right)^n = \left( \frac{1}{2} \right)^n $$
>③ 「Dだけで構成される」確率
$n$ 回すべてにおいて、D（$\{1, 5\}$ の2つの目）だけが出る確率.
$$ \left( \frac{1}{3} \right)^n $$
①と②の足し算から, 重複して数えている③を引き算する.
$$ (\text{6の倍数にならない確率}) = \left( \frac{2}{3} \right)^n + \left( \frac{1}{2} \right)^n - \left( \frac{1}{3} \right)^n $$
したがって, 求める確率は以下のようになる.
$$ 1 - \left( \frac{2}{3} \right)^n - \left( \frac{1}{2} \right)^n + \left( \frac{1}{3} \right)^n ・・・(A)$$
この考え方は, 一部のさいころの和の問題を考えるのにも有効である.
7個の7面サイコロ（1から7が同様に確からしく出るさいころ）を振る時, 出た目の和が2の倍数になる確率を求めよ.
まずは有名事実.
6面さいころを$n$回振ったとき, その和が2の倍数となる確率は, $\frac{1}{2}$である.
理由は, $n - 1$回さいころを振ったときにその和が偶数でも奇数でも, 次が偶数になる確率は2分の1だから.
同じような理論で, 以下も言える.
6面さいころを$n$回振ったとき, その和が3の倍数となる確率は, $\frac{1}{3}$である.
6面さいころを$n$回振ったとき, その和が6の倍数となる確率は, $\frac{1}{6}$である.
このような対称性を用いた解法は, simasima special と言われ, 特に競技数学においてはよく使われます. 詳しくは以下の記事で.（この問題についても解説されています）
https://mathlog.info/articles/nNX6dXUeyb35vYurGP5l
では, この問題を解いていく. 方針は, うまくグループ分けをして公式2に帰着させることである.
なのでグループ分けで強引に6面サイコロを作り出す.
A = {1, 2, 3, 4, 5, 6}, B = {7}とする.
[実験]出た目の組を目が属する集合で変換してみる.
変換
$(1, 2, 4, 7, 1, 7, 3) ⇒ (A, A, A, B, A, B, A) $
$(1, 3, 7, 7, 1, 7, 6) ⇒ (A, A, B, B, A, B, A) $
$(7, 7, 7, 7, 7, 7, 7) ⇒ (B, B, B, B, B, B, B)$
ここで, 例えば出た目の組が{$A, A, A, A, A, B, B$}になるとき, 出目が2の倍数となる確率を考えてみる.
足し算の順序は自由に変えても構わないので, 最後に足すさいころの目をAのもののうちのどれかにして考えてみると, なんとここで対称性が使えるっ！（他の6個のさいころの目の和が偶数でも奇数でも, 7つ目で2の倍数になる確率は $\frac{1}{2}$）
よって, 特別に考えなければならないのは, 出た目の組が{$B, B, B, B, B, B, B$}になるときのことである.
このとき, 面の和は 7 * 7 = 49より, 2の倍数にならない.
よって, この問題の答えは,
$(すべての出目が集合Bである確率) * 0 +（そうでない確率）* \frac{1}{2} $
計算
$A = \{1, 2, 3, 4, 5, 6\}$ が出る確率 $ = \frac{6}{7}$
$B = \{7\}$ が出る確率 $ = \frac{1}{7}$
である.
ここで、「すべての出目が集合Bである（＝7個すべてで『7』が出る）」という特殊なパターンの確率は,
$$ \left( \frac{1}{7} \right)^7 = \frac{1}{7^7} $$
となる.
一方で,「そうでない確率（＝少なくとも1回はAの目が出る確率）」は、余事象を考えて,
$$ 1 - \left( \frac{1}{7} \right)^7 = 1 - \frac{1}{7^7} $$
と求まる.
あとは, 最初に立てた方針の式にこれらを代入する.
$$ (\text{すべての出目が集合Bである確率}) \times 0 + (\text{そうでない確率}) \times \frac{1}{2} $$
$$ = \frac{1}{7^7} \times 0 + \left( 1 - \frac{1}{7^7} \right) \times \frac{1}{2} $$
$$ = \frac{1}{2} \left( 1 - \frac{1}{7^7} \right) $$
$$ = \frac{1}{2} - \frac{1}{2 \cdot 7^7} ・・・(A) $$
どうだっただろうか. この集合分けのテクニックにより, さいころの確率の難しい問題は, 体感ほぼすべて解くことができると思う. 以下は2問ほどの演習問題である.
6面サイコロを3個振ったとき, 出目の積が8になる確率を求めよ.
ほぼ答え
A = {2, 6}, B = {4}, C = {1, 3, 5}
としてみれば解ける.
Bを単独で分けた理由は, $2^2$だから, 他より2の倍数としての貢献度が高い.
答え by gemini
グループの整理と確率
出目の積が $8 = 2^3$ になるということは、3個のさいころに含まれる素因数2の個数の合計がちょうど3個になるということです。
各目の「素因数2の個数」でグループ分けしてみましょう。
A = $\{2, 6\}$ ： 素因数2を 1個 含むグループ（確率は $\frac{2}{6} = \frac{1}{3}$）
B = $\{4\}$ ： 素因数2を 2個 含むグループ（確率は $\frac{1}{6}$）
C = $\{1, 3, 5\}$ ： 素因数2を 0個 含むグループ（確率は $\frac{3}{6} = \frac{1}{2}$）
積が8になる（素因数2が計3個）パターンの列挙
3個のさいころの組み合わせで、素因数2の合計が3個になるパターンは以下の3通りしかありません。
パターン①：【A, A, A】（1個 ＋ 1個 ＋ 1個 ＝ 3個）
3個ともAのグループから出る場合です。
$$ \left( \frac{1}{3} \right)^3 = \frac{1}{27} $$
パターン②：【A, B, C】（1個 ＋ 2個 ＋ 0個 ＝ 3個）
A, B, Cから1個ずつ出る場合です。さいころ3個の並び替え（$3! = 6$ 通り）を考慮します。
$$ 3! \times \left( \frac{1}{3} \times \frac{1}{6} \times \frac{1}{2} \right) = 6 \times \frac{1}{36} = \frac{1}{6} $$
パターン③：【B, C, C】（2個 ＋ 0個 ＋ 0個 ＝ 3個）
Bから1個、Cから2個出る場合です。Bがどのさいころかで $\frac{3!}{2!} = 3$ 通りあります。
$$ 3 \times \left( \frac{1}{6} \times \frac{1}{2} \times \frac{1}{2} \right) = 3 \times \frac{1}{24} = \frac{1}{8} $$
最終的な計算
これら3つのパターンは同時に起こらない（互いに排反である）ため、すべて足し合わせることで求める確率になります。
$$ \frac{1}{27} + \frac{1}{6} + \frac{1}{8} $$
通分するために、分母の最小公倍数である $216$ に揃えます。
$$ = \frac{8}{216} + \frac{36}{216} + \frac{27}{216} $$
$$ = \frac{71}{216} $$
答え： $\frac{71}{216}$
6面サイコロを$n$個振ったとき, 出目の積が平方数になる確率を求めよ.
（"OMCの技 simasima special 解説 (前編)" より引用）
かなり難しい問題. （これも上のリンクの記事で紹介されている）
素因数の偶奇に干渉するものを探していこう.
ちなみに漸化式でも解けるけど今回は封印で.
ほぼ答え&答え（リンク先）
6面サイコロの出目を二つの集合に分ける.
A = {1, 2, 3, 6}, B = {4, 5}
Aに含まれる出目はの2, 3の素因数の数の偶奇にのみ干渉し, Bに含まれる出目はの5の素因数の数の偶奇にのみ干渉する.
あとは, すべての素因数の数が偶数になることに注意して計算する.
続きは以下で,
https://mathlog.info/articles/nNX6dXUeyb35vYurGP5l
C - 動的計画法
みんな大好き動的計画法.
1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする．15段の階段を昇る昇り方は何通りあるか．
（2007 京都大学）
例のあれ. みんな大好き京都大学から.の前に, 以下の問題を考えてみる.
1歩で1段または2段のいずれかで階段を昇るとき，15段の階段を昇る昇り方は何通りあるか．
若干きもい解き方する.
$i$段目まで上るときの場合の数を, $dp[i]$とする.
すると.
$dp[i] = dp[i - 1] + dp[i - 2] (i > 2)$
が成り立つ.（一段前と二段前から上るのの足し合わせ）
$dp[1] = 1, dp[2] = 2$より（考えたらわかる）, 頑張ったら求まる.
このように, $i$番目の式を, すでに求めた$i - 1$番目とかを使って表して解いていくやり方を, 動的計画法(Dynamic Programming)という.
詳しくは以下
https://tars0x9752.com/posts/dp-nyuumon
※動的計画法は, 主にプログラミングの文脈で使われることが多く, 例えばサイゼリヤで1000円払って得られる最大カロリーを考えるときとかに使う.（こういう問題をナップザック問題という）日本情報オリンピックなどの競技プログラミング大会では頻出なので（がちで）覚えておくとよい.
んで, 最初の問題に戻る.
1歩で2段昇ることは連続しないということは, 2段上ったら, 次1段上るのは確定.
つまり, これを3段上る1セットとして考えればいい（dp[2]を求める影響から, 1段⇒2段の順で）.
なので, さっきみたいにdpの式で表すと,
$i$段目まで上るときの場合の数を, $dp[i]$とする.
すると.
$dp[i] = dp[i - 1] + dp[i - 3] (i > 3)$
が成り立つ.（1段前と3段前から上るのの足し合わせ）
$dp[1] = 1, dp[2] = 2, dp[3] = 3$より（考えたらわかる）, 頑張ったら求まる.
答え by gemini
計算の準備として、初期値をもう一度整理しておきます。
$dp[1] = 1$ （「1」の1通り）
$dp[2] = 2$ （「1→1」「2」の2通り）
$dp[3] = 3$ （「1→1→1」「1→2」「2→1」の3通り。※「2→2」は連続するのでNG）
あとは、この3つの数字をもとに、「1つ前の数」と「3つ前の数」を足すというルール（ $dp[i] = dp[i-1] + dp[i-3]$ ）を繰り返すだけです。
DPテーブルの計算
順番に足し算をしていきましょう。
$dp[4]$ $= dp[3] + dp[1] = 3 + 1 = \mathbf{4}$
$dp[5]$ $= dp[4] + dp[2] = 4 + 2 = \mathbf{6}$
$dp[6]$ $= dp[5] + dp[3] = 6 + 3 = \mathbf{9}$
$dp[7]$ $= dp[6] + dp[4] = 9 + 4 = \mathbf{13}$
$dp[8]$ $= dp[7] + dp[5] = 13 + 6 = \mathbf{19}$
$dp[9]$ $= dp[8] + dp[6] = 19 + 9 = \mathbf{28}$
$dp[10]$ $= dp[9] + dp[7] = 28 + 13 = \mathbf{41}$
$dp[11]$ $= dp[10] + dp[8] = 41 + 19 = \mathbf{60}$
$dp[12]$ $= dp[11] + dp[9] = 60 + 28 = \mathbf{88}$
$dp[13]$ $= dp[12] + dp[10] = 88 + 41 = \mathbf{129}$
$dp[14]$ $= dp[13] + dp[11] = 129 + 60 = \mathbf{189}$
$dp[15]$ $= dp[14] + dp[12] = 189 + 88 = \mathbf{277}$
最終的な解答
$$ dp[15] = 277 $$
よって、15段の階段を昇る昇り方は 277通り である。
手計算でも1分足らずで安全に完答できる、まさに動的計画法（DP）の強力さがよく分かる名作問題です。
一回の移動で, x軸, y軸, z軸のいずれかに1移動する.原点から(11, 45, 14)への最短経路は何通りあるか.
この動的計画法のことを漸化式って言わなかった理由がこれ. 多変数関数的なのにも対応している.（というかそれが本命まである）
$(x,y,z)$まで行くときの場合の数を, $dp[x][y][z]$とする.
すると.
$dp[x][y][z] = dp[x - 1][y][z] + dp[x][y - 1][z] + dp[x][y][z - 1] (x, y, z > 0)$
が成り立つ.
$dp[0][0][0] = 1$より, 頑張ったら求まる.
dpはなんか計算がめっちゃめんどい気がするが, 刺さるときには刺さるので覚えておけるとつよい.
中3の超むずいテストで98点取れたのはDPのおかげまである.
数オリの問題も何問かDPで沈めたし.
特に競プロは出てこない日がほぼないまであるくらい大事.
以下が練習問題
リンク先の問題（編集気力の喪失...）
割と有名問題.
https://onlinemathcontest.com/contests/omc021/tasks/132
D - 飛び道具の紹介
説明がめっちゃだるいのと多分難しすぎるため扱わなかった発展的なトピックたち.
写像12相
場合の数の有名問題寄せ集めみたいなもの.（スターリング数とか。ブログの番号がヤクザ...）
https://manabitimes.jp/math/893
グラフ理論の基礎
「ご注文は数オリですか？（通称ごちすう）」の記事は, めちゃくちゃ教育的でどれもおすすめ.（どこの競技〇〇行っても激つよPlayerの中にRabbit Houseさんとか, ごちうさ民いる気がする. なんで理系人気謎に高いんだあの漫画...）
https://gochisuu.netlify.app/topics/graph-intro/
ポリアの数え上げ定理
個人的には数え上げが楽になるらしいがそれよりも理解に苦しむ.
多分理解するには上の「グラフ理論の基礎」を読む必要がある.
https://atcoder.jp/contests/abc284/editorial/5481?lang=ja
この記事を高評価した人
この記事に送られたバッジ
投稿者
