😊出会いの泉😊

多分mの最大は17ですよね。
適当に考えたので全く綺麗ではないですが、例えば
2,1,3,1,4,2,3,2,4,3,3,4,4,1,1,2,2

m=17 で作ると
右端と左端とは同じものになりそうですね。

はい、両端は同じ数字になります。
ゾロ目が入っているとちょっとややこしいので、11,22,33,44を除いたm=13で考えます。
（m=17のパターンから同じ数字の連続を1文字減らせばそのパターンになります。）
また先頭の数字は2とします。
2で始まる2桁は21,23,24の3個
2で終わる2桁は12,32,42の3個
が必要ですが、右端が2でないと仮定すると
2a…A2b…B2c…
のようになり、2a,2b,2cの3個で21,23,24はすべて終わりますが、
そうすると2で終わるものがA2,B2の2個しかないので足りません。
よって2で始まるものと2で終わるものが同数になるためには
2a…A2b…B2c…C2
のように2で始まったら2で終わらなければなりませんので、
左端と右端の数字は常に同じになります。

1 までを使う場合、最長の 1 つは
1,1

2 までを使う場合、これのどこかの 1 を 1,2,1 に変え、さらにどこかの 2 を 2,2 に変えると
1,2,2,1,1

3 までを使う場合、これのどこかの 1 を 1,3,1 に変え、さらにどこかの 2 を 2,3,2 に変え、そしてどこかの 3 を 3,3 に変えると
1,3,3,1,2,3,2,2,1,1

以下同様に繰り返せば、n まで使うときの n^2+1 項の数列の一例を錬成できますね。

m=17 で所望の有限数列を求めるにあたり、
１列の繋がりではなく、
m-1=16 の数からなる円環をまずは構成するのも面白いですね。
DD+さんによる構成を真似すれば n が 4 のときも n^2 がベストなわけです。m-1=16はそれを満たしています。
四色のビーズに糸を通してワッカにし
机の上においたときに
輪を右回りに方向つけて、
各ビーズの右隣、左隣の色のパターンがそれぞれ
輪のなかでダブルことがないようにするには
(四色でしたから)
4✕4 = 16 が最大であろうと見当がつきます。
うまく並べることができたら、
輪っかの糸を一箇所で切断し
ビーズを１列に並ぶようにします。
このとき、切断のおかげで、
色の並びのひとつが消失します。
それを補償するために
ビーズを１個補充して
左右の端の色が同じになるようにします。

これにて、17個で、左右の端が同じになる
列ができあがります。

論理が飛んでいますがご容赦ください。

