数学A / 場合の数

場合の数実戦編の問題全8問

難関大の総合問題。複数の単元を融合した単元横断の演習

難易度: ★ 基礎·★★ 標準·★★★ 応用·★★★★ 難関·実戦編·最難関編

対角線を越えない最短経路(カタラン数と反射原理)
2×n をタイルで敷き詰める(フィボナッチ数)
3つの箱に空なしで入れる(全射と包除原理)
斜めの和の公式(組合せの意味で示す)
オイラー関数の和(約数で分類する)
符号つき二項和(全射の数え上げ)
円環をk色で塗り分ける(数え上げと漸化式)
グループ分けの総数(ベル数の漸化式)

問1対角線を越えない最短経路(カタラン数と反射原理)

実戦編数え上げ最短経路二項係数反射原理単元横断

問題

格子を右または上へ1歩ずつ進んで $(0, 0)$ から $(n, n)$ へ行く最短経路のうち、つねに $y \leq x$ (対角線 $y = x$ を上に越えない)ものの総数を求めよ。

ヒントを見る

全経路から「ダメな経路(対角線を越える= $y = x + 1$ に触れる)」を引く。触れた後を対角線で折り返す反射で、ダメな経路が別の端点への全経路と1対1に対応する。

解答・解説

方針

全経路は $(n 2 n)$ 。 $y \leq x$ を破る経路(直線 $y = x + 1$ に触れる)を、最初に触れた後を対称移動する反射原理で $(- 1, 1)$ → $(n, n)$ の経路 $(n - 1 2 n)$ と1対1対応させ、引く。

解答

⓪ 発想(どう考え始めるか) 「越えない経路」を直接数えるのは難しい。全体から悪い経路を引く方針に切り替える。

全経路は右 $n$ 歩・上 $n$ 歩の並べ方で $(n 2 n)$ 。悪い経路(直線 $y = x + 1$ に触れる)を数えるのがいちばん大事なところだ。

決め手は反射原理だ: 悪い経路を「最初に $y = x + 1$ に触れた後の部分を、その直線について折り返す」と、 $(- 1, 1)$ から $(n, n)$ への経路と1対1に対応する。折り返しで、数えにくいものが数えやすいものに置き換わる。

定理反射原理:直線

ℓ

に触れる経路は、初めて触れた後を

ℓ

で折り返すと、始点を

ℓ

で対称移動した点からの経路と1対1に対応する

① 全経路。 $(0, 0) \to (n, n)$ の最短経路は右 $n$ 回・上 $n$ 回の並べ方で $(n 2 n)$ 通り。

例(n=3): 対角線 y=x(破線)を上に越えず (0,0) から (3,3) へ行く経路の一例。総数はカタラン数 C₃=5。

② 越える経路を反射で数える。 $y \leq x$ を破る経路は直線 $y = x + 1$ に触れる。初めて触れた点以降を $y = x + 1$ で折り返すと、始点 $(0, 0)$ の鏡像 $(- 1, 1)$ から $(n, n)$ への経路になる。これは右 $n - (- 1) = n + 1$ 回・上 $n - 1$ 回の並べ方で $(n - 1 2 n)$ 通り。逆にたどれるので1対1対応、越える経路はちょうど $(n - 1 2 n)$ 通り。

③ 引く。 よって越えない経路は $(n 2 n) - (n - 1 2 n) = (n 2 n) (1 - \frac{n}{n + 1}) = \frac{1}{n + 1} (n 2 n) .$ これがカタラン数 $C_{n} = \frac{1}{n + 1} (n 2 n)$ 。

まとめ 「対角線を越えない経路」は、全経路 $(n 2 n)$ から越える経路を反射原理で $(n - 1 2 n)$ と数えて引く。差はカタラン数 $\frac{1}{n + 1} (n 2 n)$ 。数え上げ・最短経路・二項係数(反射)の融合。 $n = 3$ なら $C_{3} = 5$ 。

発展。 カタラン数 $1, 2, 5, 14, 42, \dots$ は、対になった括弧の列( $n$ 組)、凸多角形の三角形分割、二分木の形など、見た目のまったく違う問題に繰り返し現れる。どれも本問の経路と1対1対応が作れる。また票数の一般形(A が $a$ 票、B が $b$ 票、 $a > b$ 、開票中つねに A が優勢である確率 $= \frac{a - b}{a + b}$ )は「投票の問題」と呼ばれ、反射原理がそのまま働く。

答

全経路 $(n 2 n)$ から、対角線を越える「悪い経路」を反射原理で $(n - 1 2 n)$ と数え、差 $(n 2 n) - (n - 1 2 n) = \frac{1}{n + 1} (n 2 n)$ (カタラン数)。

別解

「最初に対角線へ戻る場所」で分解する(カタラン数の再帰構造)。 反射原理とは別の見方として、良い経路を最初に $y = x$ に戻る点で切る見方がある。

良い経路が最初に対角線に戻るのが $(k + 1, k + 1)$ だとすると、経路は「最初の右1歩+内側で対角線に触れない長さ $2 k$ の部分+上1歩」と「残りの長さ $2 (n - k - 1)$ の良い経路」に割れる。個数を $C_{n}$ と書くと

$C_{n + 1} = k = 0 \sum n C_{k} C_{n - k}$

という再帰の分解が出る( $C_{0} = 1$ )。実際 $1, 1, 2, 5, 14, 42, \dots$ がこの式で次々に生成される。

反射原理(本解)は閉じた式 $\frac{1}{n + 1} (n 2 n)$ への最短路で、再帰分解は「カタラン数が括弧の対応・二分木・多角形の三角形分割にも現れる」理由を説明する道だ。同じ数列を2つの方向から見ている。

ポイント

