最終更新:2019/05/04

Look-and-say sequence(見て言って数列)

分野: 数列  レベル: マニアック

この記事では,以下のような数列について考えます。
1, 11, 21, 1211, 111221, 312211, $\dots$
面白い性質と規則性を持った数列です。

Look-and-say sequence

さきほどの数列は,以下のような規則性があります。

初項は1

1 は 1 個の 1
なので,第2項は 11

11 は 2 個の 1
なので,第3項は 21

21 は 1 個の 21 個の 1
なので,第4項は 1211

1211 は 1 個の 11 個の 22 個の 1
なので,第5項は 111221

このように,前の項の個数と数字を順番に読んで次の項を作った数列のことを Look-and-say sequence と言います。強引に日本語訳すると「見て言って数列」でしょうか。

Look-and-say sequence の性質

以下では,初項が $1$ である Look-and-say sequence $a_n$ の性質を見ていきます。

性質1:
各項の各桁は $1,2,3$ のいずれかである。

証明

第2項以降は,左から奇数桁目が「数字の個数」を表し,偶数桁目は「前の数字に現れる数字」を表す。

0 が現れないことの証明:
奇数桁目は「数字の個数」を表すので 0 は現れない。また,偶数桁目は「前の数字に現れる数字」を表すので,0 が現れたとすると,1つ前の項にも 0 が現れる。これを繰り返すと,さかのぼって $a_1$ にも 0 が現れる必要があるが,そうではないので 0 は現れない。

4 から 9 が現れないことの証明:
$a_n$ の奇数桁目に4以上の数字が現れたと仮定する。すると,$a_{n-1}$ には同じ数字が4つ以上連続することになる。しかし,偶数桁目に同じ数字が連続することは無い(注)ので,4つ以上連続になることは無い。よって $a_n$ の奇数桁に 4 は現れない。
さらに「0が現れないことの証明」と同じ理由により,偶数桁目に4以上の数字が現れないことも分かる。

注:$abcb$ のように偶数桁目に同じ数字 $b$ が連続することはありません。$a$ 個の $b$$c$ 個の $b$ は,まとめて $(a+c)$ 個の $b$ と言うべきだからです。

性質2:
桁数は単調非減少。つまり,$a_n$ の桁数を $l_n$ とすると,$l_n\leq l_{n+1}$

証明

$l_1\leq l_2$ はすぐ確認できる。

2項目以降は,$l_n$ は偶数である。そして,さきほどの性質:
偶数桁目に同じ数字が連続することは無い
より,$a_n$ には $\dfrac{1}{2}l_n$ 個以上の「$a$ 個の $b$ というブロック」が存在する。よって,1個のブロックに次の項の2桁が対応するので,
$l_{n+1}$ は $\dfrac{1}{2}l_n\times 2$ 以上である。
つまり,$l_{n+1}\geq l_n$

性質3:
桁数は無限大に発散する。つまり,$\displaystyle\lim_{n\to\infty}l_n=\infty$

性質1や性質2の証明よりは少しだけ難しいですが,頑張ればできます。考えてみてください!

ちなみに,初項が 1 ではなく 22 である Look-and-say sequence はいつまでも 22 を繰り返します。

性質4:
$\displaystyle\lim_{n\to\infty}\dfrac{l_{n+1}}{l_n}=\lambda$
ただし,$\lambda$ は定数で,およそ $1.30$

性質4は,性質3よりも強いです。性質4の証明は,私も知りません。

参考:Look-and-say sequence

英語では「two 1s」ですが,日本語では「2個の1」と言うよりも「1が2個」と言いたくなる気もします。