😊出会いの泉😊

DD++ さん、誤りをご指摘いただきありがとうございます。
計算を見直したら、はじいてはいけない解をはじいていました。
（解）は修正しました。

n本の場合に刺し方がF(n)通りあるとする。
ただし、n=0の場合はF(0)=1とする。

まち針がn+1本ある時を考える。
特定の1本のまち針[赤]に着目し、その先端側にあるまち針の本数をi本、頭側にあるまち針の本数をn-i本とする(0≦i≦n)。
n本のまち針をこの2グループに分ける方法はCombination(n,i)通り。
先端側にあるi本のまち針の刺し方はF(i)通りで、その各々に対しまち針[赤]を刺す場所がi+1通り(針山とi本のまち針の頭)。
頭側にあるn-i本のまち針の刺し方はF(n-i)通り(まち針[赤]の頭を針山とみなせばよいため)。
よって漸化式は、
F(n+1) = Σ[i=0...n] Combination(n,i) * F(i) * (i+1) * F(n-i)
となる。

F(n)の式の形は予想できているので数学的帰納法で示せばよい。

……のですが、式変形できずに詰まっています。

そうなんですよ。

Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n

Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)

このどっちかが成り立ってくれれば話は終わりなんですけど、
「私の備忘録」->「代数学分野」->「二項係数の性質」
にもそれっぽい式はないんですよね。
二項係数関係の総和は、底か指数かどちらか固定されていたら「よくある問題」なんですが、両方変わっていくのはほとんど見たことがありません。

どれが積でどれが添字か全くわからないので、添字は [ ] で書くなど区別しやすい表記にしてもらうことはできますか？

やっと情報を見つけました。
https://en.m.wikipedia.org/wiki/Cayley%27s_formula

こっちにある証明法がわかりやすかったので、この問題の用語や数値に合わせながら翻訳します。
https://en.m.wikipedia.org/wiki/Double_counting_(proof_technique)


まず、針山もまち針とみなします。
つまり「針山をまち針の頭に刺す」が、なぜかできそうな気分になっておきます。

以下の操作を行います。

(1) n+1 本のまち針（本当は針山であるものも含む）を机上に並べます。

(2) n+1 個の頭から 1 つを選びます。そして、その頭とつながっておらず、かつどこにも刺していない針先 n 個のうち 1 つを選びます。選んだ針先を選んだ頭に刺します。

(3) n+1 個の頭から 1 つを選びます。そして、その頭とつながっておらず、かつどこにも刺していない針先 n-1 個のうち 1 つを選びます。選んだ針先を選んだ頭に刺します。

(4) さらに繰り返し、合計 n 回行います。選べる針先の選択肢が 1 つずつ減っていき、n 回目では 1 個のうち 1 個を選んで刺すことになります。

(5) ある 1 本のまち針の頭に他の n 本が全部刺さっているオブジェ（木と呼びたいが根っこが刺さってない……）ができたら操作終了です。

各選択肢の個数を考えると、この操作の方法は全部で (n+1)^n * n! 通りあります。
ただし、同じ形のオブジェがまち針を刺す順番違いで n! 個ずつできるので、オブジェの種類は (n+1)^n 通りです。

そして、このオブジェには n+1 本の各まち針が一番下になるパターンが (n+1)^(n-1) 通りずつ含まれます。
つまり、まち針とみなしていた針山の上に本物のまち針 n 本が全部刺さって、きちんと題意通りの形になっているパターンは (n+1)^(n-1) 通りとなります。


これで「最長数列の総数」も解決したことになります。
あるいは、考え方を流用すれば「まち針の木」の問題に帰着させるまでもなくあっちを解けるかも。
上手い説明ができるかどうか考えてみます。

そして残った No.1051 の恒等式の謎。
組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。

DD++さん
> そして残った No.1051 の恒等式の謎。
> 組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。

式変形できました。
nCk を C[n,k] と書くことにします。

