Easy Japanese ☆（＾～＾）

↑ Easy Japanese Triangle.

↑ Catalan number n+1. (n=9 → 1430)

出典

Easy Japanese pic.twitter.com/Q7qY4Jk0E2

— Antho Derv 💯💦🤦‍♂️ (@ozAntinnippon) January 2, 2021

「　これは数学なのでは……☆」

「　頭がフラフラなら、寝てろだぜ☆」

「　やらないと　寝ないのよ」

1

Cat.

11

Cat head.

122

Cat that the head eats.

212

A cat whose head eats.

1233

Cat eating red fish.

1313

Cat eating red fish.

2133

Cat eating red fish.

3123

Red cat eating fish.

3213

Red cat eating fish.

12344

A cat eating a fish with a red head.

12414

A cat eating a fish with a red head.

13144

A cat eating a fish with a red head.

14124

Red-headed cat eating fish.

14214

Red-headed cat eating fish.

21344

A cat eating a fish with a red head.

21414

A cat eating a fish with a red head.

31244

(2020-01-07 modify) 間違い: 31424 → 31244

Cat with head eating red fish.

32144

Cat with head eating red fish.

41234

Cat head eating red fish.

41314

Cat head eating red fish.

42134

Cat head eating red fish.

43124

Red cat head eating fish.

43214

Red cat head eating fish.

「　終わり☆！」

「　存在しないパターンはどこへ行ったの？　頭が赤い魚を食べる猫頭とか」

「　頭が２回出てきているので　アウト　だな☆」

「　表現力を確かめてみようぜ☆？」

n=1 の表現力

「　n=1 のときの表現力は 1 だな☆」

n=2 の表現力

「　n=2 のときの表現力も 1 だな☆」

n=3 の表現力

「　n=3 のときの表現力は 2 だな☆」

n=4 の表現力

「　n=4 のときの表現力は 2 だな☆」

「　半分なのか平方根なのか 気になるな……☆」

n=5 の表現力

「　n=5 のときの表現力は 5 だな☆」

「　倍になる増え方するなら 平方根では無いか……☆」

「　表現力を　どれぐらい　ロスしてるの？」

「　ものすごく損してるぜ☆
14種類表現できてもいいはずなのに、５つしか表現できない☆」

「　被りがあるからな☆」

「　n と paths の関係を一般化できないの？」

「　無色コーダーにはつらいぜ……☆ 考えるだけ考えてみるか☆」

paths = f(n)

「　うーむ……☆」

「　ヨッシーのたまご　で　こんなこと　やったような気がしてきた……☆」

「　すぐには　視えないか☆」

「　n=6 も試させてくれだぜ☆」

「　まだ寝ないの？」

123455

123515

(2021-01-07 add)

124155

(2021-01-07 add)

125125

(2021-01-07 add)

125215

(2021-01-07 add)

131455

131515

141255

142155

151235

151315

152135

153125

(2021-01-07 add)

153215

213455

213515

214155

(2021-01-07 add)

215125

215215

312455

312515

(2021-01-07 add)

321455

321515

(2021-01-07 add)

412355

413155

421355

431255

(2021-01-07 add)

432155

(2021-01-07 add)

512345

512415

513145

514125

(2021-01-07 add)

514215

521345

521415

(2021-01-07 add)

531245

532145

541235

541315

542135

543125

543215

「　一意の数で被りがないことは保証しているが、漏れが無いか　目視確認しようぜ☆？」

(※注 2021-01-07 に 12個追加)

「　わらう☆」

(※注 2021-01-07 に n=6 のとき paths=42)

「　うーむ☆　まだ分からん☆」

「　↓ 包含関係は あるんじゃないの？」

n=1

(n) ⊂ (n+1) ⊂ (n+2) ⊂ (n+3) ⊂ (n+4) ⊂ (n+5)

「　そりゃそうか……☆」

n=1 のとき:

「　さざんがきゅう、ししじゅうろく☆　うーむ☆」

「　n+3 の列が 4 だったら 簡単な話じゃない？」

「　漏れがあるかも知らん……、見直すかだぜ☆」

「　目視確認では、 n+3 の列は 3 で合ってるんだぜ☆」

「　プログラムで　ブルートフォース・サーチ　できんのか☆？」

「　今日は遅くなったので、また今度な☆」

「　三角形の　右上がりの半分と、右下がりの半分　に分かれていることが
補助線の視えにくさ　になっているのではないか、という辺りを　寝ながら考えるか……☆」

解法を考えようぜ☆？

「　↑ 上図の単語の１つ１つを　エレメント　と呼ぼうぜ☆」

「　↑ 猫の方を１に、赤いの方を４にするかだぜ☆」

「　↑ 棒が右に倒れているとき、スイッチオフ☆　数でいうと　０　にしておこうぜ☆」

