3

加算と2倍のレパートリーのなす数の総数

106
0
$$$$

はじめに

はじめまして、シェーマと申します。
いつかMathlogに記事を書きたいなと思っていたら、面白そうな問題を見つけたので、記事を書く練習がてら考えてみようと思いました。
先日 ぱぺさん の投稿した 【問題提起】加算と2倍のレパートリー という記事において、下記の問題が提示されています。

整数1に対して、以下の2つの操作を計$n$回 (操作$A$のみを$n$回、操作$B$のみを$n$回も可)だけ行ったとき、その計算結果としてあり得る整数の個数を$n$で表せ。

【操作】

  • 操作$A$「1を加える」
  • 操作$B$「2倍する」

$n$回の操作でできる整数からなる集合を$S_n$、その要素数を$a_n$とおくと、定義から
$S_1 = \lbrace 2 \rbrace, S_{n+1} = \lbrace x+1,2x|x \in S_n \rbrace $
が成り立ちます。
この問題は$a_n$の一般項を求めよ、ということですね。

$S_n$の例

$S_1= \lbrace 2 \rbrace $
$S_2= \lbrace 3,4 \rbrace $
$S_3= \lbrace 4,5,6,8 \rbrace$
$S_4= \lbrace 5,6,7,8,9,10,12,16 \rbrace$

執筆時点で元の記事にはコメントにて nissyさん が先に一般項を求めておられましたが、別のアプローチを紹介したいと思います。

自然数の結合と重み付き和

唐突ですが、次の概念を考えます。

自然数の結合

自然数からなる組$\left( x_1, x_2, \cdots, x_k \right)$$ \displaystyle \sum_{i=1}^{k}x_i=n$を満たすとき、この組$\left( x_1, x_2, \cdots, x_k \right)$自然数$n$の結合という。また、自然数$n$の結合のなす集合を$\overline{X}_n$とおく。

この「結合」という名称が正式なものかはわかりませんが、「composition」の直訳です。

重み付き和

重み付き和$p: \overline{X}_n \rightarrow \mathbb{N} $
$\displaystyle p:(x_1,x_2, \cdots, x_k) \mapsto \sum_{i=1}^{k} 2^{i-1}x_i$
で定め、その像を$X_n$とおく。

いくつか具体例を見てみましょう。

$\overline{X}_n$$X_n$の例

$\overline{X}_1= \lbrace (1) \rbrace , \quad X_1=\lbrace 1 \rbrace$
$\overline{X}_2= \lbrace (2), (1,1) \rbrace , \quad X_2=\lbrace 2,3 \rbrace$
$\overline{X}_3= \lbrace (3),(2,1),(1,2),(1,1,1) \rbrace , \quad X_3=\lbrace 3,4,5,7 \rbrace$
$\overline{X}_4= \lbrace (4),(3,1),(2,2),(1,3),(2,1,1),(1,2,1),(1,1,2),(1,1,1,1) \rbrace ,$
$X_4=\lbrace 4,5,6,7,8,9,11,15 \rbrace$

$S_n$$X_n$の関係

さて、$S_n$$X_n$の例を見比べた方の中にはお気づきの方もいらっしゃるでしょうが、$S_n$$X_n$の間には次のような関係が存在します。

$S_n$$X_n$の間には次のような全単射が存在する。
$X_n \rightarrow S_n,\quad x \mapsto x+1$

この事実を証明する前に、次の補題を用意します。

$X_n$の帰納的定義

$X_n$は次のように帰納的に構成される。
$X_1=\lbrace 1 \rbrace, \quad X_{n+1} = \lbrace x+1, 2x+1 | x \in X_n \rbrace$

$\overline{X}_{n+1}$の元は、$\overline{X}_n$の元$(x_1, x_2 \cdots, x_k)$から次の2通りで構成されます。

  1. $(x_1+1,x_2, \cdots, x_k)$
  2. $(1,x_1, x_2, \cdots, x_k)$