事前準備その１
C[n,i] * C[n-i,j] = C[n,j] * C[n-j,i]
（証明略）

事前準備その２
f(k)をkのn-1次以下の多項式として、
Σ[k=0...n] C[n,k] * (-1)^k * f(k) = 0
（証明は、「私の備忘録」->「代数学分野」->「二項係数の性質」の中の性質(5)と(28)、あるいは
　平成２３年１１月１９日から２６日にかけてのらいさん・攻略法さん・ａｔ さん・ＦＮさんのやりとり を参照）


それでは本番 (2行目から3行目の置き換えはh=n-k)
Σ[h=0...n] C[n,h] * (h+1)^h * (n-h+1)^(n-h-1)
= Σ[h=0...n] C[n,n-h] * (n-h+1)^(n-h-1) * (h+1)^h
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * (n-k+1)^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * ((n+2)-(k+1))^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * { Σ[m=0...n-k] C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-k-m) }
= Σ[k=0...n] Σ[m=0...n-k] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= Σ[m=0...n] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] Σ[k=0...n-m] C[n,m] * C[n-m,k] * (n+2)^m * (-1)^(n-m) * (-1)^k * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * { Σ[k=0...n-m] C[n-m,k] * (-1)^k * (k+1)^(n-m-1) }
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * 0
= (n+2)^n

おお、なるほど、そんな方法で k+1 の指数から k を消せるとは。
これで

> Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n
>
> Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)

の上の式は示されましたね。
下の式はりらひいさんの証明の 1 行目（ h をそのまま k に書き換え）と 3 行目を足したものが最終結果の 2 倍になることから得られます。

これらの総和、いつかどこかでまた使うことがあるかもしれないので、証明方法ともども覚えておきたいと思います。
ありがとうございます。

先日の式変形（No.1068）をもう一度眺めていて思ったのですが、次の式

(a+b)^n / a = Σ[k=0...n] C[n,k] * (a+k)^(k-1) * (b-k)^(n-k)

が成り立つんですね。
ただし、 a≠0とします。
計算は先日の3行目～最終行とまったく同様です。
先日の式は、 a=1, b=n+1 の場合にあたります。

a,bは整数に限らず実数でいけるのが面白いところですね。

ある本に、無限ということばが、自然に出ています。
限りなくとか、無数という言葉が、出てきます。形式主義と公理主義、
直観主義が、混雑しています。

https://shayashiyasugi.com/wwwshayashijp/HistoryOfFOM/Axiomatik/axiomatism.html

長いですが、興味がおありの方もいらっしゃることかと。

正しい指摘だと思います。

どう投げても、底面が上になることは、有り得ない。
それに、元々、サイコロというのは、どの面も合同でないと
サイコロの意味を成さないと思います。

> 四角錘
漢字は「四角錐」だと思います。

> 重心をどこにとれば、長さの比をどのようにすれば、いいのか？物理的な問題でしょうか？
四角錐の材質・床の材質・反発係数などが関係しそうな気がしますので、物理の問題で、しかも与えられた条件では答えが出せない気がします。


> どの面も合同でないとサイコロの意味を成さない
そうでもないと思います。例えば「両側を削った元々六角柱の鉛筆」のような形なら、削った円錐面が下になることがありませんので、ちゃんと（理論的には）確率1/6ずつのサイコロになると思います。

四角錐のサイコロは古代メソポタミアで実際に使われていたようですね。発掘されているとのこと。

ふと思ったのですが、
ニつの合同な正五角錐を、底面どうしで貼りつけた形状のものが実際には便利ではないかと。美的には十ある面が正三角形のものがよいかもですね。

「正双五角錐」という名前があるようですね。
https://www.wikiwand.com/ja/%E5%8F%8C%E8%A7%92%E9%8C%90
↑ここに「双五角錐」と書かれた図形がありますが、
見た感じ「正双五角錐」になっているようです。
この形だと平べったくなってサイコロのように振った時にどうかなと思ったのですが、
コマのように回せますのでかえって面白いかも知れませんね。

