「部分列って部分集合と何が違うの？」 「数列の問題で部分列が出てきたけど、よく分からない」 「プログラミングでも部分列って出てくるけど、同じ意味？」
こんな疑問を持っていませんか？
部分列（subsequence）は、元の並びから、順序を保ったまま要素を取り出したものです。 一見簡単そうですが、実は数学の様々な分野で重要な役割を果たす概念なんです。
この記事では、部分列の基本から、部分集合との違い、実際の問題での活用まで、具体例たっぷりで解説します。 もう部分列で悩むことはありません！
部分列の基本定義
部分列とは何か
部分列とは、ある数列から、いくつかの項を順序を変えずに取り出してできる数列のことです。
重要なポイント：
- 元の順序は必ず保つ
- 連続している必要はない
- 元の数列自身も部分列
- 空列も部分列
具体例で理解しよう
元の数列：1, 2, 3, 4, 5
この数列の部分列の例：
✓ 1, 3, 5（飛び飛びでもOK）
✓ 2, 4（連続していなくてもOK）
✓ 1, 2, 3, 4, 5（全部でもOK）
✓ 3（1つだけでもOK）
✓ （空列でもOK）
✗ 3, 1（順序が逆はNG）
✗ 2, 6（元にない要素はNG）
数式での表現
元の数列を A = (a₁, a₂, a₃, …, aₙ) とすると、 部分列 B = (aᵢ₁, aᵢ₂, …, aᵢₖ) は以下を満たす：
1 ≤ i₁ < i₂ < … < iₖ ≤ n
つまり、添字（インデックス）が増加する形で選ばれています。
部分列と部分集合の違い
決定的な違い：順序の有無
これ、よく混同されるので要注意です！
| 概念 | 順序 | 重複 | 例（元：1,2,3） |
|---|---|---|---|
| 部分列 | 重要 | あり得る | (1,3), (2,2,3)※ |
| 部分集合 | 無関係 | なし | {1,3}, {2,3} |
※元の数列に同じ数が複数ある場合
具体例で比較
元のデータ：[1, 2, 2, 3]
部分列の例：
- [1, 2, 3] ✓（最初の2を選択）
- [1, 2, 3] ✓（2番目の2を選択、別の部分列）
- [2, 2] ✓（両方の2を選択）
- [3, 2] ✗（順序が逆）
部分集合の例：
- {1, 2, 3} ✓（重複は1つとして扱う）
- {2} ✓
- {2, 2} ✗（集合では重複なし）
なぜこの違いが重要？
部分列が使われる場面：
- 時系列データの分析
- DNAの配列解析
- 文字列のパターンマッチング
部分集合が使われる場面：
- 組み合わせの計算
- 集合演算
- データベースの検索
部分列の種類と性質
連続部分列（部分文字列）
連続部分列とは、連続した要素だけを取り出したものです。
元の数列：1, 2, 3, 4, 5
連続部分列：
- 1, 2, 3 ✓
- 3, 4 ✓
- 2, 3, 4, 5 ✓
通常の部分列だが連続でない：
- 1, 3, 5 ✗
- 2, 5 ✗
プログラミングでは「substring」と呼ばれることも。
増加部分列・減少部分列
単調増加部分列： 後の項が前の項より必ず大きい
元の数列：3, 1, 4, 1, 5, 9, 2, 6
増加部分列の例：
- 1, 4, 5, 9
- 3, 4, 5, 6
- 1, 2, 6
単調減少部分列： 後の項が前の項より必ず小さい
同じ数列から：
- 3, 1
- 9, 2
- 4, 1
最長増加部分列（LIS）
与えられた数列の中で、最も長い増加部分列を見つける問題です。
数列：10, 9, 2, 5, 3, 7, 101, 18
最長増加部分列：2, 3, 7, 101
長さ：4
これはアルゴリズムの重要な問題の1つ！
部分列の個数を数える
基本的な数え方
n個の要素を持つ数列の部分列の総数は 2ⁿ個 です。
なぜ2ⁿ個？ 各要素について「選ぶ」か「選ばない」の2通りがあるから。
数列：a, b, c（3要素）
部分列の総数：2³ = 8個
1. （空列）
2. a
3. b
4. c
5. a, b
6. a, c
7. b, c
8. a, b, c
条件付き部分列の数
長さkの部分列の個数： nCk（n個からk個を選ぶ組み合わせ）
数列：1, 2, 3, 4（4要素）
長さ2の部分列の個数：
4C2 = 4!/(2!×2!) = 6個
実際の部分列：
1,2 1,3 1,4 2,3 2,4 3,4
実際の問題で部分列を使う
例題1：部分列の判定
問題： 数列A = [1, 3, 5, 7, 9]に対して、 B = [3, 7]は部分列か？
解答：
A: 1, 3, 5, 7, 9
↑ ↑
B: 3, 7
3と7が順序を保って存在する → Yes、部分列です
例題2：共通部分列
問題： 2つの数列の共通部分列を見つける
数列X：1, 2, 3, 4, 5
数列Y：2, 3, 5, 6
共通部分列の例：
- 2
- 3
- 5
- 2, 3
- 2, 5
- 3, 5
- 2, 3, 5（最長共通部分列）
例題3：回文部分列
問題： 回文（前から読んでも後ろから読んでも同じ）になる部分列を見つける
数列：a, b, c, b, a
回文部分列：
- a, b, a
- a, c, a
- b, c, b
- a, b, b, a
- a, b, c, b, a（全体）
プログラミングでの部分列
文字列の部分列
プログラミングでは、文字列でよく使われます。
# Pythonでの例
文字列 = "HELLO"
部分列の例：
- "HLO"（H, L, O を選択）
- "ELL"（E, L, L を選択）
- "HE"（H, E を選択）
# 部分文字列（連続）との違い
部分文字列："HEL", "ELL", "LLO"など
部分列："HLO", "EO", "HL"なども含む
動的計画法での活用
最長増加部分列（LIS）を求めるアルゴリズム：
配列：[10, 9, 2, 5, 3, 7, 101, 18]
処理の流れ：
1. 各位置での最長の長さを記録
2. 前の要素より大きければ+1
3. 最大値が答え
結果：[1, 1, 1, 2, 2, 3, 4, 4]
答え：4（長さ4の増加部分列が最長）
部分列に関する重要な定理
エルデシュ・シェケレスの定理
定理： 長さn²+1以上の数列には、必ず長さn+1以上の増加部分列または減少部分列が存在する。
例：
n = 2の場合：
長さ5（2²+1）の数列には、
長さ3以上の増加または減少部分列が必ず存在
数列：3, 1, 4, 2, 5
増加部分列：1, 2, 5（長さ3）✓
ディルワースの定理
数列を単調列に分解する際の最小個数に関する定理。 これは順序集合論で重要な役割を果たします。
応用分野での部分列
バイオインフォマティクス
DNA配列の解析：
DNA1: ACTGACCT
DNA2: AACCTTGG
最長共通部分列：ACCTT
→ 遺伝的な類似性の指標
データ圧縮
繰り返しパターンの検出：
元データ：ABCABCABC
部分列パターン：ABC
→ 効率的な圧縮が可能
時系列分析
株価の傾向分析：
株価：100, 95, 102, 98, 105, 103, 110
増加部分列：95, 98, 103, 110
→ 上昇トレンドの把握
よくある間違いと注意点
間違い1：順序を無視する
❌ 間違い：
元：1, 2, 3
部分列として 3, 1 を選ぶ
✅ 正しい： 順序は必ず保つ！1, 3 ならOK
間違い2：連続性を要求する
❌ 間違い： 「部分列は連続していないといけない」
✅ 正しい： 飛び飛びでもOK！それが部分列の特徴
間違い3：重複を見落とす
元の数列：1, 2, 2, 3
部分列 [1, 2, 3] は2通りある：
- 1番目の2を使う場合
- 2番目の2を使う場合
数え方に注意！
練習問題
問題1（基礎）
数列 [2, 4, 6, 8] の部分列をすべて列挙せよ。
解答：
空列：[]
長さ1：[2], [4], [6], [8]
長さ2：[2,4], [2,6], [2,8], [4,6], [4,8], [6,8]
長さ3：[2,4,6], [2,4,8], [2,6,8], [4,6,8]
長さ4：[2,4,6,8]
合計：2⁴ = 16個
問題2（応用）
数列 [3, 1, 4, 1, 5] の最長増加部分列を求めよ。
解答：
可能な増加部分列：
- [1, 4, 5]（2番目の1から）
- [1, 5]（4番目の1から）
- [3, 4, 5]
最長：[1, 4, 5] または [3, 4, 5]
長さ：3
問題3（発展）
2つの文字列 “ABCDGH” と “AEDFHR” の最長共通部分列を求めよ。
解答：
ABCDGH
A D H
AEDFHR
A D H
最長共通部分列：ADH
長さ：3
まとめ：部分列マスターへの道
部分列について、重要なポイントをまとめます：
部分列とは：
- 📝 元の順序を保って要素を選んだもの
- 🔢 連続している必要はない
- ↗️ 順序が最重要！
部分集合との違い：
- 部分列：順序あり、重複考慮
- 部分集合：順序なし、重複なし
重要な性質：
- n要素の数列 → 2ⁿ個の部分列
- 増加/減少部分列の存在
- 最長共通部分列問題
応用分野：
- プログラミング（文字列処理）
- バイオインフォマティクス（DNA解析）
- データ分析（パターン認識）
学習のコツ：
- 具体例で考える
- 順序を意識する
- 図を描いて確認
部分列は一見単純ですが、数学やコンピュータサイエンスの様々な場面で登場する重要な概念です。 この記事で学んだ基礎をしっかり理解して、より高度な問題にも挑戦してみてください！
コメント