漸化式×場合の数

4814

初めまして！奏といいます。Mathlogへの憧れでこの度記事を書くことにしました。
私の話はさておき、この記事では場合の数の問題を漸化式を用いて処理するテクニックについて紹介します。ある界隈では「動的計画法」と呼ばれているようですが、筆者があまり詳しくないのでここでの使用は避けます。競技数学でも受験数学でも広く使える考え方です。漸化式および数列の基本的な知識を前提としています。

考え方

さて、この考え方を端的に言うと、「一般化することで再帰的な構造をもつ場合の数の問題について、漸化式を立てて調べ上げる」ということになります。なるほど、意味不明ですね。具体例を見ていく方がわかりやすいので、以下のような問を考えてみましょう。

階段を $1$ 歩につき $1$ 段または $2$ 段登るとき、 $8$ 段の階段を登る方法は何通りですか？

色々な解法が考えられそうです。筆者は「 $2$ 段登った回数で場合分け」、「気合いで数え上げ」、そして「漸化式で処理」あたりがパッと思いつきました。いずれも有効ですが、ここでは漸化式を用いた解法を紹介します。

以下、解説です。

※自分で考えたい方はネタバレ注意です。

まず、一般に $n$ 段の階段を登る方法を $a_{n}$ 通りとします。 $a_{8}$ の値を求めればよいことになります。ここで、あと $1$ 歩で登り切れるという状況は、「ちょうど $6$ 段または $7$ 段を登った」ときなので、 $a_{8} = a_{7} + a_{6}$ が成立します。

補足

6

段を登ったとき、残りの登り方は

2

通りあるのでは？と考える方もいるかもしれませんが、そのうち

2

歩かけて登る際に

7

段目を踏みますよね。なのでこれで漏れなく、重複なく数えることができています。最後の

1

歩で登る段数によって場合分けをしていると言うと分かりやすいでしょうか。

同様にして、一般に漸化式 $a_{n + 2} = a_{n + 1} + a_{n}$ を得ます。今回の問題設定は $3$ 項間漸化式に対応するわけですね。
さて、漸化式が機能するためには初期条件が必要でした。これは調べ上げですぐに $a_{1} = 1, a_{2} = 2$ が分かります。後は $a_{3} = 2 + 1 = 3, a_{4} = 3 + 2 = 5, . . .$ と調べていくことで、求める場合の数は $a_{8} = 34$ 通りです。

以上が全体の解法の流れになります。改めてまとめると、

実験などから場合分けで再帰的な構造を発見し、漸化式を立てる
数え上げである値を調べて、漸化式を繰り返し用いてもとの値を求める

ということになります。再帰的、とは同じ形式の問題に帰着できるということです。今回の問題であればもとの問題から同様に $1$ 段や $2$ 段を登るというより簡単な問題に置き換えられました。
また、多くの場合漸化式を解くことはあまりメリットがありません。例えば、先ほどの漸化式（フィボナッチ数列といいます）の解は

$a_{n} = \frac{1}{\sqrt{5}} {(\frac{1 + \sqrt{5}}{2})^{n + 1} - (\frac{1 - \sqrt{5}}{2})^{n + 1}}$

という形で表されます。これを求めて $n = 8$ を展開...やめておきましょう。素直に $1$ つずつ求めるのがよさそうです。

例題

続いて、もう $1$ つ頻出のパターンを紹介します。例題を見ながら考えていきましょう。

OMC128-C

$2 \times 6$ のマス目があり、各マスに $1, 2, 4$ のいずれかを書き込みます。このとき、辺で隣り合う $2$ マスに書き込まれた整数が常に互いに素となるような書き込み方は何通りありますか？

整数との融合問題ですね。筆者のお友達の問題です。作問がうまい。

先ほどと本質的な考え方は同じなので少し考えてみてください。下に進むと解説が始まります。

まずは条件を整理すると、偶数どうしが隣り合ってはならないので、隣り合うマスの少なくとも一方は $1$ です。逆に、これは題意を満たすための十分条件でもあります。

この事実を踏まえて、マス目を便宜上 $2$ 行 $6$ 列とします。マス目は横長なのでまずは各列について考察しましょう。各列の数字を上から $(x, y)$ のように表記すると $(1, 1), (1, 2), (1, 4), (2, 1), (4, 1)$ の $5$ つのパターンが考えられます。
また、各列のそれぞれのパターンと隣り合うことができるパターンは常に $5, 3, 3, 3, 3$ 通りと分かります。このパターンをいい感じに並べていけばよさそうです。構造がかなり見えてきましたね。