正ねじれ双五角錐によるサイコロというものがあるのでしたか。

https://ja.m.wikipedia.org/wiki/%E3%81%AD%E3%81%98%E3%82%8C%E5%8F%8C%E8%A7%92%E9%8C%90#/media/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%3A10-sided_dice_250.png

gp > for(n=1,10,print(n";",\
-sum(k=1,n+1,(-1)^k*k*binomial(n+1,k)*(n+1)^(n-k)), " VS ",n^n))

に関しては、{(n+1)-1}^n を二項展開した後少し変形しただけですかね。
nCk を含む総和公式は、
「底が k に依存しない」場合は二項展開の式で変数の中身をうまく選んだ式あることが多く、
「指数が k に依存しない」場合は二項展開の式に何か掛けたり割ったりしながら微積分を繰り返して作った式であることが多いです。

今にして思えば、/n がついているのは最初の数を 1 に限定しているせいですね。
最初の数も任意にしてよいのであれば、最長数列の総数は (n!)^n 通りというとても整った結果になります。
また、計算方法も先頭の数は任意である方がやりやすそうです。

ということで、「まち針の木」の方で wikipedia から拾ってきた発想をこの問題用に書き直しつつ、「n まで使える場合の最長数列の総数は (n!)^n 通りである」の証明を以下に記述します。
No.1041 の内容と重複する部分も含みます。
わかりにくければ、トランプを使って実際に手を動かすと助けになると思います。


条件を満たすような数列を以下のような方法で作ることを考えます。

1 から n までのカードの組を n セット用意します。
それぞれを適当な順に積み重ねて、各山に 1 番から n 番までの番号をつけておきます。

最初に初項 a[1] として 1 以上 n 以下の数を選びます。
a[1] 番の山の一番上のカードを手に取り、書いてあった数字を a[2] とし、カードは破棄します。
a[2] 番の山の一番上のカードを手に取り、書いてあった数字を a[3] とし、カードは破棄します。
以下、同様に繰り返します。
a[m] 番の山の一番上を手に取ろうとしたら既にその山にカードがなかった場合、a[m] を末項として数列を終了します。

[例1] n=3, a[1]=1 で各山が上から順に
1 番の山：1, 3, 2
2 番の山：2, 1, 3
3 番の山：2, 3, 1
の場合、数列は 1, 1, 3, 2, 2, 1, 2, 3, 3, 1 となります。

[例2] n=3, a[1]=1 で、各山が上から順に
1 番の山：1, 3, 2
2 番の山：2, 1, 3
3 番の山：1, 2, 3
の場合、数列は 1, 1, 3, 1, 2, 2, 1 となります。

[例3] n=3, a[1]=1 で、各山が上から順に
1 番の山：1, 3, 2
2 番の山：2, 1, 3
3 番の山：1, 3, 2
の場合、数列は 1, 1, 3, 1, 2, 2, 1 となります。

n^2+1 項続く最長数列ができる場合というのは、n^2 枚ある全てのカードを破棄できる場合ということになります。
そして、
「最長数列の内容」
「全て破棄できるようにカードを積み重ねて a[1] を選ぶ方法」
が一対一に対応することは数列の作り方からすぐにわかるので、結局カードを全部破棄できるような場合の数を考えればいいことになります。

では、カードを全て破棄することに関していくつか考察を行います。

まず、この操作は a[1] と異なる数のカードで終わることは絶対にありません。
しかも、終わったときには必ず a[1] と同じ数のカードが全ての山から破棄されています。
なぜなら、どこかの山でカードが足りなくなるのは「全ての山から a[1] と同じ数のカードを引く」を達成し、最初の 1 回とあわせて a[1] 番の山からカードを引くのが n+1 回目になるとき以外ありえないからです。

そして、a[1] と異なる数のカードも全て破棄されるかどうかは、a[1] 番以外の山の一番下のカードだけ見ればわかります。

