★Beat Angels

前途は遠かった。でもそれはどうでもいい。道こそが人生だからだ。 - Jack Kerouac

神田川数列(最終回)

問題をあらためてここに整理する。

 f:id:taamori1229:20200521172226p:plain

mxnの格子に対して、1x2の畳を敷き詰める。畳は縦長、横長のいずれでも構わない。敷き詰めるすべての方法の数を求めることである。当然、m、nの両方が奇数の場合は、必ず1つあまりが出てしまうので、0となる。

全体を俯瞰していい方法が見当たらなかったので、地道ではあるがmの値を1から順に計算していって全体の流れから一般式を見い出す作戦とした。


まずm=1の場合、畳は横長に並べてるしかない。nが奇数の場合は、余りがでてしまうので0である。nが偶数の場合だけ1となる。これを漸化式として表現すると、

 f:id:taamori1229:20200521173324p:plain

となる。nが2つ飛びであることに注意を要する。

次にm=2の場合は、畳は縦に一つ置く、横に2つ並べて置く、の2通りを順次繰り返していくことになる。これは有名なフィボナッチ数列であり漸化式は、

 f:id:taamori1229:20200521173917p:plain

である。続いてm=3の場合である。これについては前回までに示したように、縦横の組み合わせパターンに分類してパターンごとの漸化式を作成しそれらを統合してくことで求められる。

 f:id:taamori1229:20200521174435p:plain

ここでもm=1の場合で見られたように、2つ飛びの漸化式となる。これがmが奇数の場合の特徴である。nが奇数の項ではとびとびに0となる。

続いてm=4の場合、これもさらに複雑な計算の結果、

 f:id:taamori1229:20200521174732p:plain

が得られた。mが偶数なので隣接の漸化式である。n-4の項まで登場した。

さらにm=5。苦しい計算の結果、

 f:id:taamori1229:20200521175050p:plain

となった。mが奇数なので2つ飛びである。

m=6の場合についても非常に煩雑な計算の末に、

 f:id:taamori1229:20200521175338p:plain

体力的にはここまでが限界である。

以上の結果を数表の形で示すと下表のようになる。

 f:id:taamori1229:20200521181403p:plain

m、nについては交換しても数字が変わらないことを利用してm=7,8もある程度は記入することができる。

4x4が36通りというのはなんとなくわかるが、6x6になると6千通りを超えるという事実がどうにも信じられない。8x8の場合は求められていないが100万通りをはるかに超える。この表を見ていても数字の規則を見つけられそうにない。そこで漸化式の形に着目して規則を見出すことにした。漸化式を=0の形で表現して登場する係数を並べたものが下表である。(m=7、8は類推)

f:id:taamori1229:20200521182211p:plain

漸化式の中心の項を縦方向に並べてみる。

f:id:taamori1229:20200521182810p:plain

これで見えてくるのは、

 (1) 漸化式の項数はmの増加に従って、指数関数的に増加する。
 (2) 漸化式の係数は中央の項からみて前後に対称である。
 (3) 特に最初と最後の項の係数は1かー1である。

本表をもう少し見通しをよくするために上記の隣接項表記から、つまり2つ飛び表記したらどうかを検討した。

一般に隣接する項による漸化式は所定の手続きで2項飛びの表記に変換が可能である。

その原理をm=2の場合(フィボナッチ数列)を例に示す。

 f:id:taamori1229:20200521195008p:plain

このように元の漸化式を項をずらしたものに所定の値を掛けたものを複数足し合わせることで、2つ飛びの漸化式に変換可能である。これを用いて上の表を書き直したものを下表に示す。

f:id:taamori1229:20200521194634p:plain

こうして漸化式の進化の規則についてその概要を明らかにすることができた。しかし、本表に登場する数字の規則性についてはまだまだ藪の中である。m=7以上で漸化式を求めることは非常に困難であるためこの手法の解析はここまでとして、今後、全く異なるアプローチの登場を待つしかない

神田川数列(その3)

性懲りもなく前回の続きである。縦方向を3から4にしてみたらどうなるだろうか。題意からは大きく外れるが。2列の基本形における敷き詰め方は、


 f:id:taamori1229:20200505091555p:plain
この5通りである。次に横4列(=8畳)の場合はどうなるか。

 f:id:taamori1229:20200505091623p:plain
すべてが横長、すべてが縦長の場合はそれぞれ1通りずつと単純明快なのだが縦横が入り乱れると途端に複雑さを増す。数えてみると36通りである。