それではいよいよ漸化式を立てていきます。一般に $2$ 行 $n$ 列のマス目について、左から書き込んでいくこととします。
ここが本問の山場なのですが、 $(1, 1)$ 以外のパターンはどのパターンについても｢ $(1, 1)$ とは隣合ってよく、その他に自身以外のちょうど $2$ つのパターンと隣合うことができる｣という性質があります。すなわち、これら $4$ つのパターンには対称性があるので、書き込み方のうち最も右の行が $(1, 1)$ であるものを $a_{n}$ 通り、そうでないものを $b_{n}$ 通りとします。求める値は $a_{6} + b_{6}$ ですね。

すると、先ほどまでの議論から、 $1$ つ左の行のパターンとの組合せに注意して書き込んでいくことを考えると

${\begin{cases} a_{n + 1} = a_{n} + b_{n} \\ b_{n + 1} = 4 a_{n} + 2 b_{n} \end{cases}$

が成立します。この問題は連立漸化式を立てることで解くことができたのです。
後は例のごとく初項 $a_{1} = 1, b_{1} = 4$ を引っ張ってくることで、終わり...でも良いのですが、せっかくなのでもう一工夫できないでしょうか？

漸化式の形と求める値をじーっと見ると、答えは $a_{7}$ であると分かります。よって、漸化式をいい感じに変形して、 $a_{n + 2} = 3 a_{n + 1} + 2 a_{n}$ という形にするとその後の計算が半分になりますね。 $a_{1} = 1, a_{2} = 5$ から順に調べると求める値は $a_{7} = 2753$ 通りです。

というわけで、連立漸化式の紹介でした。最後の変形は元々サイトにあったものをお借りしているのですが、本当に練られていますよね。( 出典はこちら )
$3$ 項間漸化式と合わせてこれらが圧倒的に頻出だと思います。最後に、その他のトリッキーな漸化式の問題を $1$ つ紹介して例題解説を終えます。

JMO'07yo-07

どれも $3$ の非負整数乗であるいくつかの整数の和として $100$ を表す方法は何通りあるか。ただし、和をとる順番のみが異なるものは同じ表し方とみなす。

JMOからの出題です。初見のときはかなり苦戦しました...

「漸化式を用いる」をヒントにぜひ一度挑戦してみて下さい。

それでは下に進むと解説です。なかなか重たいですが頑張りましょうね。

解説に早速入りますが...ひとまず実験してみましょう。

一般に、 $3$ の非負整数乗であるいくつかの整数の和として $n$ を表す方法を $a_{n}$ 通りとします。求める値は $a_{100}$ ですね。

実験

n = 1

のとき、

1 = 1

(

1

通り)

n = 2

のとき、

2 = 1 + 1

(

1

通り)

n = 3

のとき、

3 = 1 + 1 + 1 = 3

(

2

通り)

n = 4

のとき、

4 = 1 + 1 + 1 + 1 = 1 + 3

(

2

通り)

n = 5

のとき、

5 = 1 + 1 + 1 + 1 + = 1 + 1 + 3

(

2

通り)

n = 6

のとき、

6 = 1 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 3 = 3 + 3

(

3

通り)

さて、ここから何が言えるでしょう。

前後の項に着目すると、「添字が $3$ の倍数のときには値が増加して、そうでないときは変わらない」という予想が立つといい感じです。値がどのように増えるかはちょっと情報不足なので、まずは後半から考えていきましょう。

任意の $n$ について、 $a_{3 n + 2} = a_{3 n + 1} = a_{3 n}$

このように表現できますね。便宜上 $a_{0} = 1$ としています。さて、実験の $n$ が $3$ の倍数でない部分から一つ気づきたいのは「 $1$ は必ず使う」ということです。言われてみれば、 $1$ がないと和は $3$ の倍数になってしまうので当たり前に思えますが、これは手を動かしてみないと意外と見えません。実験は世界を救います。

任意の $n$ について、 $3 n + 1$ を表す際、 $1$ を使わないと仮定すると和は $3$ の倍数となり矛盾する。よって、 $1$ を初めに $1$ つ用意すると、残りの $3 n$ の表し方と $3 n + 1$ の表し方は $1$ 対 $1$ に対応する。すなわち $a_{3 n + 1} = a_{3 n}$ である。
同様にして $a_{3 n + 2} = a_{3 n + 1}$ が従い、予想は示された。

さて、漸化式がたったから例のごとく初期条件を...といきたいところですが、これだけでは解けません。実際、 $a_{3 n}$ の添字を小さくすることができません。筆者はここで困りました...
今 $a_{3 n}$ で困っている理由は、必ず使うと断定できる数が存在しないからです。このあたりは丁寧に言語化していきましょう。初心に帰って漸化式を立てる方針を確認すると「場合分けで再帰的な構造を見つける」とのことです。階段の例がまさにそれでした。

先ほどの議論を応用することを念頭に置くと、「 $1$ を使うかどうか」で場合分けという方針が見えてきます。以下、 $a_{3 n}$ の別の表現を探ります。

$1$ を使う場合
これは上の議論と同じです。残りの $3 n - 1$ を分解する方法を考えればよいので、表し方は $a_{3 n - 1} = a_{3 (n - 1)}$ 通りです。後のことを考えて漸化式でできるだけ添字を小さくしておきましょう。
$1$ を使わない場合
このときはちょっと訳が違ってきそうです。困ったら再び実験しましょう。

実験

n = 1

のとき、

3 = 3

(

1

通り)

n = 2

のとき、

6 = 3 + 3

(

1

通り)

n = 3

のとき、

9 = 3 + 3 + 3 = 9

(

2

通り)

n = 4

のとき、

12 = 3 + 3 + 3 + 3 = 3 + 9

(

2

通り)

n = 5

のとき、

15 = 3 + 3 + 3 + 3 + 3 = 3 + 3 + 9

(

2

通り)

n = 6

のとき、

18 = 3 + 3 + 3 + 3 + 3 + 3 = 3 + 3 + 3 + 9 = 9 + 9

(

3

通り)

お〜、なんだか見覚えのある並びですね。

具体的には、 $a_{n}$ と全く同じ挙動をしています。これは、 $1$ を使わない場合には全ての数が $3$ の倍数で表されているために、両辺を $3$ で割ることで $n$ を表す方法に帰着するからです。よって、これは $a_{n}$ 通りです。

以上より、 $a_{3 n} = a_{3 (n - 1)} ＋ a_{n}$ です。一度事実を整理しておきましょう。

任意の $n$ について、 $a_{3 n + 2} = a_{3 n + 1} = a_{3 n} = a_{3 (n - 1)} + a_{n}$

それではいよいよ $a_{100}$ を計算しましょう。
実験より、 $a_{1} = a_{2} = 1, a_{3} = 2$ なので、 $a_{5} = a_{4} = a_{3} = 2, a_{6} = a_{3} + a_{2} = 3$ ...
あれ、これを $100$ までやるのは少し大変そうですね。 $3$ つごとに同じ値を取ることに着目すると計算は高々 $33$ 回なのでいけなくはないのですが、多くのことを学んで頂きたいのでここでは漸化式のもう一つの使い方を紹介します。

それは「求める値の添字を落とす」ということです。これまでは漸化式を得たら「添字の小さいものから全て順に調べていく」という手法を取っていました。ここでは逆に「 $a_{100}$ を漸化式を用いて変形していく」ということをします。やや出題頻度は低いですが、むしろ素直な方法だと筆者は感じます。

さて、実際に計算すると、
$a_{100} = a_{99} = a_{33} + a_{96} = a_{11} + a_{30} + a_{31} + a_{93}$ ...
ん〜、項の数がどんどん増えてしまいます。さあ、この問題の最大の壁にぶつかりました。どうしたものでしょうか。
結論からいうと、漸化式の形から、添字が $3$ の倍数のものを処理する際には必ず項が $2$ つに分かれてしまうので、項が極端に少ないまま計算するのは難しいと思います。ということで、せめて扱いやすい形に持ち込みたいものです。

そんな動機で再び漸化式とにらめっこすると、 $a_{3 n} - a_{3 (n - 1)} = a_{n}$ という形が見えてきます。これは、「 $a_{3 n}$ の階差数列が $a_{n}$ である」ということを示します。(厳密には $a_{n - 1}$ です)

よって、このことを念頭に置くと、
$a_{100} = a_{99} = \sum_{i = 1}^{33} a_{i} + a_{0} = \sum_{i = 0}^{33} a_{i} = 3 \sum_{i = 0}^{10} a_{3 i} + a_{33} = 3 \sum_{i = 0}^{10} a_{3 i} + \sum_{i = 0}^{10} a_{i} + a_{11}$
と変形できます。後半の変形は $a_{3 n + 2} = a_{3 n + 1} = a_{3 n}$ を用いています。シグマの各項にも同様の議論をすることで、
$\sum_{i = 0}^{10} a_{3 i} = \sum_{i = 0}^{10} \sum_{j = 0}^{i} a_{j} = \sum_{i = 0}^{10} (11 - i) a_{i}$
を得ます。ここの変形は本質部分ではないので割愛しますが、実際に項を書き並べてみると理解できるかと思います。
後は下り坂ですね。計算して求める値は
$3 \sum_{i = 0}^{10} (11 - i) a_{i} + \sum_{i = 0}^{10} a_{i} + a_{11} = \sum_{i = 0}^{11} (34 - 3 i) a_{i} = 93 a_{0} + 66 a_{3} + 39 a_{6} + 12 a_{9} = 402$

となります。

いや〜お疲れ様でした。筆者は計算を合わせるのに $1$ 時間かかりました。難易度がぐんと上がったのですが、「実験などから構造を理解したのち、場合分けをして漸化式に落とし込む」という同様のプロセスが使えることを体感して頂けたらすごく嬉しいです。全然見た目の異なる問題を同一視できる点が数学の楽しさだと思います。

これにて解説は終了です。演習問題を以下に用意しました。OMCからの問題の解説はリンクに飛ぶことで確認して下さい。

演習問題

JMO'11yo-9

赤、青、黄色の玉を合わせて $12$ 個一列に並べる方法で、どの球についても同じ色の隣接する球があるようなものは何通りか。ただし、並べる球の色が $2$ 色以下の場合も考えるものとする。

$9$ 番にしては易しい印象を受けます。あまり怯えすぎないで下さいね。

解説

一般に、

n

個の球を並べる方法を

a_{n}

通りとする。

n + 2

個の球を左から並べることを考えると、

n

個目と

n + 1

個目の色が同じであるとき、場合の数は

a_{n + 1}

通り。

n

個目と

n + 1

個目の色が異なるとき、最後の

2

個の色の組は

2

通りなので、場合の数は

2 a_{n}

通り。
よって、

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

であり、

a_{2} = a_{3} = 3

と合わせて求める値は

a_{12} = 2049

通りである。

OMC091D

$2$ 行 $10$ 列のマス目のそれぞれに矢印 ↑、↓、←、→ のいずれか1つを書き込む方法であって、以下の条件をみたすものは何通りありますか？
・どのマス $M$ についても、 $M$ と辺を共有するマスであって、そこに書き込まれた矢印が $M$ を指すものがちょうど1個存在する。

個人的にOMCで $1$ 番の良問だと思っています。
出典および解説はこちら

自作

以下を満たすための正整数 $n$ に関する必要十分条件を求めて下さい。
・サイコロを $n$ 回投げるとき、出目の総和が $5$ の倍数となる確率は $\frac{1}{5}$ より大きい。

証明問題を添えてみました。設定がシンプルでお気に入りです。

解説

一般に、

n

回サイコロを降ったとき、出目の総和を

S_{n}

とし、これが

5

で割って

i

余るような方法を

a_{n, i}

通りとする。(

i = 0, 1, 2, 3, 4

)
ここで、このような方法は

S_{n - 1} \equiv S_{n} - 1 (\mod 5)

のとき

n

回目に

1, 6

が出ればよいため

2 a_{n - 1, i - 1}

通りである。そうでないとき

n

回目の出目は一意に定まることから

6^{n - 1} - a_{n - 1, i - 1}

通りある。すなわち、

a_{n, i} = 6^{n - 1} + a_{n - 1, i - 1}

が成立する。ただし、

a_{n, - 1} = a_{n, 4}

とした。

n

が5の倍数でないとき、漸化式を繰り返し用いれば、

a_{n, 0} = 6^{n - 1} + 6^{n - 2} + 6^{n - 3} + . . . . . . + 6 + a_{1, i} = \sum_{k = 0}^{n - 1} 6^{k} = \frac{6^{n} - 1}{5}

を得る。

a_{1, i}

について、

i = 0, 2, 3, 4

のいずれかであることに留意せよ。場合の数の総数が

6^{n}

通りであることより、不適である。

n

が

5

の倍数のとき、同様の議論から以下を得る。

a_{n, 0} = \sum_{k = 1}^{n - 1} 6^{k} + a_{1, 1} = \frac{6^{n} + 4}{5}

よって、このとき題意を満たすことが分かるので求める条件は｢

n

が

5

の倍数であること｣である。

おわりに

ここまで読んで下さりありがとうございました。初めてこの手法を学ぶ方を想定して記事を作成したつもりです。記事を書くのが初めてなので、「ここの説明がわからない」などあれば教えて下さい。もちろん感想も大歓迎です。
今回取り上げた手法は私が競技数学を好きになったきっかけともいえるものです。いつか記事を書くときには題材はこれにしようと決めていました。少しでも面白いなと思って頂ければ幸いです。ではまた。

投稿日：2022年12月16日