全経路 $(n 2 n)$ から越える経路を引く(余事象)。
越える経路は反射原理で $(- 1, 1) \to (n, n)$ の経路 $(n - 1 2 n)$ と1対1。
差はカタラン数 $\frac{1}{n + 1} (n 2 n)$ 。

よくある間違い

反射の対応先を $(1, - 1)$ からの経路と取り違える(直線 $y = x + 1$ に関する $(0, 0)$ の対称点は $(- 1, 1)$ )。
「触れたら悪い」の基準線を $y = x$ と混同する( $y \leq x$ は $y = x$ に触れてよい。破るのは $y = x + 1$ に達したとき)。
反射が1対1対応であること(悪い経路のどれもが対応し、逆向きも作れる)の説明を落とす。

問22×n をタイルで敷き詰める(フィボナッチ数)

実戦編数え上げ漸化式フィボナッチタイル張り単元横断

問題

$2 \times n$ のマス目を $1 \times 2$ のタイル(縦でも横でもよい)で隙間も重なりもなく敷き詰める方法の総数 $a_{n}$ を求めよ。

ヒントを見る

左端をどう埋めるかで場合分け。縦タイル1枚なら残りは $2 \times (n - 1)$ 、横タイル2枚(上下)なら残りは $2 \times (n - 2)$ 。 $a_{n}$ の漸化式は?

解答・解説

方針

一番左の列に注目。縦タイル1枚で埋めると残りは $2 \times (n - 1)$ 、横タイル2枚で埋めると残りは $2 \times (n - 2)$ 。これで漸化式が立つ。

解答

⓪ 発想(どう考え始めるか) 敷き詰めの総数は、端がどう埋まるかで場合分けすると漸化式が立つ。

一番左の列の埋まり方は2通りしかない: 縦タイル1枚(残りは $2 \times (n - 1)$ )か、横タイル2枚を上下に重ねる(残りは $2 \times (n - 2)$ )。よって $a_{n} = a_{n - 1} + a_{n - 2}$ となる。フィボナッチの漸化式だ。 $a_{1} = 1, a_{2} = 2$ から $a_{n} = F_{n + 1}$ 。

① 漸化式を立てる。 左端の埋め方で $a_{n} = 縦 1 枚 a_{n - 1} + 横 2 枚 a_{n - 2} .$

2×4 の敷き詰めの一例(縦1枚・横2枚・横2枚・縦1枚の順)。左端の埋め方で a_n=a_{n-1}+a_{n-2} が立つ。

② 初期値。 $a_{1} = 1$ ( $2 \times 1$ は縦タイル1枚のみ)、 $a_{2} = 2$ ( $2 \times 2$ は縦2枚または横2枚)。

重要

a_{n} = a_{n - 1} + a_{n - 2}

、

a_{1} = 1, a_{2} = 2

はフィボナッチ数列

1, 2, 3, 5, 8, \dots

で、

a_{n} = F_{n + 1}

(

F_{1} = F_{2} = 1

)

③ 結論。 よって $a_{n} = F_{n + 1}$ 。たとえば $a_{3} = 3, a_{4} = 5, a_{5} = 8$ 。

まとめ 「左端の埋め方」で場合分けすると、 $2 \times n$ の敷き詰めは $2 \times (n - 1)$ と $2 \times (n - 2)$ に帰着し、 $a_{n} = a_{n - 1} + a_{n - 2}$ 。フィボナッチ数 $F_{n + 1}$ が現れる。数え上げと漸化式の融合。

発展。 盤を $3 \times n$ に広げると、答えは漸化式 $b_{n} = 4 b_{n - 2} - b_{n - 4}$ (奇数 $n$ では 0)という別の形になり、 $2 \times n$ のフィボナッチがいかに特別に単純かが分かる。「端の埋まり方で分類 → 漸化式」という手順自体は、盤が変わっても通用する。状態(端の欠け方)を増やして追いかければよく、これは動的計画法の基本になる。

答

左端の詰め方で場合分けすると $a_{n} = a_{n - 1} + a_{n - 2}$ 、 $a_{1} = 1, a_{2} = 2$ 。よって $a_{n} = F_{n + 1}$ (フィボナッチ数)。

別解

「1段・2段の階段登り」と同一視する(対応で言い換える)。 敷き詰めを左から読むと、各位置で「縦1枚( $1$ 列消費)」か「横2枚( $2$ 列消費)」のどちらかを選んでいる。

つまり敷き詰めは、 $n$ を $1$ と $2$ の順序つきの和に分解する方法(合成)と1対1対応する:

$n = 4 : 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2 ⟶ 5 通り$

これは「1段か2段ずつで $n$ 段の階段を登る方法」とまったく同じ問題なので、答えが同じフィボナッチ数になるのは当然だった。

漸化式(本解)は答えを計算する方法で、対応づけは「見た目の違う問題が同じ構造だ」と見抜く見方である。数え上げでは、知っている問題への1対1対応が最も有効な解法になることが多い。

ポイント

一番左の列の埋め方(縦1枚 / 横2枚)で場合分け。
残りが $2 \times (n - 1)$ と $2 \times (n - 2)$ になり $a_{n} = a_{n - 1} + a_{n - 2}$ 。
$a_{1} = 1, a_{2} = 2$ よりフィボナッチ数 $a_{n} = F_{n + 1}$ 。

よくある間違い

左端の場合分けで「横タイル1枚だけ」の埋め方を数える(横1枚では上下どちらかが欠ける。横は必ず2枚セット)。
初期値を $a_{1} = 1, a_{2} = 2$ でなく $a_{0}$ の扱いで混乱する( $a_{0} = 1$ (何も置かない1通り)とすれば漸化式と整合)。
フィボナッチとの対応の添字( $a_{n} = F_{n + 1}$ )を1つずらす。