使える数字が{1,2}や{1,2,3}ならどうなるのだろうと思ったので調べたら
{1,2}=>[1,2,2,1,1],[1,1,2,2,1] (なお1,2の数字を入れ替えても可)で<1を3回;2を2回使用>
{1,2,3}=>[1, 1, 2, 1, 3, 2, 2, 3, 3, 1] (1,2,3の数字はサイクリックに変更できる。)で<1を4回;2を3回;3を3回使用>
らすかるさんの例も(1->4.2->1,3->2,4->3)に読み替えると
{1,2,3,4}=>[1,4,2,4,3,1,2,1,3,2,2,3,3,4,4,1,1]で<1を5回;2を4回;3を4回;4を4回使用>
そこで一般に
{1,2,3,･･･,n}
の数字で条件を満たす最長のパターンは,<1をn+1回;2をn回;3をn回;4をn回;･･･,nをn回使用>して最長n^2+1の数列が作れそうです。
証明は数学的帰納法が有力だが示し方が分からない。
これが何通り構成可能かは
1を他より1回多く使用するパターンに限って調べたら
n=2;2通り（例で挙げたもの)
n=3;72通り
1;[1, 1, 2, 1, 3, 2, 2, 3, 3, 1]
2;[1, 1, 2, 1, 3, 3, 2, 2, 3, 1]
3;[1, 1, 2, 2, 1, 3, 2, 3, 3, 1]
4;[1, 1, 2, 2, 1, 3, 3, 2, 3, 1]
5;[1, 1, 2, 2, 3, 1, 3, 3, 2, 1]
6;[1, 1, 2, 2, 3, 2, 1, 3, 3, 1]
7;[1, 1, 2, 2, 3, 3, 1, 3, 2, 1]
8;[1, 1, 2, 2, 3, 3, 2, 1, 3, 1]
9;[1, 1, 2, 3, 1, 3, 3, 2, 2, 1]
10;[1, 1, 2, 3, 2, 2, 1, 3, 3, 1]
11;[1, 1, 2, 3, 3, 1, 3, 2, 2, 1]
12;[1, 1, 2, 3, 3, 2, 2, 1, 3, 1]
13;[1, 1, 3, 1, 2, 2, 3, 3, 2, 1]
14;[1, 1, 3, 1, 2, 3, 3, 2, 2, 1]
15;[1, 1, 3, 2, 1, 2, 2, 3, 3, 1]
16;[1, 1, 3, 2, 2, 1, 2, 3, 3, 1]
17;[1, 1, 3, 2, 2, 3, 3, 1, 2, 1]
18;[1, 1, 3, 2, 3, 3, 1, 2, 2, 1]
19;[1, 1, 3, 3, 1, 2, 2, 3, 2, 1]
20;[1, 1, 3, 3, 1, 2, 3, 2, 2, 1]
21;[1, 1, 3, 3, 2, 1, 2, 2, 3, 1]
22;[1, 1, 3, 3, 2, 2, 1, 2, 3, 1]
23;[1, 1, 3, 3, 2, 2, 3, 1, 2, 1]
24;[1, 1, 3, 3, 2, 3, 1, 2, 2, 1]
25;[1, 2, 1, 1, 3, 2, 2, 3, 3, 1]
26;[1, 2, 1, 1, 3, 3, 2, 2, 3, 1]
27;[1, 2, 1, 3, 2, 2, 3, 3, 1, 1]
28;[1, 2, 1, 3, 3, 2, 2, 3, 1, 1]
29;[1, 2, 2, 1, 1, 3, 2, 3, 3, 1]
30;[1, 2, 2, 1, 1, 3, 3, 2, 3, 1]
31;[1, 2, 2, 1, 3, 2, 3, 3, 1, 1]
32;[1, 2, 2, 1, 3, 3, 2, 3, 1, 1]
33;[1, 2, 2, 3, 1, 1, 3, 3, 2, 1]
34;[1, 2, 2, 3, 1, 3, 3, 2, 1, 1]
35;[1, 2, 2, 3, 2, 1, 1, 3, 3, 1]
36;[1, 2, 2, 3, 2, 1, 3, 3, 1, 1]
37;[1, 2, 2, 3, 3, 1, 1, 3, 2, 1]
38;[1, 2, 2, 3, 3, 1, 3, 2, 1, 1]
39;[1, 2, 2, 3, 3, 2, 1, 1, 3, 1]
40;[1, 2, 2, 3, 3, 2, 1, 3, 1, 1]
41;[1, 2, 3, 1, 1, 3, 3, 2, 2, 1]
42;[1, 2, 3, 1, 3, 3, 2, 2, 1, 1]
43;[1, 2, 3, 2, 2, 1, 1, 3, 3, 1]
44;[1, 2, 3, 2, 2, 1, 3, 3, 1, 1]
45;[1, 2, 3, 3, 1, 1, 3, 2, 2, 1]
46;[1, 2, 3, 3, 1, 3, 2, 2, 1, 1]
47;[1, 2, 3, 3, 2, 2, 1, 1, 3, 1]
48;[1, 2, 3, 3, 2, 2, 1, 3, 1, 1]
49;[1, 3, 1, 1, 2, 2, 3, 3, 2, 1]
50;[1, 3, 1, 1, 2, 3, 3, 2, 2, 1]
51;[1, 3, 1, 2, 2, 3, 3, 2, 1, 1]
52;[1, 3, 1, 2, 3, 3, 2, 2, 1, 1]
53;[1, 3, 2, 1, 1, 2, 2, 3, 3, 1]
54;[1, 3, 2, 1, 2, 2, 3, 3, 1, 1]
55;[1, 3, 2, 2, 1, 1, 2, 3, 3, 1]
56;[1, 3, 2, 2, 1, 2, 3, 3, 1, 1]
57;[1, 3, 2, 2, 3, 3, 1, 1, 2, 1]
58;[1, 3, 2, 2, 3, 3, 1, 2, 1, 1]
59;[1, 3, 2, 3, 3, 1, 1, 2, 2, 1]
60;[1, 3, 2, 3, 3, 1, 2, 2, 1, 1]
61;[1, 3, 3, 1, 1, 2, 2, 3, 2, 1]
62;[1, 3, 3, 1, 1, 2, 3, 2, 2, 1]
63;[1, 3, 3, 1, 2, 2, 3, 2, 1, 1]
64;[1, 3, 3, 1, 2, 3, 2, 2, 1, 1]
65;[1, 3, 3, 2, 1, 1, 2, 2, 3, 1]
66;[1, 3, 3, 2, 1, 2, 2, 3, 1, 1]
67;[1, 3, 3, 2, 2, 1, 1, 2, 3, 1]
68;[1, 3, 3, 2, 2, 1, 2, 3, 1, 1]
69;[1, 3, 3, 2, 2, 3, 1, 1, 2, 1]
70;[1, 3, 3, 2, 2, 3, 1, 2, 1, 1]
71;[1, 3, 3, 2, 3, 1, 1, 2, 2, 1]
72;[1, 3, 3, 2, 3, 1, 2, 2, 1, 1]