さてこれを2n列並べた一般的な場合を考える。

 f:id:taamori1229:20200505091729p:plain
4n枚の畳の敷き詰め方をnの一般式として表すのが目的である。

前回同様の漸化式のアプローチをとる。右端に着目すると次の6パターンが存在する。

 f:id:taamori1229:20200505093202p:plain

 f:id:taamori1229:20200505093230p:plain

 f:id:taamori1229:20200505093245p:plain

 f:id:taamori1229:20200505093309p:plain

 f:id:taamori1229:20200505093324p:plain

 f:id:taamori1229:20200505093341p:plain 

それぞれの系列をK、Y、S、T、U、Wという6つの系列で表す。今回求めたいのはこの中のK系列である。図において、×をつけたのは複数のパターンが存在することを示していてその数を系列の係数として表現している。ここまでの考察で、次の漸化式が得られる。

 f:id:taamori1229:20200505094002p:plain

K以外の系列について次の敷き詰め方を注意深く見ていくと、次の漸化式が成り立つことが分かる。

 f:id:taamori1229:20200505094132p:plain

非常に煩雑なので、次の規則を適用する。対称性から明らかに、

 f:id:taamori1229:20200505094330p:plain
が成り立つのでTを消去して整理すると、次の漸化式群が得られる。

 f:id:taamori1229:20200505094421p:plain

あとは根気強くこれらを解いてKだけの漸化式を求める。その結果、

 f:id:taamori1229:20200505094819p:plain

が得られる。この漸化式の特性方程式を解くと、

 f:id:taamori1229:20200505094909p:plain
Kの一般項はこれらのべき乗の線形結合となる。適当な初期条件でこれを解くと、

 f:id:taamori1229:20200505095010p:plain
が得られる。

非常に面倒な計算式なので前回同様に、

 f:id:taamori1229:20200505095157p:plain

解を展開したときに現れる係数a、bを用いることとすると、

 f:id:taamori1229:20200505095241p:plain
という簡単な式が得られる。これによって数列は、次のように求められる。

 f:id:taamori1229:20200505095323p:plain

急速に増大していく。数え上げようと思わない方がいい。

次はさらに縦方向を4を5、6と増やしていきたいところだが手計算で行えるのはここまでが限界で、もっと賢いやり方を考えないとこれ以上は無理である。


最終的に求めたいのは、縦方向、横方向の2次元で一般化したK(n,m)である。ここまでで得られた範囲で書き出してみると下記となる。ここで、畳がきちんと収まらないものは除外している。当然のことだが、n、mについては交換しても値は同一になる。また、2行目、2列目にはおなじみのフィボナッチ数列が登場する。

  f:id:taamori1229:20200507075507p:plain

現時点ではこれを眺めてみても何も見えてこない


神田川数列(その2)

前回に引き続き3n畳間を畳で敷き詰める場合の数の話である。
 
 f:id:taamori1229:20200501073938p:plain

nに対応した場合の数を

 f:id:taamori1229:20200429142409p:plain

としてその数列の一杯式を求める。

全体を俯瞰しても答えが見つかりそうもないので、端からかいつまんで考えてみる。

まずは、最後にきれいに2列分空いている場合である。

 
f:id:taamori1229:20200501074712p:plain

この場合は、最後の3畳分は、次の3通りが存在し、残りの部分の組み合わせは、n-1に対応したものに等しく、最後の部分には次の3通りが存在する。

 f:id:taamori1229:20200429142052p:plain

残りの部分の組み合わせは、n-1に対応したものに等しく、最後の部分には次の3通りが存在する。

次に最後がこのようにきれいな2列にならない場合は、次の2つのパターンがあり、それらはKでは表現できないのでそれぞれU、Lと呼ぶ。

 f:id:taamori1229:20200501075111p:plain

以上より、次の漸化式が成立する。

 f:id:taamori1229:20200501075602p:plain

U、Lについては対称性から、

 f:id:taamori1229:20200501075747p:plain

となることは容易に想像がつくので、

 f:id:taamori1229:20200501075827p:plain

となる。次にUを考える。また端の部分に着目すると下記となる。

 f:id:taamori1229:20200501080024p:plain

よって、

 f:id:taamori1229:20200501080202p:plain

以上より、神田川数列は次の連立漸化式に従う。

 f:id:taamori1229:20200501080433p:plain

これらよりUを消去すると、

 f:id:taamori1229:20200501080521p:plain

が得られる。この解法はテクニカルになるのであまり説明はしないが、次の2次方程式、

 f:id:taamori1229:20200501080713p:plain