問33つの箱に空なしで入れる(全射と包除原理)

実戦編数え上げ包除原理全射写像単元横断

問題

$n$ 個の異なる玉を、区別できる $3$ つの箱にどの箱も空にならないように入れる方法の総数を求めよ( $n \geq 3$ )。

ヒントを見る

全部で $3^{n}$ 通り。「どれかの箱が空」を引く。1つの箱を空にする=残り2箱に入れるで $2^{n}$ 、2つ空は $1^{n}$ 。包除で足し引き。

解答・解説

方針

条件なしの入れ方 $3^{n}$ から、少なくとも1つの箱が空になる場合を包除原理で引く。「箱 $A$ が空」は残り2箱に入れる $2^{n}$ 通り。

解答

⓪ 発想(どう考え始めるか) 「どの箱も空でない」は直接数えにくい。条件なしから、空の箱がある場合を引く。ここで包除原理を使う。

条件なしは各玉に3択で $3^{n}$ 。「箱 $A$ が空」は残り2箱に入れて $2^{n}$ 通りで、これが3つの箱ぶんある。だが「 $A$ も $B$ も空」(残り1箱、 $1^{n}$ 通り)を2回引いているので、3つぶん足し戻す: $3^{n} - 3 \cdot 2^{n} + 3 \cdot 1^{n}$ 。

定理包除原理

∣ A \cup B \cup C ∣ = \sum ∣ A ∣ - \sum ∣ A \cap B ∣ + ∣ A \cap B \cap C ∣

① 全体と「空」の場合。 全部の入れ方は $3^{n}$ 。箱を $1, 2, 3$ とし、 $X_{i} =$ 「箱 $i$ が空」の入れ方。 $∣ X_{i} ∣ = 2^{n}$ (残り2箱に入れる)。 $∣ X_{i} \cap X_{j} ∣ = 1^{n} = 1$ (残り1箱に全部)。 $∣ X_{1} \cap X_{2} \cap X_{3} ∣ = 0$ (どこにも入れられない、 $n \geq 1$ )。

② 包除で「空あり」を数える。 $∣ X_{1} \cup X_{2} \cup X_{3} ∣ = 3 \cdot 2^{n} - 3 \cdot 1 + 0 = 3 \cdot 2^{n} - 3.$ ③ 余事象で答え。 空の箱がない入れ方は $3^{n} - (3 \cdot 2^{n} - 3) = 3^{n} - 3 \cdot 2^{n} + 3.$

まとめ 「どの箱も空でない」= 全体 $3^{n}$ から「空の箱がある」を包除で引く。 $3^{n} - 3 \cdot 2^{n} + 3$ 。これは $n$ 個の玉から $3$ 箱への全射の数でもある。数え上げ・包除・写像の融合。 $n = 3$ なら $27 - 24 + 3 = 6 = 3!$ 。

発展。 箱を $m$ 個に増やすと、全射の数は $\sum_{k = 0}^{m} (- 1)^{k} (k m) (m - k)^{n}$ で、それを $m!$ で割るとスターリング数 $S (n, m)$ になる。「ラベルあり $\div m! =$ ラベルなし」の関係はそのまま拡張される。さらに全部の $m$ について $S (n, m)$ を足すとベル数(この単元の最終問題)になる。数え上げの部品が1本の系譜でつながっている。

答

全部の入れ方 $3^{n}$ から「ある箱が空」を包除で除く。 $3^{n} - 3 \cdot 2^{n} + 3 \cdot 1^{n} = 3^{n} - 3 \cdot 2^{n} + 3$ 。

別解

分割してからラベルを貼る(2段階の構成)。 順序を変えて、先に中身のグループ分け、後から箱の名前を付ける。

$n$ 個の玉を「区別のない3つの非空グループ」に分ける方法の数を $S$ とする(スターリング数と呼ばれる)。グループが決まれば、3つの箱への割り当ては $3! = 6$ 通り。よって求める数は $6 S$ 。

逆に本解の包除の結果から $S = \frac{3 ^{n} - 3 \cdot 2 ^{n} + 3}{6}$ が読める。たとえば $n = 4$ : 全射は $81 - 48 + 3 = 36$ 通りで、 $S = 6$ となり、4人を3グループに分ける6通り( ${2, 1, 1}$ 型の $(2 4) = 6$ )と一致する。

「ラベルあり(全射) $=$ ラベルなし(分割) $\times 3!$ 」という2段階の分解は、この後のグループ分け(ベル数)の問題と地続きで、区別の有無で数がどう変わるかの感覚を鍛えてくれる。

ポイント

全体 $3^{n}$ から「空の箱がある」を余事象で引く。
「箱 $i$ が空」 $= 2^{n}$ 、「2箱空」 $= 1$ を包除で足し引き。
答えは $3^{n} - 3 \cdot 2^{n} + 3$ (3箱への全射の数)。

よくある間違い

包除の足し戻しを忘れて $3^{n} - 3 \cdot 2^{n}$ で止める(2箱空の場合を2回引いている)。
「3箱とも空」の項( $0^{n} = 0$ )を形式的に書かず、包除の項数が合っているか不安になる( $n \geq 1$ なら0なので結果は同じ)。
玉が区別できる(異なる)という前提を見落とし、重複組合せ( $(2 n - 1)$ 型)で数え始める。

問4斜めの和の公式(組合せの意味で示す)

実戦編数え上げ二項係数組合せ論法パスカルの三角形単元横断

問題

$0 \leq r \leq n$ とする。 $k = r \sum n (r k) = (r + 1 n + 1)$ を、組合せの意味(何を選ぶか)から説明して示せ。

ヒントを見る

