回 4-1 分野 4 場合の数と確率
場合の数は、起こりうる場合が全部で何通りあるかを数えた数です。並べる順番を区別するのが順列で、10 個から 3 個を選んで並べると 10 × 9 × 8 = 720 通りです。順番を区別しないのが組み合わせで、720 ÷ 3! = 120 通りです。プログラミングでは、全探索で調べる通り数がこの数になり、間に合うかの見積もりに使います。
順列と組み合わせの公式を、Python で全部の並びを作って数えた数と比べて確かめます。
文 ゆめさくコード編集部公開 2026年10月30日更新 2026年10月30日出典を確かめた日 2026年10月30日
10 人から 3 人を選ぶのは何通りか
10 人から係を 3 人選ぶ選び方は 120 通りです。委員長、副委員長、書記のように役を決めて 3 人を並べるなら、720 通りになります。
この違いが、順番を区別するかどうかです。順番を区別して並べる数を順列、区別しないで選ぶだけの数を組み合わせと呼びます。どちらも、起こりうる場合を全部数えた「場合の数」です。
プログラミングでは、全部の場合を試す書き方 (全探索) の手間が、この場合の数そのものになります。この回では、公式を覚えるだけでなく、Python で全部の並びを作って数え、公式の数と合うかを確かめます。
数え方の決まり
和の法則と積の法則
場合の数の計算は、次の 2 つの決まりから始まります。
| 決まり | いつ使うか | 例 |
|---|
| 和の法則 | A か B のどちらか一方 (同時には起きない) | 電車 3 本かバス 2 本で行く行き方は 3 + 2 = 5 通り |
|---|
| 積の法則 | A のあとに B (続けて決める) | シャツ 3 枚とズボン 2 本の組は 3 × 2 = 6 通り |
|---|
ループで言えば、和の法則は 2 つのループを続けて書いたときの回数の合計、積の法則は二重ループの回数です。
樹形図と階乗
A、B、C の 3 枚を 1 列に並べる並べ方は、1 枚目が 3 通り、2 枚目が残りの 2 通り、3 枚目が 1 通りで、3 × 2 × 1 = 6 通りです。枝分かれを全部書いた図を樹形図と呼びます。
n から 1 までを全部掛けた数を n の階乗と呼び、n! と書きます。3! = 6、5! = 120、10! = 3,628,800 です。0! は 1 と決めます。「何も並べない並べ方」が 1 通りあると数えるためで、こう決めると下の公式が r = 0 や r = n でもそのまま使えます。
順列 nPr
異なる n 個から r 個を選び、順番を区別して並べる数が順列です。
nPr = n × (n − 1) × … × (n − r + 1) = n! ÷ (n − r)!
10 人から委員長、副委員長、書記を選ぶなら、10P3 = 10 × 9 × 8 = 720 通りです。
組み合わせ nCr
異なる n 個から r 個を、順番を区別せずに選ぶ数が組み合わせです。順列の 1 つの選び方には、同じ r 人の並べ替えが r! 通りずつ入っているので、順列を r! で割ります。
nCr = nPr ÷ r! = n! ÷ (r! × (n − r)!)
10C3 = 720 ÷ 6 = 120 通りです。選ぶ 3 人を決めることは、選ばない 7 人を決めることと同じなので、10C3 = 10C7 です。一般に nCr = nC(n − r) が成り立ちます。
nCr は、(a + b)^n を展開したときの係数にも出てくるので、二項係数とも呼びます。
パスカルの三角形
nCr を n = 0 から順に横に並べると、三角形になります。
| n | 並び |
|---|
| 0 | 1 |
|---|
| 1 | 1 1 |
|---|
| 2 | 1 2 1 |
|---|
| 3 | 1 3 3 1 |
|---|
| 4 | 1 4 6 4 1 |
|---|
| 5 | 1 5 10 10 5 1 |
|---|
どの数も、すぐ上の左右の 2 つの数の和です。式で書くと nCr = (n − 1)C(r − 1) + (n − 1)Cr です。「ある 1 人を選ぶ場合」と「選ばない場合」に分けて数えると、この式になります。
各段の合計は 2^n です。n 個のそれぞれを「選ぶ」か「選ばない」かの 2 通りずつ決めると、選び方の全部は 2^n 通りで、それを選んだ個数ごとに分けたのが 1 つの段だからです。
ほかの数え方
よく出る数え方は、次の通りです。
| 名前 | 何を数えるか | 式 | 例 |
|---|
| 重複順列 | 同じ物を何度使ってもよく、並べる | n^r | 0 と 1 で 8 桁の並びは 2^8 = 256 通り |
|---|
| 円順列 | 円に並べ、回して同じ物は 1 つ | (n − 1)! | 5 人が丸い机に座る座り方は 4! = 24 通り |
|---|
| じゅず順列 | 円に並べ、裏返しても同じ物は 1 つ | (n − 1)! ÷ 2 (n が 3 以上) | 5 個の玉の首飾りは 12 通り |
|---|
| 同じ物を含む順列 | 同じ文字が混ざった並べ方 | n! ÷ (p! × q! × …) | AABBB の並べ方は 5! ÷ (2! × 3!) = 10 通り |
|---|
| 重複組み合わせ | 同じ物を何度選んでもよく、選ぶだけ | (n + r − 1)Cr | 3 種類の果物から 5 個選ぶのは 7C5 = 21 通り |
|---|
格子の道で、右に 4 回、上に 3 回進む最短の道の数は、7 回のうちどこで上に行くかを選ぶ数なので 7C3 = 35 通りです。
5 人が 1 列に並ぶとき、A と B が隣り合う並べ方は、A と B を 1 組にまとめて 4 つを並べる 4! 通りに、組の中の並べ方 2 通りを掛けて 48 通りです。
360 の約数の個数は、360 = 2^3 × 3^2 × 5 と素数に分けると、2 を何個使うか (0 から 3 の 4 通り)、3 を何個 (3 通り)、5 を何個 (2 通り) の積の法則で、4 × 3 × 2 = 24 個です。
動かして確かめる
1 本目は、10 人から 3 人を選ぶ数を、公式と、全部を並べて数えた数の両方で出します。itertools は、並べ方や選び方を全部作る Python の道具です。
動かす 公式と全部並べた数を比べる
実行すると、次の通りに出ます
並べた 720 720
選んだ 120 120
720 / 3! 120
10C7 120
並べた数も選んだ数も、公式と同じです。720 を 3! = 6 で割ると 120 になり、10C3 と 10C7 も同じ数です。
2 本目は、パスカルの三角形を「上の 2 つの和」だけで作り、math.comb と各段の合計を照らします。
動かす パスカルの三角形を足し算で作る
実行すると、次の通りに出ます
0 [1] 1 True
1 [1, 1] 2 True
2 [1, 2, 1] 4 True
3 [1, 3, 3, 1] 8 True
4 [1, 4, 6, 4, 1] 16 True
5 [1, 5, 10, 10, 5, 1] 32 True
足し算だけで作った段が、どれも nCr と一致しました (右の True)。段の合計は 1、2、4、8 と 2^n で増えます。
3 本目は、ほかの数え方を全部並べて数えます。AABBB の並べ方は、並べ替えを全部作ってから、同じ並びを 1 つにまとめます。
動かす 数え方の表を全部並べて確かめる
実行すると、次の通りに出ます
重複順列 256
AABBB 10
重複組み合わせ 21 21
格子の道 35 35
表に書いた 256、10、21、35 が、全部並べた数と同じになりました。
4 本目は、全探索の手間を見積もります。数の集まりから何個かを選んで合計が目標になる選び方を、2^n 通り全部試して数えます。ビットの 1 と 0 を「選ぶ」と「選ばない」に対応させる書き方を、ビット全探索と呼びます。
動かす ビット全探索で 2^n 通り試す
実行すると、次の通りに出ます
試した 64
合計 24 [[11, 13], [7, 17]]
10 個 1024
20 個 1048576
30 個 1073741824
6 個なら 64 通りで、合計が 24 になる選び方は 2 つ見つかりました。20 個で約 100 万通り、30 個で約 10 億通りです。単純な計算が 1 秒に 1 億回ほどできると見積もると、20 個なら一瞬で、30 個なら 10 秒を超えます。書く前に通り数を出すと、全部試すか工夫するかを決められます。
数え方で外れる所
区別できるかを先に決める
赤玉 2 個と白玉 3 個を並べるとき、同じ色の玉を区別しないなら 10 通り、玉に番号を付けて区別するなら 5! = 120 通りです。確率の分母に使うときは、どの場合も同じくらい起こるように、玉を区別して数えます。区別の決め方がずれると、数は何倍もずれます。
重ねて数える
男性 4 人と女性 3 人から 3 人を選ぶとき、「少なくとも 1 人は女性」を「女性を 1 人決めてから、残りの 6 人から 2 人を選ぶ」と数えると 3 × 15 = 45 通りになります。けれど本当は 35 − 4 = 31 通りです。女性が 2 人入る組を 2 回、3 人入る組を 3 回数えているからです。全体の 7C3 = 35 から「女性が 0 人」の 4C3 = 4 を引くと、重なりなく数えられます。
動かす 少なくとも 1 人を 2 通りで数える
実行すると、次の通りに出ます
並べて数えた 31
全体から引いた 31
重ねた数え方 45
全部並べて数えるコードと照らすのが、重なりに気付く一番確かな方法です。
大きすぎる数と、小数の割り算
nCr は急に大きくなります。50C25 は約 1.26 × 10^14 で、67C33 は 64 ビットの符号付き整数に入りません。Python の整数は桁に上限が無いので計算できますが、ほかの言語では途中であふれます。競技プログラミングで「答えを 10^9 + 7 で割った余りを出せ」と言われるのは、このためです。
もう 1 つは、階乗を小数で割ることです。
動かす 小数で割ると答えがずれる
実行すると、次の通りに出ます
20 True 0
61 False -16
n = 20 では合いますが、n = 61 では小数の割り算の答えが本当の数から 16 ずれました。小数は桁数に限りがあるためです。nCr は math.comb か、整数のままの割り算 // で出します。
0 と範囲の外
r = 0 のとき nC0 = 1 (何も選ばない選び方が 1 通り) です。r が n より大きいと選べないので nCr = 0 で、Python の math.comb(3, 5) も 0 を返します。公式 n! ÷ (r! × (n − r)!) をそのまま書くと、(n − r)! が負の数の階乗になって計算できません。境目は先に分けて書きます。
仕事とコンテストでどう使うか
場合の数を使う場面は、次の通りです。
- 全探索の見積もり。2^n、n!、nCr のどれになるかを書く前に数え、間に合うかを決める。n! は 10! で約 363 万、13! で 60 億を超える
- テストの組み合わせ。3 つの値を取る設定が 4 つあれば 3^4 = 81 通り。全部は試せないときに、2 つずつの値の組を全部含む表 (ペアワイズ) で数を減らす
- 確率の分母。確率と期待値 (4-2) の計算は、全部の場合の数を数えることから始まる
- 動的計画法。パスカルの三角形の「上の 2 つの和」は、小さい答えから大きい答えを作る動的計画法の一番小さい例になる
- パスワードの強さ。英大文字と小文字と数字の 62 種類で 8 文字なら 62^8 で約 218 兆通りで、総当たりの手間を見積もれる
よくある問い
順列と組み合わせの違いは何ですか
順番を区別するかどうかです。A、B、C の 3 人から 2 人を選ぶとき、(A, B) と (B, A) を別に数えるのが順列で 6 通り、同じ 1 組と数えるのが組み合わせで 3 通りです。役や順位を決めるなら順列、班や組を作るだけなら組み合わせです。
0! が 1 なのはなぜですか
何も並べない並べ方を 1 通りと数えるためです。こう決めると、nPn = n! ÷ 0! が n! と合い、nC0 = n! ÷ (0! × n!) = 1 も成り立ちます。
nCr を手で速く計算するには
分子に n から 1 ずつ減らした数を r 個、分母に r から 1 までを並べて約分します。10C3 = (10 × 9 × 8) ÷ (3 × 2 × 1) = 120 です。r が n の半分より大きいときは、nCr = nC(n − r) で小さい方に直してから計算します。
Python で場合の数を出すには
数だけなら math.perm(n, r) と math.comb(n, r) です (Python 3.8 から)。並びそのものが要るなら itertools の permutations、combinations、product、combinations_with_replacement で全部作れます。通り数が大きいと全部はメモリに入らないので、数だけ要るときは math を使います。
確認クイズ
答えだと思う選択肢を押すと、その場で正誤と理由が開きます。3 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。
1 問目
10 種類のトッピングから 3 種類を選びます (選ぶ順番は関係ありません)。選び方は何通りですか。
2 問目
20 個の数のそれぞれを「使う」か「使わない」かで、全部の場合を試します。試す通り数に一番近いのはどれですか。
3 問目
このコードを動かすと何が出ますか。
import math
print(math.comb(5, 0),
math.comb(5, 5),
math.comb(5, 7))
説明課題
「10 人から 3 人を選ぶ組み合わせの数が、3 人を並べる順列の数を 3! で割った数になる理由」を、並べ替えの言葉を使って 3 文で説明してください。書いたら、下の模範解答を開いて比べてください。
模範解答
自分の説明を書いてから開いて、比べてください。
10 人から 3 人を選んで並べる順列は 10 × 9 × 8 = 720 通りある。そのうち、同じ 3 人の組を並べ替えただけの物が、どの組にも 3! = 6 通りずつ入っている。組み合わせは並べ替えを 1 つと数えるので、720 を 6 で割った 120 通りになる。
調べる通り数を先に数えられると、全部試す書き方で間に合うか、工夫が要るかを書く前に決められます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。
もっと深く
この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。
一次資料
どれも 2026年10月30日に開いて、題と中身を確かめました。