そしてその解、

 f:id:taamori1229:20200501080758p:plain
のそれぞれのn乗の線形結合で求められることが分かっている。初期値を使って、

f:id:taamori1229:20200501081002p:plain

となる。この第2項は小さいことから(<0.1)第1項のみの四捨五入で、

 f:id:taamori1229:20200501081058p:plain

となる。

この数列には次の不思議な特徴があることが考察の過程で分かった。

 f:id:taamori1229:20200501081500p:plain
と表すと、

 f:id:taamori1229:20200501081534p:plain

となることも容易に示される。これらを用いてKを計算すると次のシンプルな式が得られる。

 f:id:taamori1229:20200501081625p:plain

これは次のような手順でK数列を求めることができることを示している。

 f:id:taamori1229:20200501081728p:plain
この計算手順が、畳を敷き詰めるという行為とどういう関係にあるのかは定かでない。

もう一つの特徴である。数列Kを実際に書き並べてみると、

 f:id:taamori1229:20200501081940p:plain

である。何か気が付くことはないか。

すべて奇数であること。そして下一桁に現れる数字がのが1か3であること。

それだけではない。

 f:id:taamori1229:20200501082056p:plain

このように3の周期をもっているように見える。n=30まで確かめたが正しいかった。この予想が正しいとすれば、畳を敷き詰める問題が10進法表記上のルールを持つことになり、非常に興味深い。

 

神田川数列(その1)

かぐや姫の名曲「神田川

 ~窓の下には神田川~♪、3畳一間の小さな下宿~♪

あと数年もすれば、この曲が発表されてから半世紀になろうとしている。はたして3畳一間というアパートはまだ存在するのだろうか。若い二人は狭い部屋から始めても構わない。焦らずゆっくりと2倍、3倍、つまり6畳、9畳と増やしていけばいいのである。

畳3枚を使って3畳一間を敷き詰める方法を考えると、

  f:id:taamori1229:20200429142019p:plain

次の3通りしかない。

   f:id:taamori1229:20200429142052p:plain

回転すると同じになるものもここでは別と考える。次は通常4畳半ではあるが、この「半」が中途半端なので2倍の6畳を考える。

 f:id:taamori1229:20200429142125p:plain
畳の敷き詰め方についてであるがまずは先述の3畳が二つ並んだものと考えると、

  f:id:taamori1229:20200429142207p:plain


なり、それぞれが3畳の場合で示したように3通りがあるので、3x3の9通りである。そうでない場合については次の2通りが存在する。

  f:id:taamori1229:20200429142249p:plain

以上より、6畳の場合については合計で11通り存在する。次に9畳の場合を数え上げ始めたがどうも40通りを超えそうである。それ以上にきちんと数え上げられているか心配になる。ということで一般化を試みる。

問題を3n畳の場合で考える。


 f:id:taamori1229:20200429142328p:plain

3n畳の場合の畳の敷き詰め方の数列(神田川数列)を、

 f:id:taamori1229:20200429142409p:plain

としたときの一般式を求める、という問題である。

おてんばジュリエット

赤いスウェットに着替えて
バルコニーから抜け出すの
遠い街の灯が私を呼んでるわ

いつも退屈なパーティ
おしゃれな会話にもうんざり
新しい風をいつも感じていたい

わたし、おてんばジュリエット
重いドレスを脱ぎ捨てて

自由のつばさをひろげて
気ままに生きてゆきたい
なんでもこの目で確かめて

目の前に敷かれたレールに
運ばれていくのはいやよ
自分で決めるの

わたしは夜も飛び越える
おてんばジュリエット


今頃ママはあわててる
パパは行方を捜してる
大丈夫よ、心配しないで

素直ないい子でいるより
素敵なレディになりたい
ほんのちょっぴり冒険したいの

わたし、おてんばジュリエット
ガラスの靴も脱ぎ捨てて

星降る夜の浜辺を
裸足で駆け出したいのよ
何かが私を待っている予感

誰かが書いたシナリオに
流されていくのはいやよ
自分で決めるの

わたしは夜も飛び越える
おてんばジュリエット


www.youtube.com

 

レンガを積み上げる問題(その2)

引き続き、レンガブロックをn段積上げる方法の数について考察する。

 f:id:taamori1229:20200414054835p:plain

レンガを2n個使ってn段の柱を作る場合の組合せの数を、

 f:id:taamori1229:20200414054900p:plain

と表す。