右辺は $n + 1$ 個( $0$ 〜 $n$ )から $r + 1$ 個選ぶ数。選んだ数のうち「最大のもの」で分類すると、各場合が $(r k)$ の形になる。

解答・解説

方針

右辺 $(r + 1 n + 1)$ は ${0, 1, \dots, n}$ ( $n + 1$ 個)から $r + 1$ 個選ぶ数。選んだ最大の数で場合分けすると左辺の和になる。

解答

⓪ 発想(どう考え始めるか) 「組合せの意味から示せ」とあるので、両辺が同じものを2通りに数えていることを見つける。

右辺 $(r + 1 n + 1)$ は、 ${0, 1, \dots, n}$ ( $n + 1$ 個)から $r + 1$ 個選ぶ数。これを「選んだ中の最大の数 $k$ 」で分類する。最大が $k$ なら、残り $r$ 個は $0, \dots, k - 1$ から選ぶので $(r k)$ 通り。 $k = r, \dots, n$ を足せば左辺になる。分類の軸(最大値)を自分で決めるところが、この型の難しいところだ。

① 右辺の意味。 $(r + 1 n + 1)$ は ${0, 1, \dots, n}$ から $r + 1$ 個を選ぶ方法の数。

② 最大の数で分類する。 選んだ $r + 1$ 個のうち最大の数を $k$ とする。最大が $k$ であるためには、 $k$ を選び、残り $r$ 個を ${0, 1, \dots, k - 1}$ ( $k$ 個の数)から選ぶ。その方法は $(r k)$ 通り。 $r + 1$ 個選ぶので最大 $k$ は $r \leq k \leq n$ の範囲。

重要最大の数

k

での場合分けは互いに排反で、すべてを尽くす → 和が全体に一致

③ 総和。 各 $k$ の場合を足すと $k = r \sum n (r k) = (r + 1 n + 1) .$

パスカルの三角形の斜めの和(ホッケースティック): 1+3+6=10、斜めに足すと1つ下・隣の数

まとめ 「 $n + 1$ 個から $r + 1$ 個選ぶ」を選んだ最大の数で分類すると、各場合が $(r k)$ になり、和が $(r + 1 n + 1)$ に等しい。計算でなく「何を数えているか」で示す組合せ論法。パスカルの三角形で斜めに足すと1つ下がる、という性質の理由がこれだ。

発展。 $r = 1$ の場合は $\sum_{k = 1}^{n} k = (2 n + 1)$ (和の公式)、 $r = 2$ は $\sum (2 k) = (3 n + 1)$ となる。ここから、 $\sum k^{2}$ を $(2 k)$ と $(1 k)$ の組合せで書いて計算する、という「べき和を二項係数で計算する」方法が使えるようになる。ホッケースティックは $\sum k, \sum k^{2}, \sum k^{3}, \dots$ をすべて統一する母体の公式だ。

答

$0, 1, \dots, n$ から $r + 1$ 個選ぶ方法を「選んだ中の最大の数 $k$ 」で分類。最大が $k$ なら残り $r$ 個を $0, \dots, k - 1$ から選び $(r k)$ 通り。総和が $(r + 1 n + 1)$ 。

別解

パスカルの法則で望遠鏡式に消す(計算で示す)。 パスカルの法則 $(r + 1 k + 1) = (r + 1 k) + (r k)$ を差の形に読み替える:

$(r k) = (r + 1 k + 1) - (r + 1 k)$

これで各項が「隣り合う量の差」になった。 $k = r$ から $n$ まで足すと、途中が打ち消し合って

$k = r \sum n (r k) = (r + 1 n + 1) - (r + 1 r) = (r + 1 n + 1)$

( $(r + 1 r) = 0$ 。)望遠鏡和で1行で済む。

組合せの意味(本解)からは「なぜ成り立つか」が分かり、望遠鏡の方法では「機械的に確かめる」ことができる。パスカルの三角形でこの等式を見ると、ある斜め列を上から足すと1つ右下の値になる。形から「ホッケースティックの公式」と呼ばれ、絵としても覚えやすい恒等式だ。

ポイント

右辺は ${0, \dots, n}$ から $r + 1$ 個選ぶ数。
選んだ最大の数 $k$ で分類すると各場合 $(r k)$ 。
排反かつ全体を尽くすので和は $(r + 1 n + 1)$ 。

よくある間違い

分類の軸を「最小値」や「 $r + 1$ 番目の値」にして対応が付かず迷走する(最大値で切るのがこの和の形)。
最大が $k$ のとき残りを「 $0, \dots, k$ から $r$ 個」とする( $k$ 自身は使用済み。 $0, \dots, k - 1$ の $k$ 個から)。
和の始まり $k = r$ の意味( $r + 1$ 個選ぶには最大が $r$ 以上)を書かない。

問5オイラー関数の和(約数で分類する)

実戦編数え上げ整数の性質オイラー関数約数単元横断

問題

$n$ 以下の自然数で $n$ と互いに素なものの個数を $φ (n)$ とする。 $d ∣ n \sum φ (d) = n$ ( $d$ は $n$ の正の約数を動く)を示せ。

ヒントを見る

$1$ から $n$ までの各数を $g cd (k, n)$ で仕分ける。 $g cd (k, n) = d$ なら $k = d \cdot m$ で $m$ は $\frac{n}{d}$ と互いに素。その個数は?

解答・解説

方針

${1, 2, \dots, n}$ を「 $n$ との最大公約数 $g cd (k, n)$ の値」で分類。 $g cd (k, n) = d$ となる $k$ の個数を数え、約数 $d$ で総和をとる。

解答

⓪ 発想(どう考え始めるか) 左辺は約数ごとの和、右辺は $n$ だ。「 $1$ から $n$ までの $n$ 個の整数を、過不足なく分類すると左辺になる」と読むのが筋だ。