この構成法により$\overline{X}_{n+1}$の元は全てつくされます。
この操作を$X_n, X_{n+1}$で考えると、(1)は$x+1$、(2)は$2x+1$に対応しています。これにより、補題が示されます。

では定理1を証明していきましょう。

定理1

数学的帰納法で証明します。
$n=1$のとき、$X_1=\lbrace 1\rbrace, S_1=\lbrace 2\rbrace$より明らかです。
$n$のときに成り立つと仮定し、$n+1$のときを考えます。
補題1より、$X_{n+1}$の元$y$$X_n$の元$x$を用いて$x+1$または$2x+1$と表されます。
帰納法の仮定より、$x+1$$S_n$の元です。これにより、$x+2$$2x+2$$S_{n+1}$の元です。
$x+2=(x+1)+1,\ 2x+2=(2x+1)+1$
であるため、$X_{n+1} \rightarrow S_{n+1}, \ y \mapsto y+1$は全単射を与えることがわかります。
以上より、任意の$n$について主張が示されました。

定理1

$X_n$の要素数は$a_n$に等しい。

これにより、$a_n$を考察する際に$\overline{X_n}$$X_n$を用いることができるようになります。

$a_n$の計算

では実際に$a_n$を求めていきます。
そのために次の漸化式を証明しましょう。

$a_n$の漸化式

$a_1 = 1, a_2 = 2, a_n = a_{n-1} + a_{n-2} + n-2 \ (n \geq 3)$

$n=1,2$のときは明らかです。
$n \geq 3$のときを考えます。そのために$\overline{X}_n$を次の3つに分解します:
$(x_1, \cdots, x_k)$$\overline{X}_n$の元としたとき、
(1) $x_1=1$である元全体の集合。これは$(1, \boldsymbol{x}), \boldsymbol{x} \in \overline{X}_{n-1}$と表されるため、$\overline{X}_{n-1}$の元と1対1対応があります。
(2) $x_1=2$である元全体の集合。これは$(2, \boldsymbol{x}), \boldsymbol{x} \in \overline{X}_{n-2}$と表されるため、$\overline{X}_{n-2}$の元と1対1対応があります。
(3) $x_1 \geq 3$である元全体の集合$\overline{Y}_n$
これにより$X_n$の元は$\overline{X}_{n-1},\overline{X}_{n-2},\overline{Y}_n$の3つの集合の元から構成されることがわかります。

$\overline{X}_n$の分解法から、$X_n$の元において$\overline{X}_{n-1}$由来の元は$X_{n-1} \rightarrow X_n, \ x \mapsto 2x+1$$\overline{X}_{n-2}$由来の元は$X_{n-2} \rightarrow X_n, \ x \mapsto 2x+2$で与えられます。
前者は奇数、後者は偶数であるため、これらの像に重複する数字は存在しません。
つまり$X_n$の元のうち、$\overline{X}_{n-1}$からくる元は$a_{n-1}$個、$\overline{X}_{n-2}$からくる元は$a_{n-2}$個存在することがわかりました。
後は$\overline{Y}_n$からくる元のうち、重複しない元が$n-2$個であることを示せば終了です。

さて$\overline{Y}_n$をさらに次の2つに分解します:
$(y_1, \cdots, y_k)$$\overline{Y}_n$の元としたとき、
[1] $k=1,2$の元全体からなる集合$\overline{Y}^1_n$
[2] $k \geq 3$の元全体からなる集合$\overline{Y}^2_n$

前者は$\overline{Y}^1_n = \lbrace (n),(3,n-3),\cdots, (n-1,1) \rbrace$であり、全部で$n-2$個の元からなります(ただし、$n=3$のときは$(3)$$(3,0)$を同一視します)。
この集合からくる$X_n$の元は、$\overline{X}_{n-1},\overline{X}_{n-2}$由来の元と重複しません。
なぜなら$\overline{Y}^1_n$の重み付き和による像$Y^1_n$$Y^1_n = \lbrace n, n+1,\cdots , 2n-3\rbrace$であり、最大の数は$2n-3$です。
一方$X_{n-2}$の最小の数は$n-2$であるため、$\overline{X}_{n-2}$由来の元の最小値は$2n-2$です。
これにより$X_n$の元のうち、$\overline{Y}^1_n$由来の元が$n-2$個存在することがわかりました。