n=4; 82944通り
1;[1, 1, 2, 1, 3, 1, 4, 2, 2, 3, 2, 4, 3, 3, 4, 4, 1]
2;[1, 1, 2, 1, 3, 1, 4, 2, 2, 3, 2, 4, 4, 3, 3, 4, 1]
3;[1, 1, 2, 1, 3, 1, 4, 2, 2, 3, 3, 2, 4, 3, 4, 4, 1]
････････････････
82942;[1, 4, 4, 3, 4, 2, 4, 1, 3, 3, 2, 2, 3, 1, 2, 1, 1]
82943;[1, 4, 4, 3, 4, 2, 4, 1, 3, 3, 2, 3, 1, 1, 2, 2, 1]
82944;[1, 4, 4, 3, 4, 2, 4, 1, 3, 3, 2, 3, 1, 2, 2, 1, 1]

怪しいプログラムで探しているので、誰か確認願う。

2,72,82944は正しいです。
また、n=5は4976640000通りです。

らすかるさん、いつもありがとうございます。

n=4での結果を得るまでに優に３時間以上は要したので
n=5では指数関数的に時間が増加し、自分のプログラムではたぶん１年以上かかっても無理と思えるものになります。
それをn=5は4976640000通りとたちどころに算出できるらすかるさんの技に驚かされます。
管理人さんから出題された問題に、どんなことを意味しているのかを理解するまでにまず時間がかかり、らすかるさんの解答をみて
やっとその意味が分かり始め、始めは配列を手作業で作ろうと試みるが結局混乱していき、何とか自動化で配列を決められないかと
これをプログラムで作り出すまでにまた何度も試行錯誤を繰り返していきました。
始め全部で配列が何個できるかを探る疑問に間違った考え方で算出していたが、結果を点検したらその考え違いに気付いてコードを
全面的に修正してやっと何とか結果が得られたんではないかという顛末を辿りました。

自分なりに、修正を繰り返しながららすかるさんと同じ結果を得られたことにとてもうれしい気持ちです。

もしかして
n=6 は 23219011584000000
n=7 は 11800915893414789120000000
n=8 は 873120530892689265453642547200000000
だったりします？
コンピュータでも流石にこの桁数は厳しいですかね？