例えば [例1] の場合、まず、a[1]=1 なので 1 のカードは全て破棄されることがわかります。
次に、3 のカードは全て破棄されることもわかります。
なぜなら 3 番の山の一番下に 1 のカードがあり、「3 のカードが全て破棄されるまで 3 番の山の 1 のカードが破棄できない」という状態になっているからです。
終わるまでに必ず 1 のカードが全て破棄されるのですから、その前に 3 のカードが全て破棄されることも達成されなければなりません。
さらに、2 のカードも全て破棄されることがわかります。
なぜなら 2 番の山の一番下に 3 のカードがあり、「2 のカードが全て破棄されるまで 2 番の山の 3 のカードが破棄できない」という状態になっているからです。
終わるまでに 3 のカードが全て破棄されることは先ほど確認したので、その前に 2 のカードが全て破棄されることも達成されなければなりません。
よって、[例1] は、実際に数列を作ってみなくても、1 も 2 も 3 も全て破棄される、つまり最長数列ができることがわかります。

一方で [例2] の場合、3 のカードが全て破棄されることはありません。
なぜなら 3 番の山の一番下に 3 のカードがあり、「3 のカードが全て破棄されるまで 3 番の山の 3 のカードが破棄できない」という状態になっているからです。
一般に、a[1]≠x で x 番の山の一番下に x のカードがある場合、その山は絶対に残ってしまいます。
よって、[例2] は、実際に数列を作ってみなくても、最長数列にはならないことがわかります。

また、[例3] の場合も、2 および 3 のカードが全て破棄されることはありません。
なぜなら 2 番の山の一番下に 3 のカードがあり、同時に 3 番の山の一番下に 2 のカードがあるため、
「2 のカードが全て破棄されるまで 2 番の山の 3 のカードが破棄できない」
「3 のカードが全て破棄されるまで 3 番の山の 2 のカードが破棄できない」
という状態になっているからです。
一般に、このような依存関係のループが発生すると、それらの山は絶対に残ってしまいます。
（[例2] も単独でループしているとみなすことができます）
よって、[例3] は、実際に数列を作ってみなくても、最長数列にはならないことがわかります。

ループが存在しなければ、全ての数のカードについて直接的または間接的に a[1] と同じ数のカードを全て破棄する前にそちらを全て破棄する必要があり、最長数列ができることが確定します。
よって、最長数列になるどうかは、積み重ねるときに a[1] 番以外の山の一番下に来るカードでループが発生しないかどうかだけを考えればいいことになります。

さて、では、カードを無作為に積み重ねて初項も無作為に選んだ場合に、最長数列を作れる確率がどのくらいになるか考えます。

まず、無作為にカードを積み重ねつつ初項を無作為に選ぶ方法として以下の手順を採用します。

1 から n までのカード 1 組をシャッフルします。その後、1 番から n 番までの番号を 1 つ無作為に選び、この山の番号とします。
改めて別の 1 から n までのカード 1 組をシャッフルします。その後、1 番から n 番までの番号のうち重複しないものを 1 つ無作為に選び、この山の番号とします。
これを n 回繰り返すと、1 番から n 番までの山が完成します。
そして、最後に作った山の番号を a[1] として採用します。

この作り方であれば、n 個の山の積み重ね方 (n!)^n 通りと a[1] の選び方 n 通りの組、全 n*(n!)^n 通りの起こりやすさが同様に確からしいといえます。

ここで、確率 P[k] (0≦k≦n) を「この山の作り方で k 個の山を作った段階で、最後に残ることが確定した山がまだどこにもない確率」と定義します。
もちろん P[0]=1 です。

このとき 1 - P[k+1]/P[k] は「k 個の山を作った段階で最後に残ることが確定した山がまだどこにもないという条件のもとで、k+1 個目の山を作ったせいで最後に残ることが確定した山ができてしまう条件付き確率」です。