最後に$\overline{Y}^2_n$由来の元は、全て$\overline{X}_{n-1},\overline{X}_{n-2}$由来の元と重複することを示します。
それは次の等式から示されます:
$(x_1, \cdots, x_k) \in \overline{X}_n,\ x_1 \geq 3$に対し、
$x_1 + 2x_2 + 4x_3 = (x_1-2) + 2(x_2 + 3) + 4(x_3 - 1)$
$$x_1 + 2x_2 + \sum^{k-2}_{i=3}2^{i-1}x_i + 2^{k-2}x_{k-1} + 2^{k-1}x_k = (x_1-2) + 2(x_2 + 1) + \sum^{k-2}_{i=3}2^{i-1}x_i + 2^{k-2}(x_{k-1}+2) + 2^{k-1}(x_k -1)$$
が成り立つため、$(x_1, x_2, x_3)$$(x_1-2, x_2 +3, x_3 -1)$$(x_1, x_2, \cdots, x_{k-1}, x_k)$$(x_1 - 2, x_2 + 1, \cdots, x_{k-1} + 2, x_k - 1)$の重み付き和はそれぞれ等しくなります。
つまり$k \geq 3, x_1 \geq 3$であるとき、この操作を繰り返すことによって重み付き和の値が等しい$x_1 = 1$または$x_1 = 2$である$\overline{X}_n$を見つけることができます。
このことは$\overline{Y}^2_n$由来の元は全て$\overline{X}_{n-1},\overline{X}_{n-2}$由来の元と重複することを意味します。

以上より、$X_n$の元は$\overline{X}_{n-1},\overline{X}_{n-2},\overline{Y}^1_n$からくる元で全てつくされるため、$a_n = a_{n-1} + a_{n-2} + n-2 \ (n \geq 3)$が示されました。

最後にこの漸化式を解いていきましょう。

まず階差数列$b_n = a_{n+1} - a_n$を考えると、
$b_1 = 1, b_2 = 2, b_n = b_{n-1} + b_{n-2} +1 \ (n \geq 3)$
が成り立ちます。
最後の式は
$b_n + 1 = (b_{n-1} + 1) + (b_{n-2} + 1)$
と変形できます。これはフィボナッチ数列の漸化式と同じものです。
さらに$b_1 + 1 = 2 = \mathrm{Fibonacci}(3), b_2 + 1 = 3 = \mathrm{Fibonacci}(4)$であることから、
$b_n = \mathrm{Fibonacci}(n+2)-1$
となります。
よって、
\begin{eqnarray} a_n &=& \sum^{n-1}_{i=1}(\mathrm{Fibonacci}(i+2)-1 ) + a_1\\ &=& \mathrm{Fibonacci}(n+3) - 1 - \mathrm{Fibonacci}(1) - \mathrm{Fibonacci}(2) - (n-1) + 1 \\ &=& \mathrm{Fibonacci}(n+3) - (n + 1) \end{eqnarray}
が導かれます(途中で$\displaystyle \sum^m_{i=1} \mathrm{Fibonacci}(i) = \mathrm{Fibonacci}(m+2) - 1$の公式を使いました)。
これは$a_1 = \mathrm{Fibonacci}(4) - (1 + 1) = 1$より$n=1$のときも成り立っています。

$a_n$の一般項

\begin{eqnarray} a_n &=& \mathrm{Fibonacci}(n+3) - (n + 1) \\ &=& \frac{1}{\sqrt{5}} \left\lbrace \left(\frac{1+\sqrt{5}}{2} \right)^{n+3} - \left( \frac{1-\sqrt{5}}{2} \right)^{n+3} \right\rbrace - (n + 1) \end{eqnarray}