「　↑ 棒が左に倒れているとき、スイッチオン☆　数でいうと　１　にしておこうぜ☆」

「　↑ n が 2以上のとき、左端の e は 0、右端の e は 1 に固定だな☆」

「　↑ わたしたちの関心毎は、 e[1] と、 e[n] の間にあるな☆」

「　↑ これを 0 ☆」

「　↑ これを 1 と定義しようぜ☆？」

「　それだと ２進数 の考え方にならないか☆？」

「　これから　複雑になっていくんだぜ☆」

「　↑ 例えば n=4 なら☆」

「　↑ n=3 の三角形を２つ含んでいるので、4 <= paths は確定しそうだぜ☆」

「　↑ そして n=3 の三角形を含まないパターンを作ることができる☆　これがあるから paths = 5 ☆」

「　じゃあ少なくとも n が１つ増えるたびに、paths は ２倍以上になることは 期待したいわねぇ」

「　↑ n=5 のケースでも ほぼ同様のことが起こるぜ☆」

「　↑ n=5 の三角形は n=4 の三角形を２つ含むから、 2*5 <= paths は確定しそうだぜ☆」

「　↑ そして n=4 の三角形では作れないパターンが 4つ増えるから、 n=5 は 2*5+4 = paths だろうと、目視確認して思ったんだぜ☆」

「　作れないパターン に法則性はあるの？」

「　それが分からないから調べているんだぜ☆」

「　↑ n=6 のパターンも見ていこうぜ☆？」

「　↑ n=6 の三角形は n=5 の三角形を２つ含むから、 2*14 <= paths は確定しそうだぜ☆」

「　↑ そして n=5 の三角形では作れないパターンが 8つ増えるから、 n=5 は 2*14+8 = paths かも知れないと、目視確認して思ったんだぜ☆」

「　お父んが見つけた n=6 は 30 paths だが、 理論上は 36 paths かだぜ☆？
見つけた図に 漏れがあるのでは☆？」

「　はぁ☆　めんどくさ……☆」

「　6個 見つけた……☆」

「　1, 3, 9, 22 って あんま見ない数列ね」

paths = f(n)
    1 = f(1)
    1 = f(2)
    2 = f(3)
    5 = f(4)
   14 = f(5)
   36 = f(6)

「　↑ こうか☆」

paths = f(n)
    1 = f(1) = 1 is define
    1 = f(2) = 1 is define
    2 = f(3) = 2 f(2) + 0
    5 = f(4) = 2 f(3) + 1
   14 = f(5) = 2 f(4) + 4
   36 = f(6) = 2 f(5) + 8

「　↑ うーむ、 0, 1, 4, 8 の数列が 見慣れないぜ……☆」

「　0, 1, 4, 9 なら xの2乗なんだがな☆
お父んが 見落としているのでは☆？」

「　探すか☆　はぁ☆　めんどくさ……☆」

「　1つ 見つけたぜ☆」

「　↑ 123515 が視えてなかった……☆」

paths = f(n)
    1 = f(1) = 1 is define
    1 = f(2) = 1 is define
    2 = f(3) = 2 f(2) + 0
    5 = f(4) = 2 f(3) + 1
   14 = f(5) = 2 f(4) + 4
   37 = f(6) = 2 f(5) + 9

「　↑ これなら もう少し式を簡単にできるな☆」

paths = f(n)
    1 = f(1) = 1 is define
    1 = f(2) = 1 is define
    2 = f(3) = 2 f(2)
    5 = f(4) = 2 f(3) + (n-3)^2
   14 = f(5) = 2 f(4) + (n-3)^2
   37 = f(6) = 2 f(5) + (n-3)^2

「　↑ すっきりしねーな☆」

f(n) について:

1 <= n <= 2 のとき、 1
n = 3 のとき、 2
4 <= n <= 6 のとき、 2 f(n-1) + (n-3)^2

(※注：　f(6)=37 ではなかったので、上式は間違い)

「　↑ 見落としがどれぐらいあるか分からないが、今のところ　こうだぜ☆」

「　その (n-3)^2 の部分が何を表しているか はっきりしなければ、この調査は終わんなくない☆？」

「　それはもう　視えてきた☆」

「　おおお……☆」

n = 2 は定義

↑ 1

「　↑ n = 2 のとき、 paths = 1 は定義としてくれだぜ☆
単位三角形　とでも呼ぶかだぜ☆」

n = 3 のときの実証

↑ 2 f(n-1)

「　↑ n = 2 の三角形が、２つあるな☆」

n = 4 のときの実証

↑ 2 f(n-1)

「　↑ n = 3 の三角形が、２つあるな☆」

↑ (n-3)^2

「　↑ n = 2 の定義の単位三角形　２つを　一緒に はめ込めるな☆」