これは、0≦k≦n-2 の場合、k+1 個目の山をシャッフルしたときに一番下にきたカードが x だったとして、
・x 番の山が k 番目までにまだなく、その x 番をk+1 番目の山につけてしまった
・x 番の山が k 番目までにもうあり、「x 番の山の一番下のカードは y」「y 番の山の一番下のカードは z
」……と辿って行き着いた未使用番号を k+1 番目の山につけてしまった
のどちらかが起こる確率であり、つまりは一番下のカードが何であるかに関係なく残っている n-k 個の番号から特定の 1 個を引いてしまう確率になります。

よって、
1 - P[k+1]/P[k] = 1/(n-k)
なので、
P[k+1]/P[k] = 1 - 1/(n-k) = (n-k-1)/(n-k)
であり、
P[n-1] = (1/2)*P[n-2] = (1/2)*(2/3)*P[n-3] = …… = (1/2)*(2/3)*……*((n-1)/n)*P[0] = 1/n
となります。
最後に作る山は、どんな順序になっても、a[1] の選び方を考えれば確率に影響は与えません。
よって、
P[n] = P[n-1] = 1/n
です。

これで、「n 個の山を無作為に作り、初項 a[1] を無作為に選んだ場合に、最長数列を作れる確率は 1/n である」ことがわかりました。

ところで、この山の作り方は n*(n!)^n 通りが同様に確からしく作れる方法でした。
つまり、最長数列を作れるようにカードの積み重ねて a[1] を選ぶ方法がそのうち N[n] 通りであるとすると、古典的確率の定義より
N[n] / {n*(n!)^n} = 1/n
となります。

したがって分母を払って
N[n] = (n!)^n
が得られました。

お求めになっているものとは異なりますけれども。
３人で。

３人のうちひとりを除き２人が
１回こっきりのジャンケンをします。
この２人で勝負がつけばそれでよし
引き分けならばジャンケンに参加しなかった
者の勝ちとします。

勝率は平等です。

n 人で n 手だといかがでしょうか。

出した手の総和を mod n で。

mod n で考えると、全て同数であることを知りました。
具体的に、勝敗は、どうすればよいですか？
教えてください。

4人でジャンケンをします。
各人にはユニークな背番号をつけます。
背番号は、0、1、2、3 からつけます。
各人が出せる手は、0、1、2、3 のうちどれかひとつとします。
ジャンケンを一回おこないます。
たとえば、
1,0,2,1
という結果だとします。
総和を mod 4 で求めます。
1+0+2+1 ≡ 0 (mod 4)
これにより
背番号 0 のものが勝ちとします。

私が意図していたのは上のようなアルゴリズムです。

さて、ご質問ですが。
《mod n で考えると、全て同数であることを知りました。》
上にあげた手数が4のときのアルゴリズムの脈絡で言えば、
0,0,0,0
1,1,1,1
2,2,2,2
3,3,3,3
という4つのケースについてお尋ねになって
いらっしゃるのでしょうか？
ご質問の意図するところを掴みかねましたが
とりあえず、こういうご趣旨であろうと
仮定いたしまして。

上の4つのケースのどれであっても
mod 4 では総和が 0 と合同ですので
事前にきめておいた背番号が 0 の者を
勝ちとしたく思います。

《mod n で考えると、全て同数であることを知りました。》
は、ｎ人が、出した手を和してｍｏｄ n をとると、
０，１、…、n-１まで、同じ場合の数になるという意味です。
最初、３人、４人で調べました。山なり対称になる。ｎ人でも、
どの場合の数も、ｎ^(n-1)となることが、確認できました。
各人に、ナンバリングするところが秀逸ですね。
①一人の勝者が決まる。②引き分けがない
じゃんけんと違い、全て同じ手の時、０番の人が勝つのが意外ですね。
しばらく、考えてみると、二回目以降はどうなるか気になりました。
ｎ人を、順位づけするという目的であれば、１～ｎの番号くじを引くのが、簡明ですね。くじの準備がいりますが。

多分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