数学A / 場合の数

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

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

問題

$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つ右下の値になる — 形から「ホッケースティックの公式」と呼ばれる、絵としても覚えやすい恒等式だ。

ポイント

右辺は ${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$ 以上)を書かない。