武蔵野個別指導塾の特徴

大学入試数学数え上げの漸化式—末尾に必要な情報を残して禁止する並びの個数を求める｜武蔵野個別指導塾

公開 2026.11.15更新 2026.11.15武蔵野個別指導塾の特徴大学入試数学場合の数と確率の発展

隣り合う記号に制限がある列を末尾で分けて初期値から個数をたどる道具が、数え上げの漸化式です。

よくあるのは、高校生が連続する記号を禁じた列を、長さだけで更新しようとする場面です。たとえば2種類の記号を横に並べ、同じ印が続くことを一部で禁じると、今ある列の末尾によって次に置ける印が変わります。列の総数に一定の数を掛けても、各列から伸ばせる本数が同じとは限りません。

問われる形には、短い長さの個数を求めるもの、長さ n の個数の関係式を説明するもの、末尾の条件も加えて数えるものがあります。どれも、完成した列をどこで切るかが出発点です。ここでは有限の記号列の個数を扱い、確率には直しません。記号の位置は区別し、左右を逆にした列も、異なる並びなら別に数えます。

末尾に何を残すか

漸化式は、数列の項を前の項などで表す関係式です。たとえば aₙ が長さ n の列の個数なら、aₙ₊₁ を既に数えた列の個数で表します。ただし関係式だけでは最初の値が決まらないため、出発点となる初期値と、その式が成り立つ n の範囲も必要です。ここでは n は明記した範囲の整数で、個数は0以上の整数です。

印 A と B の列で AA を禁じるとします。図1のように末尾が A の列には B しか追加できませんが、末尾が B の列には A と B の両方を追加できます。したがって、総数を同じ倍率で更新することはできません。末尾を分ければ、それぞれの群で次に許される操作が決まります。

図1の矢印は、右端に記された印を1個追加する操作を表します。新しい列から最後の1個を消すと元の列が一意に戻るので、異なる元の列や異なる追加操作が同じ完成列になることはありません。また完成列の最後の印を消せば、必ず許された元の列に戻ります。この逆向きの確認が、重複も漏れもないという理由です。

末尾が A の個数を xₙ、B の個数を yₙ とすると、n が1以上で xₙ₊₁ = yₙ、yₙ₊₁ = xₙ + yₙ です。前者は B の後に A を置く方法、後者はどちらの末尾にも B を置く方法です。全体 aₙ = xₙ + yₙ とすると、aₙ₊₁ = aₙ + yₙ であり、n が2以上なら yₙ = aₙ₋₁ なので aₙ₊₁ = aₙ + aₙ₋₁ です。後者の等式は、長さ n-1 の許された列に B を付ける対応からも得られます。

長さ0の列を空列と呼び、1通りと約束すると、後の式を端まで揃えやすくなります。空列には末尾がないので、A 終わりや B 終わりのどちらにも含めません。空列を使わない方法でも答えは同じですが、初期値と関係式の範囲を混ぜないことが必要です。

状態は細かいほどよいわけではありません。次に置ける印が同じで、追加後にどの状態になるかも同じ列はまとめられます。一方、次の選択肢が違う列をまとめると更新の根拠を失います。たとえば AA だけでなく ABA も禁じる場合、末尾が A か B かだけでは、B の直前が A かどうかを区別できず、A を追加してよいか判定できません。必要なら末尾2個を記録します。

基本例題　最後の1個から戻る

【基本・標準】A、B の2種類を使い、AA が現れない長さ5の列を作ります。同じ記号は何度使ってもよく、各位置の並びを区別します。条件を満たす列の個数を整数で求めてください。

長さ n の個数を aₙ とし、空列を1通りとして a₀ = 1 とします。長さ1には A、B があるので a₁ = 2 です。長さ n が2以上の列を末尾で分けると、B 終わりは長さ n-1 の任意の許された列に B を付けたものです。A 終わりでは、その直前が必ず B なので、長さ n-2 の許された列に BA を付けたものです。

図2の2群は最後の印が異なるため重なりません。逆に、条件を満たす列は最後が A または B なので必ずどちらかに入り、付けた部分を取り除けば元の列が一意に定まります。長さ2の BA でも、取り除いた後は空列となるため、この分解が使えます。

a₀ = 1
a₁ = 2
aₙ = aₙ₋₁ + aₙ₋₂  （n は2以上）
a₂ = 2 + 1 = 3
a₃ = 3 + 2 = 5
a₄ = 5 + 3 = 8
a₅ = 8 + 5 = 13