n = 5 のときの実証

↑ 2 f(n-1)

「　↑ n = 4 の三角形が、２つあるな☆」

↑ (n-3)^2

「　↑ n = 2 の定義の単位三角形　４つと、 n = 3 の三角形　４つが　ペアを組みながら一緒に はめ込めるな☆」

n = 6 のときの実証

↑ 2 f(n-1)

「　↑ n = 5 の三角形が、２つあるな☆」

↑ (n-3)^2

「　↑ n = 2 の定義の単位三角形　７つと、 n = 3 の三角形　４つと、　n = 4 の三角形　７つが　はめ込めるな☆」

「　もっと　パターンある気がするけどな☆
見落としは無いのかだぜ☆？」

「　何か視えたか……、探すか☆　はぁ☆　めんどくさ……☆」

「　↑ ２つ 見つけたぜ☆ 125125 と 125215 が視えてなかった……☆」

「　じゃあ　式の立て直しよ！」

「　入 みたいなペアがあるんだったら、 人 みたいなペアもあるだろ☆　まだ　パターンある気がするけどな☆
見落としは無いのかだぜ☆？」

「　まだ何か視えたか……、探すか☆　はぁ☆　めんどくさ……☆」

「　３つ 見つけたぜ☆ 153125、 312515、 321515 が視えてなかった……☆」

paths = f(n)
    1 = f(2) = 1 is define
    2 = f(3) = 2 f(2) + 0
    5 = f(4) = 2 f(3) + 1
   14 = f(5) = 2 f(4) + 4
   42 = f(6) = 2 f(5) + 14

「　↑ 分からなくなった……☆」

「　単純に 3 f(n-1) にならんのか☆？」

「　漏れがないか探すか……☆　はぁ☆　めんどくさ……☆」

  f(2) * f(2)
=   1  *   1
= 1

  2 ( f(2) * f(3) )
= 2 (    1 *    2 )
= 4

# f(3) * f(3) は左右同型。
  2 ( f(2) * f(4) ) + ( f(3) * f(3) )
= 2 (    1 *    5 ) + (    2 *    2 )
=               10  +              4
= 14

「　↑ 1, 4, 14 はこういうことだぜ☆
これの式の立て方は、また今度考えるかだぜ☆　こんなん　できるのか……☆？」

2 f(5) + 14 の原理を考えようぜ☆？

「　↑ 上図を見ただけで、 n が偶数のとき 大きな山と 小さな山がペアになるグループと、
同じ大きさの山がペアになるグループに分かれることが分かるよな☆」

「　n=7 になったら、どんなけパターンが増えるんだぜ☆？」

「　見たくないわよーっ！」

n=7 を推測しようぜ☆？

「　↑ もし n=6 が 42 paths で合ってるのだとしたら、その山が２つで 84 paths < f(7) は確定だぜ☆」

「　↑ 山が３個入るパターンとかない？」

「　↑ 多分それは　中ぐらいの山に　小さな山が２つ入っているのを想像しているんだぜ☆」

「　↑ n が奇数なら、同じ大きさの山のペアは　できないな☆」

「　そうなの？」

「　↑ こんな山のペアだって　あるんじゃないの？」

「　↑ 中ぐらいの山の中にある小さな山でも　見てるんだろ☆」

「　むぎぎぎぎ！」

「　今は　n　を自然数でやっているが、 実数になったら 無限に吸い込まれて、頭が追い付かないぜ☆
やっぱ　わたしは　整数だな……☆」

「　↑ 例えば、 あいだが無い というのは、実数にはない整数の特徴だぜ☆
だから　大きな三角形が１個しか入らない、という　特殊な状況を　生み出しているんだぜ☆」

「　もし n が 実数なら、この水色の三角形は、背景の三角形と同じ大きさと みなしてもいいぐらいだろう☆」

「　この　水色の三角形があるから、 n=7 のときは n=6 が２つある、とか言えるのに！」

「　実数になっても、整数の部分を使えば　言えるんじゃないかな……☆」

「　↑ 多分、ここの間に エレメントが無いのも、実数ではない整数の性質な☆」

「　整数の性質があるのではなく、　自己稠密（じこちゅうみつ）という性質が無いんだろ☆」

「　平行四辺形の面積の式で 簡単にできないのかだぜ……☆　分からんな☆　引き続き　地道に調べるか☆」

「　↑ 隙間の平方四辺形の 角っこの 欠けの面積を 出せなくない？」

「　↑ それは 定義から 自明なのでは……☆ 単位三角形だぜ☆ 図にしてみるかだぜ☆」

「　ほんとか☆？」

「　脳ミソは　答えを持っているわけではないので　証明する方法は無いが
そのように視えるぜ☆」

