第2問場合の数の解答・解説

漸化式・グラフ上の経路・対称性・上下2状態当サイトの体感難易度：標準最終更新 2026/10/12

問題文について

大学の公式解答ではなく、当サイト独自の解答・解説です。問題文は掲載していません。文系の問題文は、この年度については大学が公開していません（2026/10/12時点）。お手元の過去問集・赤本などでご確認ください。

問題を転載している非公式サイトへのリンクは、当サイトでは行っていません。

$A$ を始点として辺に沿って $n$ 回移動したとき、終点が $A, B, C$ のいずれかとなる経路の総数 $a_{n}$ を求める

答 $a_{n} = \frac{3 ^{n} + 1}{2}$

どの頂点からも辺は3本出ていて、そのうち2本は同じ三角形（同じ面）の中、1本だけが反対側の面へ向かう。だから「いま上の面にいるか下の面にいるか」だけを追えばよく、6頂点を2状態にまとめられる。

$A, B, C$ を「上の面」、 $D, E, F$ を「下の面」と呼ぶ。どの頂点からも辺は3本出ていて、その内訳は

同じ面の他の2頂点へ： $2$ 本
向かい合う面の頂点へ： $1$ 本

である。そこで、 $n$ 回移動したあと上の面にいる経路の数を $t_{n}$ 、下の面にいる数を $u_{n}$ とする。 $P_{0} = A$ なので $t_{0} = 1$ 、 $u_{0} = 0$ である。

漸化式。 上の内訳から

t_{n} = 2 t_{n - 1} + u_{n - 1}, u_{n} = t_{n - 1} + 2 u_{n - 1}

である。和と差をとると

t_{n} + u_{n} = 3 (t_{n - 1} + u_{n - 1}), t_{n} - u_{n} = t_{n - 1} - u_{n - 1}

となる。したがって $t_{n} + u_{n} = 3^{n}$ （全経路数で、当然である）、 $t_{n} - u_{n} = t_{0} - u_{0} = 1$ である。2式を足して $2$ で割ると

a_{n} = t_{n} = \frac{3 ^{n} + 1}{2}

である。

最初の数項は $2, 5, 14, 41, 122, \dots$ である。 $3^{n}$ が奇数なので $3^{n} + 1$ は偶数で、 $a_{n}$ は必ず整数になる。

三角柱の辺のつながりを隣接表にして経路数を数え上げると、 $n = 1, \dots, 9$ で $2, 5, 14, 41, 122, 365, 1094, 3281, 9842$ となり、 $\frac{3 ^{n} + 1}{2}$ の値と完全に一致する。たとえば $n = 2$ では、 $A$ から2回で上の面に戻る経路が $5$ 通りある。

「上の面にいる」だけを状態にできるのは、上の面のどの頂点から見ても内訳が $2 : 1$ で同じだからである。頂点ごとに数えようとすると6本の漸化式になる。

$t_{n} - u_{n}$ が変わらないことに気づくと、 $t_{n}$ の2項間漸化式を解かずに済む。 $t_{n} = 2 t_{n - 1} + (3^{n - 1} - t_{n - 1}) = t_{n - 1} + 3^{n - 1}$ として階差で解いてもよい。

$P_{0} = A$ なので $n = 0$ では終点が $A$ である。 $t_{0} = 1$ から始める。

2022年度の全5問をまとめて読む

大学の公式解答ではなく、当サイト独自の解答・解説です。問題文は掲載していません。解答は当サイトで検算していますが、誤りが残っている可能性はあります。掲載方針

当サイト運営者が制作した教材

同じ形式の問題を、5回分

合格答案をつくる京大文系数学 2027

京大文系数学の出題を分析して書き下ろした予想問題集です。過去問そのものは入っていません。本番と同じ試験時間・大問構成で5回分、解答・詳解・別解に加えて、小問ごとの加点・減点つきの採点表を収録しています。

Amazonで見る全2巻を見る¥2,695・106ページ・2026年8月9日発売

中身を試し読みする

扉・問題・解答などを、それぞれ抜粋して掲載しています。連続したページではありません。画像を押すと拡大できます。

抜粋をPDFでまとめて見る

問題文について

A を始点として辺に沿って n 回移動したとき、終点が A,B,C のいずれかとなる経路の総数 an​ を求める

同じ形式の問題を、5回分

中身を試し読みする

関連するページ

$A$ を始点として辺に沿って $n$ 回移動したとき、終点が $A, B, C$ のいずれかとなる経路の総数 $a_{n}$ を求める