分類の軸は $g cd (k, n)$ の値。 $g cd (k, n) = d$ なら $k = d m$ で、 $m$ は $\frac{n}{d}$ と互いに素。つまり「 $g cd = d$ の組」の個数はちょうど $φ (\frac{n}{d})$ 。 $d$ が約数を走れば $\frac{n}{d}$ も約数を走るから、和は $\sum φ (d)$ に等しい。

① $g cd$ で分類する。 ${1, 2, \dots, n}$ の各 $k$ を $g cd (k, n) = d$ で分ける。 $d$ は $n$ の約数を動く。 $g cd (k, n) = d$ なら $k = d \cdot m$ と書け、 $g cd (m, \frac{n}{d}) = 1$ かつ $1 \leq m \leq \frac{n}{d}$ 。

② 各組の個数。 よって $g cd (k, n) = d$ となる $k$ の個数は、 $\frac{n}{d}$ 以下で $\frac{n}{d}$ と互いに素な $m$ の個数、すなわち $φ (\frac{n}{d})$ 。

重要

g cd (k, n) = d ⟺ k = d m, g cd (m, \frac{n}{d}) = 1

。その個数は

φ (\frac{n}{d})

③ 総和をとる。 すべての $k$ はちょうど1つの $d$ に属す(排反かつ全体)から $n = d ∣ n \sum φ (\frac{n}{d}) = d ∣ n \sum φ (d)$ (最後は $d$ と $\frac{n}{d}$ が約数全体を同じように動くため)。

まとめ $1$ 〜 $n$ を $g cd (k, n)$ で分類すると、 $g cd = d$ の組は $φ (\frac{n}{d})$ 個。約数で足すと全体 $n$ 。約数を裏返せば $\sum_{d ∣ n} φ (d) = n$ 。数え上げの分類と整数(オイラー関数)の融合。 $n = 36$ なら約数の $φ$ の和が $36$ 。

発展。 この等式は「1の $n$ 乗根を位数で分類すると、位数 $d$ の根がちょうど $φ (d)$ 個」という複素数平面の事実の言い換えでもある(既約分数 $\frac{k}{d}$ ⟺ 位数 $d$ の根 $e^{2 π ik / d}$ …を数IIIの言葉を借りずに言えば、円周の $n$ 等分点の「周期」による分類)。数論ではこの型の和の関係からメビウスの反転公式が生まれ、 $φ (n)$ の積公式へつながっていく。

答

$1, 2, \dots, n$ の各 $k$ を $g = g cd (k, n)$ で分類。 $g cd (k, n) = d$ となる $k$ は $\frac{k}{d}$ が $\frac{n}{d}$ と互いに素なもので $φ (\frac{n}{d})$ 個。約数を渡ると総数 $n$ 。

別解

分数 $\frac{1}{n}, \dots, \frac{n}{n}$ を約分して仕分ける(1行の名証明)。 $n$ 個の分数

$\frac{1}{n}, \frac{2}{n}, \frac{3}{n}, \dots, \frac{n}{n}$

をすべて既約分数に約分する。約分後の分母は $n$ の約数 $d$ のどれかで、分母が $d$ になる分数は「分子が $d$ 以下で $d$ と互いに素」なものなので、ちょうど $φ (d)$ 個ある(逆に、分母 $d$ ・既約の分数はすべてこのリストに現れる: $\frac{a}{d} = \frac{a ( n / d )}{n}$ )。

$n$ 個の分数が、約数ごとに $φ (d)$ 個ずつに過不足なく仕分けられたのだから

$d ∣ n \sum φ (d) = n$

$g cd$ による分類(本解)と中身は同じだが、「約分」という誰もが知る操作で言い換えると、証明が1枚の絵になる。 $n = 12$ で実際に12個の分数を約分してみると、分母 $1, 2, 3, 4, 6, 12$ に $1, 1, 2, 2, 2, 4$ 個ずつとなり、合計12個であることが確かめられる。

ポイント

$1$ 〜 $n$ を $g cd (k, n)$ の値で分類する。
$g cd (k, n) = d$ となる $k$ は $φ (\frac{n}{d})$ 個。
約数で総和をとると全体 $n$ 、裏返して $\sum_{d ∣ n} φ (d) = n$ 。

よくある間違い

「 $g cd (k, n) = d$ となる $k$ の個数」を $φ (d)$ とする(正しくは $φ (n / d)$ 。 $k = d m$ の $m$ が $n / d$ と互いに素)。
$d$ と $n / d$ の走り替え( $d$ が約数全体を走れば $n / d$ も走る)の一言を落とし、 $\sum φ (n / d) = \sum φ (d)$ の同一視が宙に浮く。
分類が「漏れなく重複なく」であること( $g cd$ は各 $k$ にただ1つ)を明示しない。

問6符号つき二項和(全射の数え上げ)

実戦編数え上げ包除原理二項係数全射単元横断

問題

$n$ を自然数とする。 $k = 0 \sum n (- 1)^{k} (k n) k^{n}$ を求めよ。

ヒントを見る

$n$ 個から $n$ 個への全射は全単射だから $n!$ 通り。これを「 $k$ 個の要素が値域から抜ける」包除で数えると $\sum (- 1)^{k} (k n) (n - k)^{n}$ 。 $k$ を $n - k$ に置き換えると?

解答・解説

方針

写像 ${1, \dots, n} \to {1, \dots, n}$ の全射の数を、包除原理で $\sum (- 1)^{k} (k n) (n - k)^{n}$ と表す。全射=全単射なので $n!$ 。置換で目的の和に直す。

解答

⓪ 発想(どう考え始めるか) 交互符号 $\times$ 二項係数 $\times$ べき、という組合せは包除原理でよく現れる形だ。何かの数え上げの式ではないか、と疑う。