n=5は数分だったのですが、n=6にかかる時間はざっと考えても1兆倍以上かかりそうなので、
コンピュータでカウントする方式では試すまでもなく全く無理ですね。

n まで使える場合に最長数列が何通り構成できるか。
その答えは全く別の「ある問題」の答えを足がかりにするとよい、というところまで昨晩到達し、実際に n=8 までの解を（合っているかどうかまだ不明ですが）求めました。

が、しかし、その「ある問題」を一般の n で解こうとして一晩考えても方針が全く思い浮かびません。
みなさんの協力を求めるべく、別スレッドで「まち針の木」として出題しています。
あっちが解ければこっちも解けるので、挑戦よろしくお願いします。

そういえば、記事中の

> 違うパターンで考えてみると、
> １、２、３、４、１、３、２、４、２、１、２、２
> で、第１３項目に入る数はないので、

の例では、第 11 項の時点で「1, 2」が 2 回登場してルール違反になっていますね。
らすかるさんが既に証明している通り、「数列がこれ以上続けられない」という現象は必ずスタートに使った数字で起こるはずです。

n=9
gp > prod(i=0,8,floor((80+i)/9)!)
%368 = 12123409823952368497816099928432676175872000000000
n=10
gp > prod(i=0,9,floor((99+i)/10)!)
%369 = 39594086612242519324387557078266845776303882240000000000000000000

一般にnなら
prod(i=0,n-1,floor((n^2-1+i)/n)!)
となりませんか？

(n!)^n/n と同じ式ですかね？

n=8 までは私が直接求めたので、（私が計算ミスをしていない限り）この式に一致する結果になっています。
そして、n≧9 でも多分成り立つんだろうなと私も思います。

でも、「成り立つと予想した」だけでは解けたとは言えません。
解けたと宣言するには成り立つ証明まで必要です。

「最長数列の総数」と「まち針の木」の関係について掲載しておきます。
一般の n のままだとわかりにくいので、「最長数列の総数」の n=4 という具体的な話で進め、既に出ている 82944 通りという数を導出してみます。

まず、
「数列の現在の末尾の数が 4 回目以内の登場ならば、次に書くことができる数がまだ残っている」は数列の作り方から明らかです。
よって対偶を考えれば
「次に書くことのできる数がもうないならば、現在の末尾の数は 5 回目以降の登場をしている」
ことがわかります。

しかし、条件
「s≠t で、a[s]=a[t] ならば、a[s+1]≠a[t+1]」
の対偶
「s≠t で、a[s+1]=a[t+1] ならば、a[s]≠a[t]」
より、同じ数が複数回登場する場合、直前の数字は全て異ならなくてはいけません。
つまり、5 回以上登場できる数は、先頭にある 1 に限られます。
つまり、次に書くことのできる数がもうなくなった数列は、必ず 1 が「先頭」「1 の次」「2 の次」「3 の次」「4 の次」を順不同に 1 回ずつ計 5 回登場した直後で終わっています。

さて、最長数列の個数を考えましょう。
まず、n=4 の最長数列を実際にたくさん作って、「1 以外の各数について、4 回目の登場の次に何を書いたか」で分類します。
例えば、GAI さんのリストの先頭のものは、4 回目の 2 の次は 4、4 回目の 3 の次は 4、4 回目の 4 の次は 1、となっているので、
1;[1, 1, 2, 1, 3, 1, 4, 2, 2, 3, 2, 4, 3, 3, 4, 4, 1] -> [2->4, 3->4, 4->1]
と分類します。