答えは13通りです。実際に長さ3では、BBB、BBA、BAB、ABB、ABA の5通りです。長さ4の8通りに B を付ける8通りと、長さ3の5通りに BA を付ける5通りが、長さ5の条件を満たす列を過不足なく作ります。13という値を元の並びへ戻す確認にもなります。

標準例題　同じ印が続かない3種類

【標準・やや難】赤、青、緑の3種類の印を横に4個並べます。同じ色は繰り返し使えますが、隣り合う2個は異なる色とします。左右の位置を区別し、条件を満たす列の個数を整数で求めてください。

長さ n の個数を bₙ とします。長さ1では3通りで、任意の許された列の末尾には、その色以外の2色を追加できます。消去すると元の列と追加した色が一意に戻るため、n が1以上で bₙ₊₁ = 2bₙ です。

b₁ = 3
b₂ = 2・3 = 6
b₃ = 2・6 = 12
b₄ = 2・12 = 24

答えは24通りです。基本例題と違って、どの末尾にも追加できる色が2種類あるため、総数だけで更新できます。別の数え方では、左端を3通りに選び、以後の各位置を直前以外の2通りから選ぶので、3・2・2・2 = 24 です。最初の色ごとに8通りずつあり、どの列も隣接する色が異なることを確かめられます。

ただし末尾ごとに追加できる数が等しいだけでは、後に別の制限を課したときも総数で足りるとは限りません。たとえば最後を赤に指定するなら、全体から赤終わりの数を取り出す理由が要ります。この問題では色を入れ替えても条件が変わらないので、終わりの3色は同数で、それぞれ8通りです。

発展例題　2状態から3つ前の項へ

【発展・難】印 P、Q の列を作ります。P は隣り合ってはならず、さらに P と次の P の間には少なくとも2個の Q が必要です。Q は何個続いてもよく、同じ印を繰り返して使えます。長さ6の列の個数を整数で求めてください。

長さ n の許された列を cₙ とし、空列を c₀ = 1 とします。長さ1は Q、P の2通り、長さ2は QQ、QP、PQ の3通りです。長さ n が3以上の列を、最後が Q の群と P の群に分けます。Q 終わりは、長さ n-1 の許された列に Q を付ける cₙ₋₁ 通りです。

P 終わりは、その前の2個が QQ でなければなりません。末尾 QQP を取り除いた部分は任意の許された長さ n-3 の列です。元の末尾が P でも、間に2個の Q があるため新しい P と矛盾しません。逆に、QQP を付けると必ず条件を満たし、消せば元に戻るので cₙ₋₃ 通りです。

c₀ = 1
c₁ = 2
c₂ = 3
cₙ = cₙ₋₁ + cₙ₋₃  （n は3以上）
c₃ = 3 + 1 = 4
c₄ = 4 + 2 = 6
c₅ = 6 + 3 = 9
c₆ = 9 + 4 = 13

答えは13通りです。別解として P の個数で分けます。長さ6では P を3個置くには最短でも PQQPQQP の7個が必要なので、P は0個、1個、2個です。0個は1通り、1個は位置の選択が6通りです。2個の位置を i、j とすると、1 ≤ i、i + 3 ≤ j、j ≤ 6 で、i が1、2、3の場合に順に3、2、1通りです。合計は1 + 6 + 6 = 13通りとなり、列の位置に戻しても一致します。

この式は3つ前までを使う関係ですが、途中の項の係数が0であることを含めて考えると、最後の1個だけから更新する式ではありません。初期値3個が必要なのは、n = 3 から先を順に計算するためです。長さ2に QQP を付ける分解を無理に適用しないことも、成立範囲の確認に当たります。

誤答を分解して直す

基本例題で「A、B の2種類だから長さが1増えるごとに2倍」とし、長さ2を4通りとするのは誤りです。図3のように長さ1の A から AA と AB、B から BA と BB を作ると、AA は条件に反します。長さ2の正しい列は AB、BA、BB の3通りです。

図3の4候補は、元の末尾と付ける印を明示しているので、どの枝を除くか見えます。A 終わりの列の数を xₙ、B 終わりの列の数を yₙ とすれば、次の全体は xₙ + 2yₙ です。2(xₙ + yₙ) とした場合には、A 終わりからさらに A を付ける xₙ 通りを余分に数えています。

