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 の性質

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

性質1

各項の各桁は 1,2,31,2,3 のいずれかである。

証明

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

0 が現れないことの証明:

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

4 から 9 が現れないことの証明:

ana_n の奇数桁目に4以上の数字が現れたと仮定する。すると,an1a_{n-1} には同じ数字が4つ以上連続することになる。しかし, 偶数桁目に同じ数字が連続することは無い(注)ので,4つ以上連続になることは無い。よって ana_n の奇数桁に 4 は現れない。

さらに「0が現れないことの証明」と同じ理由により,偶数桁目に4以上の数字が現れないことも分かる。

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

性質2

桁数は単調非減少。つまり,ana_n の桁数を lnl_n とすると,lnln+1l_n\leqq l_{n+1}

証明

l1l2l_1\leqq l_2 はすぐ確認できる。

2項目以降は,lnl_n は偶数である。そして,さきほどの性質:

偶数桁目に同じ数字が連続することは無い

より,ana_n には 12ln\dfrac{1}{2}l_n 個以上の「aa 個の bb というブロック」が存在する。よって,1個のブロックに次の項の2桁が対応するので,

ln+1l_{n+1}12ln×2\dfrac{1}{2}l_n\times 2 以上である。

つまり,ln+1lnl_{n+1}\geqq l_n

性質3

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

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

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

性質4

limnln+1ln=λ\displaystyle\lim_{n\to\infty}\dfrac{l_{n+1}}{l_n}=\lambda

ただし,λ\lambda は定数で,およそ 1.301.30

つまり,十分大きな nn を持ってくると ln+1ln1.3\dfrac{l_{n+1}}{l_n}\fallingdotseq 1.3 というわけです。

性質4は,性質3よりも強いです。

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