$n$ 人から $n$ 人への写像で「全員が像に現れる」(全射)を包除で数えると

$\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{n}$ は、使われない人を $k$ 人選んで除外する形だ。全射=全単射で答えは $n!$ だ。あとは $k \to n - k$ の置き換えで、与えられた和の形に直せば $(- 1)^{n} n!$ 。

定理包除原理による全射の数

k = 0 \sum n (- 1)^{k} (k n) (n - k)^{n}

(

n

個から

n

個への全射)

① 全射 $=$ 全単射で $n!$ 。 ${1, \dots, n} \to {1, \dots, n}$ の写像が全射なら、値域が $n$ 個すべてを覆い、大きさが等しいので単射でもある(全単射)。よって全射の数は $n!$ 。

② 包除で数える。 値域の $k$ 個の要素を「覆わない」とする場合を包除で足し引きすると、全射の数は $k = 0 \sum n (- 1)^{k} (k n) (n - k)^{n} = n! .$ ③ 置換して目的の和に。 $k \to n - k$ と置換する。 $(n - k n) = (k n)$ 、 $(- 1)^{n - k} = (- 1)^{n} (- 1)^{k}$ だから $n! = k = 0 \sum n (- 1)^{n - k} (k n) k^{n} = (- 1)^{n} k = 0 \sum n (- 1)^{k} (k n) k^{n} .$ よって $k = 0 \sum n (- 1)^{k} (k n) k^{n} = (- 1)^{n} n!$ 。

まとめ符号つき二項和は「全射の個数」の包除表示。全射=全単射で $n!$ 、置換 $k \to n - k$ で目的の和が $(- 1)^{n} n!$ と分かる。数え上げ・包除・二項の融合。 $n = 3$ なら $- 6$ 。

発展。 べきを下げると $\sum (- 1)^{k} (k n) k^{m} = 0$ ( $0 \leq m < n$ )となる。これは「 $n$ 回差分すると $n$ 次未満は消える」の言い換えで、こちらも全射の数え上げ(不足するから0)として読める。この「二項係数×交互符号は $n$ 階差分」という対応は、スターリング数の一般式 $S (n, m) = \frac{1}{m !} \sum (- 1)^{k} (k m) (m - k)^{n}$ の背景でもある。

答

$n$ 個から $n$ 個への全射(=全単射 $n!$ 通り)を包除で数えると $\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{n} = n!$ 。 $k \to n - k$ の置換で $\sum (- 1)^{k} (k n) k^{n} = (- 1)^{n} n!$ 。

別解

「n 回差をとる」と読む(階差の言葉)。 数列 $f (x)$ の階差を $Δ f (x) = f (x + 1) - f (x)$ とすると、 $n$ 回繰り返した階差は二項係数で書ける:

$Δ^{n} f (0) = k = 0 \sum n (- 1)^{n - k} (k n) f (k)$

つまり、与えられた和は( $(- 1)^{n}$ 倍を除いて) $f (x) = x^{n}$ の $n$ 階の階差そのものだ。

ここで階差の性質: 多項式の階差は次数を1下げ、先頭係数に次数を掛ける( $Δ x^{m} = m x^{m - 1} + \dots$ 、微分とそっくり)。 $n$ 次の $x^{n}$ を $n$ 回差分すると、 $n \cdot (n - 1) \dots 1 = n!$ という定数だけが残る(低次の項は途中で消滅する)。よって

$k = 0 \sum n (- 1)^{k} (k n) k^{n} = (- 1)^{n} Δ^{n} (x^{n})_{x = 0} = (- 1)^{n} n!$

全射の数え上げ(本解)は組合せの見方で、階差は「離散の微分を $n$ 回」という解析の見方だ。同じ和が組合せと解析の2つの分野を結びつけている。

ポイント

$n$ 個から $n$ 個への全射は全単射で $n!$ 通り。
包除で $\sum (- 1)^{k} (k n) (n - k)^{n} = n!$ 。
$k \to n - k$ の置換で $\sum (- 1)^{k} (k n) k^{n} = (- 1)^{n} n!$ 。

よくある間違い

包除の式を $(n - k)^{n}$ でなく $k^{n}$ で立てて符号がずれる( $k \to n - k$ の置換で $(- 1)^{n}$ 倍が出て、この符号が答えの $(- 1)^{n}$ になる)。
「全射 $=$ 全単射」( $n$ 人から $n$ 人へ)の理由(有限集合で個数が同じ)を書かない。
$k = 0$ の項( $0^{n}$ や $n^{n}$ )の扱いを雑にして和の端が崩れる。

問7円環をk色で塗り分ける(数え上げと漸化式)

実戦編数え上げ漸化式塗り分け彩色単元横断

問題

$n$ 個のマスを円形に並べ、隣り合うマスが異なる色になるように $k$ 色で塗る方法の総数 $c_{n}$ を求めよ( $n \geq 3, k \geq 2$ )。

ヒントを見る

1列に並べる塗り方は $k (k - 1)^{n - 1}$ 。そのうち両端が同色のものは、両端をくっつけると $n - 1$ 個の円になる。 $c_{n}$ と $c_{n - 1}$ の関係は?

解答・解説

方針

まず1列(円にしない)の塗り方は $k (k - 1)^{n - 1}$ 。これを「両端が異色(=円としても正しい)」と「両端が同色」に分け、後者を1つ短い円と対応させて漸化式を作る。

解答

⓪ 発想(どう考え始めるか) 円は端がつながっていて数えにくい。いったん切って1列にするのが基本だ。

1列の塗り方は、左端 $k$ 色、以降は左隣と違う色で $k (k - 1)^{n - 1}$ 通り。