さて、では同じ [2->4, 3->4, 4->1] に分類される数列は何個作れるでしょうか。
実はこれは非常に簡単な問題です。
先に示した通り、そのような数列は最長でもそうでなくても、行き詰まるのは必ず 5 回目の 1 が登場したときです。
そして、それは「先頭」「1 の次」「2 の次」「3 の次」「4 の次」が全て揃ったときになるはずです。
ところが、4->1 という関係がある以上、4 が 4 回登場した後でないと「4 の次」は起こりません。
したがって、4->1 という依存関係があれば、どんなに雑に数列を作っても、行き詰まる前に 4 が 4 回登場することは絶対に保証されるのです。
さらに、4 が 4 回登場するのは「1 の次」「2 の次」「3 の次」「4 の次」が全て揃ったときになるはずですが、2->4, 3->4 という関係があるので、同様に 2 と 3 もどんなに雑に作っても 4 回登場することが保証されるのです。
つまり、
「1 の登場 4 回目までは次の数に 1,2,3,4 を任意の順で使う」
「2 の登場 3 回目までは次の数に 1,2,3 を任意の順で使う」
「3 の登場 3 回目までは次の数に 1,2,3 を任意の順で使う」
「4 の登場 3 回目までは次の数に 2,3,4 を任意の順で使う」
を守る限り、何をやっても自動的に [2->4, 3->4, 4->1] に分類される最長数列ができあがるのです。
よって、その総数は 4!*3!*3!*3! = 5184 通りです。
これは [2->4, 3->4, 4->1] に限った話ではないので、分類それぞれの中で必ず 5184 個の最長数列が作れることになります。

では、そのような分類は何組できるかということを考えます。
[2->a, 3->b, 4->c] の a, b, c を適当に選べばよいかというとそうではありません。
例えば [2->4, 3->2, 4->2] の場合。
2 と 4 はお互いに 4 回目の登場があるとしたら相手の 4 回目より後でないといけないというループが発生しています。
つまりどんなにうまくやっても 2 や 4 の 4 回目が登場しないまま 5 回目の 1 が来て数列が終わってしまうことを意味します。
よって、[2->4, 3->2, 4->2] という分類は存在しません。
あるいは [2->1, 3->2, 4->4] の場合。
2 と 3 については 4 回の登場が保証されます。
しかし、4 については 4 回目の登場があるとしたら 4 回目の 4 より後でないといけないという自己ループが発生していますので、4 は 4 回目の登場がありません。
よってこれも最長数列には絶対にならず、[2->1, 3->2, 4->4] という分類はできません。
つまり [2->a, 3->b, 4->c] という名目の分類が存在するか否かは、依存関係にこのようなループが発生しないか否かを考えればよいことになります。
そしてそれは、「まち針の木」で 1 という針山と 2, 3, 4 というまち針を用意して、
2 は a の頭（a=1 なら針山）に刺す
3 は b の頭（b=1 なら針山）に刺す
4 は c の頭（c=1 なら針山）に刺す
という木が存在するか否かを考えればいいことになります。
3 本のまち針で作る木は 16 通りだとわかっています。
よって、このような依存関係の作り方は 16 通り、ゆえに、最長数列の分類も 16 組であることがわかります。

したがって、n=4 の最長数列の総数は 5184*16 = 82944 となります。


一般の n の場合も同様に考えることができて、
「n-1 本のまち針の木の総数」 * n! * (n-1)! * (n-1)! * …… * (n-1)! （ (n-1)! は全部で n-1 個）
と求められることがわかります。
さて、では「まち針の木」の総数を求める式（証明付き）は？　というのが現状私がたどり着いている最先端です。

どうも、
de Bruijn sequence
と密接な関わりがあるような気がしてまいりました。

管理人さんによるお題は１列ですが、
この左端と右端とを繋げて輪にします。
繋げるにあたり、両端は同じでしたが、片方は除去します。

一列に n^2+1 の要素があったものを
n^2 の要素のある輪にします。

de Bruijn sequence については以下を
御参照ください。
https://en.m.wikipedia.org/wiki/De_Bruijn_sequence