終わりに

はじめての記事でしたが、いかがでしたでしょうか。$a_n$の数え方にはフィボナッチ数列が関係していなさそうなのに、一般項にはフィボナッチ数列が出てくるところが面白いですね。
最後におまけとして、唐突に出てきた自然数の結合やその重み付き和はどこから考えたのかを簡単に書いておきたいと思います。こちらは読みたい方だけどうぞ。それでは。

おまけ

クリックして詳細をチェック

まずこの問題を考えるにあたって、いくつか計算してみようと思いました。
ただ、$n$が大きくなると計算する$A, B$の組み合わせが多くなるため、面倒だなと。
そこで$AB = BAA$の関係式を使い、$B$を全て左に持っていって$B^kA^l$の形に持っていけば計算が多少楽になるのでは、と考えたわけです(ここでは$A, B$を自然数への右作用とみなしています)。
ではどうやって$A, B$の組み合わせを$B^kA^l$の形に持っていくのか。
その初めの一歩として
$ABAAB \longleftrightarrow (2,5)$
$BBABA \longleftrightarrow (1,2,4)$
というように、左から数えて何番目に$B$があるのか、という対応を考えます。
この対応で得られる組を$(c_1, c_2, \cdots, c_k)$とおいたとき、これはどのような演算に対応するのでしょうか。
$AB = BAA$の関係式から、$B$$A$の順番を入れ替えると$A$の数が2倍になることがわかります。
つまり$B$を左に入れ替えていくと、その$B$よりも左にある$A$の数が2倍になって右に行くことになります。
$(c_1, c_2, \cdots, c_k)$において、$c_1$番目の$B$より左には$c_1-1$個の$A$があり、それは入れ替えをすることで右に$2(c_1-1)$個の$A$が並びます。
$c_1$番目の$B$$c_2$番目の$B$の間には$c_2-c_1-1$個の$A$がもともとあるため、全部で$2(c_1-1) + (c_2-c_1-1)$個の$A$が並んでいるわけです。
これらの$A$$c_2$番目の$B$を入れ替えていくことで$4(c_1-1) + 2(c_2-c_1-1)$個の$A$になります。
以上の操作を繰り返すことで、$A,B$$n$回作用させるとき、$(c_1, c_2, \cdots, c_k)$と同じ操作を与える作用は
$$B^kA^l, l = \sum^{k+1}_{i=1}2^{k-i+1}(c_i - c_{i-1}-1), \ (c_0 = 0, c_{k+1} = n + 1 ) $$
となります。
これにより、2に$A,B$$n-1$回作用させるとき、その作用が$(c_1, c_2, \cdots, c_k)$に対応しているとすると、
\begin{eqnarray} 2^{k+1} + \sum^{k+1}_{i=1}2^{k-i+1}(c_i - c_{i-1}-1) &=& 2^{k+1} + \sum^{k+1}_{i=1}2^{k-i+1}(c_i - c_{i-1}) - (2^{k+1} - 1) \\ &=& \sum^{k+1}_{i=1}2^{k-i+1}(c_i - c_{i-1}) + 1 \end{eqnarray}
が得られることがわかります。
最後のシグマ記号の中身を見てみると、
$c_i - c_{i-1} \geq 1, \ \sum^{k+1}_{i=1}(c_i-c_{i-1}) = c_{k+1} - c_0 = n$
であることから、
$(c_1, c_2, \cdots, c_k) \longleftrightarrow (c_1, c_2 - c_1, \cdots, c_k - c_{k-1}, n - c_k)$
という対応で自然数$n$の結合が得られます。
そして作用の計算結果は重み付き和となっています。
これらの概念はこうやって思いついたということですね。
以上、おまけでした。

投稿日:617
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

昔大学で数学をしていた人

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中