部分列の定義・イメージや具体例について
1. 部分列とは
部分列を作る際には、元の列における要素の順序を変えずに抜き出す必要がありますが、抜き出す要素が連続している必要はありません。
1.1. 部分列のイメージ
例えば、元の列が \( a_1, a_2, a_3, a_4 \) であるとき、次のようなものが部分列になります。
- \( a_1, a_2, a_3 \)（元の列の最初から3つの要素をそのまま使った部分列）
- \( a_2, a_4 \)（元の列から \( a_2 \) と \( a_4 \) を抜き出した部分列）
- \( a_1, a_4 \)（元の列から \( a_1 \) と \( a_4 \) を抜き出した部分列）
- \( a_3 \)（元の列から \( a_3 \) だけを抜き出した部分列）
一方、元の列が \( a_1, a_2, a_3, a_4 \) の場合、 \( a_3, a_1 \) は部分列ではありません。これは、 \( a_3 \) が \( a_1 \) よりも元の列で後に現れるためです。
2. 部分列と漸化式
2.1. フィボナッチ数列の部分列
フィボナッチ数列は、次のような漸化式で定義されます。
\[ a_n = a_{n-1} + a_{n-2} \quad (n \geq 3) \]
初期条件は \( a_1 = 1 \) および \( a_2 = 1 \) です。
例えば奇数番目の項のみを考えてみましょう。フィボナッチ数列の部分列 \( b_n = a_{2n-1} \) を定義します。この部分列は次のようになります。
\[ b_1 = a_1 = 1, \quad b_2 = a_3 = 2, \quad b_3 = a_5 = 5, \quad b_4 = a_7 = 13, \ldots \]
このように、元の漸化式の奇数番目の項を取り出した部分列ができました。
一方で、平方数の部分列を考えるます。フィボナッチ数列の部分列 \( b_n = a_{n^2} \) を定義します。この部分列は次のようになります。
\[ b_1 = a_1 = 1, \quad b_2 = a_4 = 3 \ldots \]
2.2. 部分列でない場合
例えば、フィボナッチ数列の一部を逆順に並べた数列を考えます。
\[ \{a_n\} = \{1, 1, 2, 3, 5, 8, \ldots\} \]
を
\[ \{b_n\} = \{8, 5, 3, 2, 1, 1, \ldots\} \]
と並べ替えた場合、これは元の数列の部分列とは言えません。
3. 部分列と写像
\[ b_m = a_{f(m)} \]
ここで、写像 \( f \) は以下の2つの条件を満たします。
- \( f(m) < f(m+1) \) である。
- \( f(m) \) は自然数である。
このような写像 \( f \) を使って部分列を定義することで、元の数列の中から順序を保ちながら特定の項を選び出すことができます。