上の記事中で
"The number of distinct de Bruijn sequences B(k, n) is"
とあります。
この記事で、管理人さんからの
お題を調べている私達の目的においては
n=2
で固定で考えてよいです。
B(k, n)ではなく、B(k, 2)
を知りたいのです。
また、この記事における k は
私達が解こうとしていた問題の n に相当します。
このことを意識して
B(k, 2) を求める式をみてください。
さて、こうして得られる数は
輪にしていたものに対応して数えています。
輪を切断して元の一列にするには
k倍する必要があります。

といった………
浅い読み方をしております。
皆様からの御批正をお願いいたします。

なるほど、密接な関わりどころか、ほぼそのものですね。
しかし、2 種類の n 連続で重複を避ける方向から発展してきた都合上、n 種類の 2 連続での話はあんまりないみたいですね。

でも、とりあえず予想している式が正しいという保証ができたことは大きな一歩です。
ありがとうございます。
「この問題はちゃんと解ける問題である」というのは数学において最大のヒントですからね。

その後プログラムを何度か高速化して
n=5の時の4976640000通りが一瞬で求められるようになり、
このプログラムでn=6について求めたところ
約23分で「23219011584000000通り」と求まりました。
（同一数字の連続をなくしたものを数えてn(n-1)^(n-1)を掛けるようにしたのが主な高速化）
それでもn=7は数え方を根本から変えないと無理そうです。

prod(i=0,n-1,floor((n^2-1+i)/n)!)
と
(n!)^n/n
の結果が同じものになるのが面白く、構造を分析すると

n=3
3!*2!*2!*(3^1)=3!*3!*2!=3!*3!*(3!/3)=(3!)^3/3

n=4
4!*3!*3!*3!*(4^2)=4!*4!*4!*3!=4!*4!*4!*(4!/4)=(4!)^4/4

n=5
5!*4!*4!*4!*4!*(5^3)=5!*5!*5!*5!*4!=5!*5!*5!*5!*(5!/5)=(5!)^5/5

n=6
6!*5!*5!*5!*5!*5!*(6^4)=6!*6!*6!*6!*6!*5!=6!*6!*6!*6!*6!*(6!/6)=(6!)^6/6

n=7
7!*6!*6!*6!*6!*6!*6!*(7^5)=7!*7!*7!*7!*7!*7!*6!=7!*7!*7!*7!*7!*7*(7!/7)=(7!)^7/7

････････････････････････････････

２つ目の所がprod(i=0,n-1,floor((n^2-1+i)/n)!)で最後の部分が(n!)^n/n
に対応していく。


ここにDD++さんの記述と重ね合わせると
「n-1 本のまち針の木の総数」 * n! * (n-1)! * (n-1)! * …… * (n-1)!
（ (n-1)! は全部で n-1 個）
と求められることがわかります。


n=3である場合のDD++さんの解説にある
つまり [2->a, 3->b, 4->c] という名目の分類が存在するか否かは、
依存関係にこのようなループが発生しないか否かを考えればよいことになります。
そしてそれは、「まち針の木」で 1 という針山と 2, 3, 4 というまち針を用意して、
2 は a の頭（a=1 なら針山）に刺す
3 は b の頭（b=1 なら針山）に刺す
4 は c の頭（c=1 なら針山）に刺す
という木が存在するか否かを考えればいいことになります。
3 本のまち針で作る木は 16 通りだとわかっています。
（私はいまいち理解が及んでいませんが、この数が4^2の部分に相当しているのか？）


n=5まではコンピュータで
[1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5]
を勝手に並び変えたとき、例の数列の条件が満たされる配列総数が
4976640000
まで確認されているのですから、n=5での
5!*4!*4!*4!*4!*(5^3)=5!*5!*5!*5!*4!=5!*5!*5!*5!*(5!/5)=(5!)^5/5(=4976640000)
における5^3=125は「まち針の木の総数」と解釈できるんですよね。


この形式をたどれば一般にnでの「まち針の木の総数」= n^(n-2)
となりそうなんですが、n>=8 でもそれでいいという証明が必要ということでしょうか？
https://oeis.org/A000272