この1列を円に丸めるとき、両端が異色ならそのまま正しい円の塗り( $= c_{n}$ )。両端が同色なら、両端を融合すると1つ短い円の塗り( $= c_{n - 1}$ )に対応する。よって $c_{n} + c_{n - 1} = k (k - 1)^{n - 1}$ となる。この漸化式を解けば閉じた式が出る。

① 直線の塗り方を分ける。 $n$ マスを1列に隣接異色で塗る方法は $k (k - 1)^{n - 1}$ 。両端の色で $k (k - 1)^{n - 1} = 両端異色 c_{n} + 両端同色 c_{n - 1} .$ (両端同色の並びは、その両端を1マスとみなすと $n - 1$ マスの円の正しい塗りと1対1。)

例(n=5, k=3): 5マスを輪にし、隣どうし異色に3色で塗った一例(青・赤・黒)。総数は (k−1)ⁿ+(−1)ⁿ(k−1)。

② 漸化式を解く。 $c_{n} = k (k - 1)^{n - 1} - c_{n - 1}$ 。両辺に $(- 1)^{n}$ を掛けて整理する、あるいは $c_{n} - (k - 1)^{n}$ を考えると等比になる。 $c_{n} - (k - 1)^{n} = - (c_{n - 1} - (k - 1)^{n - 1})$ が成り立つ(代入で確認)ので、 $d_{n} = c_{n} - (k - 1)^{n}$ は公比 $- 1$ の等比数列。

重要

c_{n} = k (k - 1)^{n - 1} - c_{n - 1}

から

c_{n} - (k - 1)^{n} = - (c_{n - 1} - (k - 1)^{n - 1})

③ 一般項。 $c_{2} = k (k - 1)$ (2マスの円=1列と同じ)より $d_{2} = c_{2} - (k - 1)^{2} = (k - 1)$ 。よって $d_{n} = (k - 1) (- 1)^{n - 2} = (k - 1) (- 1)^{n}$ 。したがって $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1) .$

まとめ円は直線に開いて数え、両端が同色・異色で場合分けすると $k (k - 1)^{n - 1} = c_{n} + c_{n - 1}$ 。等比化して $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ 。数え上げと漸化式の融合。 $n = 5, k = 3$ なら $32 - 2 = 30$ 。

発展。 $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ は、グラフ理論では「サイクル $C_{n}$ の彩色多項式」と呼ばれる式そのもの。さらに「回転して同じ塗りは1つと数える」(首飾りの問題)に変えると、割る操作が単純な $\div n$ では済まず、バーンサイドの補題(回転ごとの固定点を平均する)が必要になる。「配置の数え上げ」と「対称性で割る数え上げ」の違いは、この問題を少し変えるだけで現れる。

答

1列(パス)の塗り方 $k (k - 1)^{n - 1}$ を、両端が同色か否かで分けると $k (k - 1)^{n - 1} = c_{n} + c_{n - 1}$ 。解いて $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ 。

別解

端の色で場合分けする第2の漸化式(検算にも使える)。 円を切らずに、 $n$ 番目のマスの色で直接分類する手もある。1列に並べた $1, \dots, n$ 番を考え、円の条件は「隣どうし異色+両端異色」。

$n$ 番目のマスから見ると:

$n - 1$ 番目までが「円として正しい塗り」( $c_{n - 1}$ 通り)のとき、 $n$ 番は「 $n - 1$ 番とも1番とも違う色」で、 $k - 2$ 色
$n - 1$ 番目までが「1列としては正しいが両端( $1$ 番と $n - 1$ 番)が同色」のとき、 $n$ 番は「その色以外」で、 $k - 1$ 色。この場合の数は( $n - 1$ 番と1番を融合して) $c_{n - 2}$ 通り

$c_{n} = (k - 2) c_{n - 1} + (k - 1) c_{n - 2}$

本解の $c_{n} + c_{n - 1} = k (k - 1)^{n - 1}$ とは別の漸化式だが、閉じた式 $(k - 1)^{n} + (- 1)^{n} (k - 1)$ は両方を満たす(代入で確認できる)。2本の独立な漸化式から同じ式が出れば、答えの信頼度は大きく上がる。数え上げの検算の方法として覚えておきたい。

ポイント

直線(1列)の塗り方 $k (k - 1)^{n - 1}$ を両端の色で分ける。
両端同色は $n - 1$ マスの円と対応、 $k (k - 1)^{n - 1} = c_{n} + c_{n - 1}$ 。
等比化して $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ 。

よくある間違い

円の数え上げをいきなり「1列の $\frac{1}{n}$ 」などと回転で割る方向に行く(マスは固定されていて回転同一視はしない問題)。
両端同色の1列と $c_{n - 1}$ の対応(両端を融合して1マス減らす)の説明を落とす。
漸化式を解くとき、 $c_{n} - (k - 1)^{n}$ が公比 $- 1$ の等比になる構造( $c_{n} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ の由来)を確認せず結果だけ書く。

問8グループ分けの総数(ベル数の漸化式)

実戦編数え上げ漸化式組分け二項係数単元横断

問題

$n$ 人を、区別のないグループにいくつかに分ける方法の総数(各人はちょうど1グループ、空グループは作らない)をベル数 $B_{n}$ とし、 $B_{0} = 1$ とする。(1) $B_{n + 1} = k = 0 \sum n (k n) B_{k}$ を示せ。

(2) $B_{4}$ を求めよ。

ヒントを見る

(1) 特定の1人(例えば最後の人)に注目。その人と同じグループになる残りのメンバーを $n$ 人から選ぶと、残りの人たちの分け方が $B$ で書ける。(2) $B_{0} = 1$ から順に。

解答・解説

方針