別の失敗は、末尾で分けた後に初期値を置き忘れることです。同じ関係式でも初期値が異なれば個数の列は異なります。また、長さ0を0通りとすると、基本例題の長さ2の BA に対応する元がなくなります。空列を使うと決めた場合は、その空列1通りがどの完成列に対応するかまで確かめてください。

さらに、許される完成列から末尾を消したものが必ず許されるか、逆に任意の元の列へ指定部分を付けて必ず許されるかを両方調べます。片方向だけでは、余計な列や数え漏れが残ることがあります。発展例題で末尾を QP としてしまうと、元の列が P 終わりの場合に PQP が混入するため、2個目の Q が必要です。

練習問題

各問では、列の左右の位置を区別し、同じ記号を何度使ってもよいものとします。答えはすべて整数の個数で示してください。

【標準】印 C、D を5個並べます。CC を含まない列のうち、最後が C のものは何通りですか。
【標準】丸、三角、四角の3種類の印を3個並べます。隣り合う印が異なる列は何通りですか。
【やや難】文字 E、F を4個並べます。EE と FF の両方を含まない列は何通りですか。
【やや難】印 G、H を5個並べます。G の間には少なくとも2個の H が必要です。条件を満たす列は何通りですか。
【難】印 J、K を6個並べます。JJ を含まず、J がちょうど2個ある列は何通りですか。

練習問題の解答

1. 最後の C の直前を調べる

長さ n の CC を含まない列の総数を uₙ とし、u₀ = 1、u₁ = 2 とします。D 終わりと DC 終わりに分けると、n が2以上で uₙ = uₙ₋₁ + uₙ₋₂ です。

u₂ = 2 + 1 = 3
u₃ = 3 + 2 = 5
u₄ = 5 + 3 = 8

長さ5で C 終わりなら直前は D です。先頭3個は任意の許された列なので、末尾に DC を付けて u₃ = 5 通りです。5個の元の長さ3の列から得られる DDD DC、DDC DC、DCD DC、CDD DC、CDC DC は、空白を境に前半と付加部分を表し、いずれも CC を含みません。逆に末尾 DC を消せば元に戻ります。

2. 直前と異なる印を付ける

長さ1では3通りです。以後は各列に、末尾以外の2種類を追加できます。

3・2 = 6
6・2 = 12

答えは12通りです。最初の印を固定すると、その次が2通り、最後もそれぞれ2通りの4通りです。最初の3種類で群は重ならず、12個の列を元の条件に戻して数えています。

3. 交互に置く

E 終わりには F、F 終わりには E しか追加できません。長さ1の E、F から、それぞれ1通りずつ延ばします。

長さ1の個数 = 2
長さ2の個数 = 2
長さ3の個数 = 2
長さ4の個数 = 2

答えは2通りです。実際の列は EFEF と FEFE です。先頭を決めた後の印は前の印と異なるものに定まるので、この2列以外はなく、両方とも EE と FF を含みません。

4. 最後の G に注目する

長さ n の個数を vₙ、空列を1通りとします。長さ1は2通り、長さ2は HH、HG、GH の3通りです。n が3以上では、H 終わりと HHG 終わりに分けます。

v₀ = 1
v₁ = 2
v₂ = 3
v₃ = v₂ + v₀ = 4
v₄ = v₃ + v₁ = 6
v₅ = v₄ + v₂ = 9

答えは9通りです。位置でも検算すると、G が0個は1通り、1個は5通り、2個は位置の組が (1,4)、(1,5)、(2,5) の3通りです。3個には少なくとも7位置が必要なので、1 + 5 + 3 = 9 と戻せます。

5. 個数と末尾を同時に記録する

長さ n で J が k 個あり、JJ を含まない列の総数を w(n,k) とします。最後が K なら長さ n-1 に J が k 個、最後が J なら直前は K で、長さ n-2 に J が k-1 個あります。n が2以上、k が1以上の範囲で、次の関係です。

w(n,k) = w(n-1,k) + w(n-2,k-1)
w(n,0) = 1  （n は0以上）
w(1,1) = 1
w(2,1) = 2
w(3,1) = 3
w(4,1) = 4
w(5,1) = 5
w(2,2) = 0
w(3,2) = 1
w(4,2) = 3
w(5,2) = 6
w(6,2) = 10

答えは10通りです。位置を直接数えて戻すと、最初の J の位置が1、2、3、4のとき、後の J の位置はそれぞれ4、3、2、1通りです。位置5や6を最初にすると、右側に隣接しない位置はありません。合計10組はすべて異なり、各組に J を置き残りを K にすると条件に合います。