【先生】 今日は **道順** の話。 碁盤の目みたいな街で、A から B まで **最短** で行く道順は何通り? これ、公式を覚える必要なし。**「左 + 下」を順に書き込むだけ**。 これを **パスカル方式** って言うよ。 【先生】 やり方: (1) A (スタート) から伸びる **最初の縦・横の道** のすべての交差点に「1」を書く (2) その他の交差点には「**左の数 + 下の数**」を書き込む (3) ゴール B の数字が答え 右上にしか進めない (最短だから戻れない) 前提でこれが成り立つ。 【先生】 例で見よう。3×2 の格子 (横 3、縦 2) の左下から右上まで: 1 - 4 - 10 1 - 3 - 6 1 - 1 - 1 (= 一番下の段、A から右へ進むだけだから全部 1) ・2 段目の中央 = 左 1 + 下 1 = 2 …じゃなくて、左 (= 1) + 下 (= 1) を読み間違えてはダメ。 ・最後の右上 = 左 4 + 下 6 = **10 通り**。 【? 理解確認】 横 2、縦 2 の正方形格子 (3 行 3 列の交差点) で、左下 A から右上 B への最短経路は何通り? 4 通り ✓ 6 通り 9 通り 【正解】 正解! パスカル方式で書くと: 1-3-**6** 1-2-3 1-1-1 右上が 6。 【先生】 **工事中・通行止めの点** があるとき: → その交差点に **0** を書く (通れないから 0 通り) → そのあとも普通に「左 + 下」を続ければ自動的に避けた数になる 「× 印を書いて避けて計算」とせず、**0 を書いて続行** がコツ。 【先生】 **必ず通る点 P がある** タイプ: → (A から P までの道順) × (P から B までの道順) を **掛け算** → 「P を通る」=「A→P」と「P→B」を両方こなす、つまり「かつ」だから掛け算。 → 2 つの小さい格子に分けて、それぞれパスカル方式で出す。 【? 理解確認】 5×5 の街で A から B まで最短経路を考える。途中の交差点 P を **必ず通る** とき、求め方は? (A→P の通り) + (P→B の通り) ✓ (A→P の通り) × (P→B の通り) A→B の通り − P を通らない通り 【正解】 正解! 「A→P **かつ** P→B」だから掛け算。 ちなみに「P を通らない」を引き算でも出せるけど、掛け算の方が速い。 【先生】 おまけ。試合数の覚え方も伝えるね。 ・**トーナメント戦 (勝ち抜き)** N チーム → **N − 1 試合** (理由: 優勝チーム以外の N−1 チームが必ず 1 回ずつ負ける) ・**リーグ戦 (総当たり)** N チーム → **N×(N−1) ÷ 2 試合** (理由: 2 チームの組を選ぶ組み合わせ) リーグ戦の **÷2 を忘れる** ミスが超多いから注意。 いろいろな場合の数 (1) のキモ: ・道順は **パスカル方式** (左 + 下) ・**工事中は 0** を書いて続行 ・必ず通る点 P は **A→P × P→B** (掛け算) ・トーナメント = **N−1**、リーグ戦 = **N×(N−1)÷2**