n段積上げた状態でそれを上からみた形で分類すると、3つのパターンが考えられる。これはあくまでn段の上部だけを考えたものである。それぞれのパターンごとにどの位の組合せが存在するかを考えることで漸化式を作成する。

一番素直なのがこれ、2つが横並びになる場合である。これは90度回転させる場合もあるので2通りである。

  f:id:taamori1229:20200414054913p:plain

 
これは高さとしてはちょうど1段分なので、残りは(n-1)段分を積み上げる組合せになる。よって組合せの数としては、

 f:id:taamori1229:20200414054924p:plain

となる。次が縦置きに4つの場合。これは1通りだけである。 

  f:id:taamori1229:20200414055006p:plain


高さは2段分とるので、残りは(nー2)段分であり、その組み合わせの数は、

 f:id:taamori1229:20200414054939p:plain

となる。

さて、次が横置きと縦置きの混合である。これは90度ずつ4通りの回転が存在する。

   f:id:taamori1229:20200414055030p:plain

このパターンでは残りのブロックの形状はちょっと複雑で、(nー1)段の上部から横のレンガ1個分、つまり半分だけ切り取られたようないびつな形になる。これの組合せの数はBの系列では表現できないので、それとは別にS系列として定義すると、

 f:id:taamori1229:20200414055046p:plain

となる。以上より、次の漸化式が成り立つ。

 f:id:taamori1229:20200414055058p:plain

S系列については上部に飛び出した半分については2通りが考えられる。ひとつはレンガが横に置かれた場合であり、その場合の残りの部分は(nー2)個のB系列となる。もう一つはレンガが2つ縦に置かれた場合であり、その場合の残りの部分は(n-2)個のS系列となる。こうしてもう一つの漸化式である、
 
 f:id:taamori1229:20200414055117p:plain

が成り立つ。

以上より、B系列、S系列については次の連立漸化式が成立する。

 f:id:taamori1229:20200414055133p:plain

これを解くことでBだけの漸化式を求める。まず、第1式でn→nー1としたものを連立させて辺々を引く。こうすると第2式を用いてSを消去することができる。こうして、Bについての漸化式、

 f:id:taamori1229:20200414055408p:plain

が得られる。この形式の漸化式を満たす一般項は、次の特性方程式とその解、

 f:id:taamori1229:20200414055440p:plain
 f:id:taamori1229:20200414055459p:plain

を用いて、次のように表される(Cは定数)、

 f:id:taamori1229:20200414055513p:plain

これを初期条件を用いて解くことで、

 f:id:taamori1229:20200414055526p:plain

が得られる。ちょっと複雑なので、第2項以下を定量的に分析してみる。

第2項はnが増えるに従って0に限りなく近づいていく。すべてのn≧1について、

 f:id:taamori1229:20200414055546p:plain

となる非常に小さい値である。第3項は±0.333…という2通りの値しかとらないので、第2、3項は合算しても、

 f:id:taamori1229:20200414055605p:plain

程度であるから、真の値(つまり整数)と第1項の差は、

 f:id:taamori1229:20200414055616p:plain

となり、真の値は第1項を四捨五入で丸めることで求める数を得ることができる。つまり、

 f:id:taamori1229:20200414055628p:plain

となる。

余談であるが、柱をもっとシンプルにしたらどうなるだろうか。

  

 f:id:taamori1229:20200415163605p:plain

横置きのレンガの大きさで積んでいくやりかたである。この場合の組み合わせの漸化式は、

 f:id:taamori1229:20200415164256p:plain

であり、数列を書き下すと、

 f:id:taamori1229:20200415163030p:plain

おなじみのフィボナッチ数列そのものである。

レンガを積み上げる問題

昨今の情勢、そして身の回りの諸般の事情から味気ないレンガを眺めながらタバコを吸うことが多くなってきた。

 f:id:taamori1229:20200412165332j:plain

こんな問題を思いついた。一つのレンガブロックの大きさを、

 f:id:taamori1229:20200412174608p:plain
とし、これを次のようにn段積み上げる。

f:id:taamori1229:20200412174700p:plain

ここでレンガは横長においてもいいし、縦長においてもいい。ただし、空きスペースができてはいけない。つまり、上図を構成するレンガブロックの数は必ず2n個である。

ここで問題はこのようなレンガの積み上げ方は何通りあるか?である。

実際にnの小さいほうから数え上げてみると、

 f:id:taamori1229:20200412175020p:plain

である。

一般項を求めた結果、

 f:id:taamori1229:20200412175143p:plain

となった。不思議な形でちょっと自信はないがどうもこれで正しそうである。