「　お父んは 整数 で考えているから そう見えるだけで、実数では 単位三角形 ではなく、ほぼ 面積0 の 突起 だと思うけどな☆」

「　じゃあ　いったん、 面積 という発想で n=2 ～ n=6 を見直そうぜ☆？」

面積の見方で計算し直す n=2

「　斜辺を １ と定義すると 数えにくいんで、底辺を 1 としようぜ☆？」

「　お父んは どう頭を傾けて 斜辺とか底辺と 言ってるのか……☆ 平行四辺形なのに……☆」

面積の見方で計算し直す n=3

「　↑ 単位三角形の面積は 常に 0.5 なのでは……☆」

「　単位って名前してんなら 1 にしろだぜ☆」

「　単純に 単位三角形のタイルの枚数でいいんじゃないの？」

「　↑ 正方形の面積の半分だぜ☆」

「　それを　直角三角形の面積という☆」

「　paths は 直角三角形の面積では無いんじゃない？」

「　考え直しか……☆」

「　↑ うーむ☆
これは数学なのだから、指で数えなくても n=7 や n=8 の三角形の 赤い数字を出せるはずなんだぜ、うーん☆
1+1=2
1+4=5
1+9+4+4=18 うーん☆」

プログラミングで解こうぜ☆？

「　プログラミングの出番では☆？」

「　どんな データ構造なんだぜ これ☆」

「　木でしょ」

「　↑ 配列の半分を使えばいいんじゃないの？」

「　それだと　頂点　は分かるが　エッジ（辺、線）の接続が分からん……☆」

「　↑ エッジが欲しいのに……☆」

「　上から 奇数、偶数、奇数、偶数……個のエッジを　データとして持つなんて気持ち悪い……☆
それより　良いデータ構造があるぜ☆」

「　↑ ピース（Piece）は これだけあればOK☆」

「　なるほど　そうか☆　あー、そうか☆　分かった☆」

「　↑ 初期配置（Starting position）はこうだろ☆ あとはお父んが考えてくれだぜ☆」

「　↑ まあシンプルに これでいいんじゃないかだぜ☆？」

「　↑ 右か下の２択でランダムに進めだぜ☆ 4 のマスに着いたら終了だぜ☆」

「　そんなもんでいいのか☆」

「　よくないケースがあらなくない？」

「　あら、なく、ない　って何だぜ☆？」

「　↑ ぶつかったら　どうすんの？」

「　そうか……☆　木の枝は　カーブできないのだった……☆　だったら　もっと簡単に　木　を作れる……☆」

「　↑ まず 最上段を 右に走るぜ☆」

「　↑ 次に 最左列を 下に走るぜ☆」

「　↑ 次に 木のルートから、ランダムに数歩進んで……☆」

「　４ にたどり着けたらゴール、成功だぜ☆
１や２に　たどり着いたら、そんな枝は下せないぜ☆　アンドゥしろだぜ☆」

「　ビームを乱射していれば　そのうち　全マス埋まって　木　が出来上がるということかだぜ☆
それだったら……☆」

「　↑ 木が埋まるのを調べるのではなく、 要素が ｎ個 作られることを調べないといけないな☆」

「　両端を除く　順序をシャッフルした　ゴールから、　ランダム方向に　レーザーを発射すれば　ｎ回で埋まんない？」

「　目から鱗だぜ☆」

だったら もっと簡単なアルゴリズムで行けるのでは？

「　思いついたことを 実証してみるぜ☆」

「　↑ つまり、こうでは☆？」

「　数式で言うと？」

「　もうちょっと調べものがあるので　あとで☆」

「　↑ うーん☆」

Git hub

「　↑ Python でプログラムを組んだところ、 n=6 は 42 paths, n=7 は 132 paths が濃厚だぜ☆」

「　もっとサンプルを集めてみようぜ☆？」

「　↑ Python では速度が足りないな……☆」

「　↑ 30 分トライして 4800 いくつ、でバラツキがある……☆」

なんてこった☆ 終わり☆

「　↑ 謎の部分を q と置こうぜ☆」

「　↑ q の形が まだ視えないぜ☆
1,4,14,48,165,569 ……☆」

「　CGP さんが n=9は1430 、 やねさんが それただのカタラン数 って言ってるわよ」

「　なんてこった☆　終わり☆」

＜おわり＞

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

まてだぜ☆ カタラン数を説明しろだぜ☆

「　まてだぜ☆　カタラン数　を説明しろだぜ☆」

「　↑ これの 別の書き方が 他にもあるということだぜ☆」

「　↑ 例えば n が 葉ではなく 節の数のケースだぜ☆」

「　↑ その枝の先っぽの高さを等しくすれば、わたしが考えていた図と同じだぜ☆
面積を食ってしまうな☆」

「　お父んに分からなかった　q　って何だったんだぜ☆？」