(1) $(n + 1)$ 番目の人が属するグループの残りメンバー(残り $n$ 人から選ぶ)の人数で場合分けする。(2) 漸化式を順に計算。

解答

⓪ 発想(どう考え始めるか) 分け方全体を直接数えるのは難しい。特定の1人に注目して分類する。これは数え上げでよく使う手だ。

$(n + 1)$ 番目の人が入るグループの「他のメンバー」を、残り $n$ 人から $j$ 人選ぶ( $(j n)$ 通り)。残った $n - j$ 人は自由に分かれる( $B_{n - j}$ 通り)。 $j$ を走らせて足せば $B_{n + 1} = \sum (j n) B_{n - j} = \sum (k n) B_{k}$ ( $k = n - j$ と置き換え)。(2)は漸化式を $B_{1}$ から順に回すだけだ。

① 漸化式を示す。 $(n + 1)$ 番目の人と同じグループになる相手を、残り $n$ 人から $j$ 人選ぶ( $(j n)$ 通り)。この $j + 1$ 人で1グループが決まり、残る $n - j$ 人の分け方は $B_{n - j}$ 通り。よって $B_{n + 1} = j = 0 \sum n (j n) B_{n - j} .$ $k = n - j$ と置き換えると $(j n) = (k n)$ より $B_{n + 1} = k = 0 \sum n (k n) B_{k}$ 。

重要特定の1人の属するグループの残りメンバー(

n

人から選ぶ)で分類 →

B_{n + 1} = \sum_{k = 0}^{n} (k n) B_{k}

② $B_{4}$ を計算する。 $B_{0} = 1$ から順に。 $B_{1} = (0 0) B_{0} = 1,$ $B_{2} = (0 1) B_{0} + (1 1) B_{1} = 1 + 1 = 2,$ $B_{3} = (0 2) B_{0} + (1 2) B_{1} + (2 2) B_{2} = 1 + 2 + 2 = 5,$ $B_{4} = (0 3) B_{0} + (1 3) B_{1} + (2 3) B_{2} + (3 3) B_{3} = 1 + 3 + 6 + 5 = 15.$ よって $B_{4} = 15$ 。

まとめ特定の1人が属するグループの残りメンバーを選ぶ( $(k n)$ )ことで、 $B_{n + 1} = \sum_{k} (k n) B_{k}$ の漸化式ができる。順に計算して $B_{4} = 15$ 。数え上げと漸化式(ベル数)の融合。

発展。 ベル数 $1, 1, 2, 5, 15, 52, 203, \dots$ は「分け方」の総数として、確率(分割の一様ランダム)、データのクラスタリングの状態数など、応用の広い数列だ。 $B_{n} = \sum_{m} S (n, m)$ (スターリング数の総和)という2階建ての構造、そして本問の漸化式が「指数型母関数 $e^{e^{x} - 1}$ 」という1本の関数に畳み込まれることまで、数え上げの理論の見本市になっている。

答

特定の1人が属するグループの「他のメンバー」の選び方で分類して漸化式。 $B_{1} = 1, B_{2} = 2, B_{3} = 5, B_{4} = 15$ 。

別解

(2)を「グループのサイズの型」で直接数える。 漸化式を使わず、4人の分け方をサイズの型(分割のパターン)で列挙して数えることもできる。

型 ${4}$ (全員1組): $1$ 通り
型 ${3, 1}$ : 1人だけ外す選び方で $(1 4) = 4$ 通り
型 ${2, 2}$ : 2人を選ぶ $(2 4) = 6$ を、2組の入れ替え $2!$ で割って $3$ 通り
型 ${2, 1, 1}$ : ペアを選ぶ $(2 4) = 6$ 通り
型 ${1, 1, 1, 1}$ : $1$ 通り

$B_{4} = 1 + 4 + 3 + 6 + 1 = 15$

漸化式(本解)は $n$ が大きくても機械的に計算でき、型別に直接数える方法は「同サイズのグループは入れ替えても同じ( $2!$ で割る)」という区別の消し方の練習になる。両方で $15$ が出れば、検算も同時に済んでいる。

ポイント

特定の1人が属するグループの残りメンバーで分類する。
$B_{n + 1} = \sum_{k = 0}^{n} (k n) B_{k}$ ( $B_{0} = 1$ )。
順に $B_{1} = 1, B_{2} = 2, B_{3} = 5, B_{4} = 15$ 。

よくある間違い

「特定の1人」を固定せずに漸化式を立てようとして、どのグループ分けを何回数えたか分からなくなる。
型 ${2, 2}$ の数えで $(2 4) = 6$ のまま( $2$ 組の入れ替えで2重に数えている。 $\div 2!$ で3通り)。
グループに区別がない(箱と違う)ことを忘れ、前問(区別できる3箱)と同じ式を書く。

場合の数 実戦編の問題 全8問

問1対角線を越えない最短経路(カタラン数と反射原理)

問題

方針

解答

別解

ポイント

よくある間違い

問22×n をタイルで敷き詰める(フィボナッチ数)

問題

方針

解答

別解

ポイント

よくある間違い

問33つの箱に空なしで入れる(全射と包除原理)

問題

方針

解答

別解

ポイント

よくある間違い

問4斜めの和の公式(組合せの意味で示す)

問題

方針

解答

別解

ポイント

よくある間違い

問5オイラー関数の和(約数で分類する)

問題

方針

解答

別解

ポイント

よくある間違い

問6符号つき二項和(全射の数え上げ)

問題

方針

解答

別解

ポイント

よくある間違い

問7円環をk色で塗り分ける(数え上げと漸化式)

問題

方針

解答

別解

ポイント

よくある間違い

問8グループ分けの総数(ベル数の漸化式)

問題

方針

解答

別解

ポイント

よくある間違い

場合の数実戦編の問題全8問