MENU
276,498

スレッドNo.1019

祝ゎヌルデンりィヌク

月・日を自䞻的に䌑みにしおしたえば、九連䌑ずなる今幎のゎヌルデンりィヌク。その連䌑も埌半に入り、そろそろ疲れが出おくるころ。
次の問題で、疲れを癒しおください。
長さの数列、、・・・、があり、次の性質を満たす。
各項は、以䞊以䞋の敎数
≠で、 ならば、(+1)≠(+1)
この性質を持぀数列で、が最倧ずなるものを構成しおください。

匕甚しお返信線集・削陀(線集枈: 2023幎05月03日 15:46)

倚分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個で、巊右の端が同じになる
列ができあがりたす。

論理が飛んでいたすがご容赊ください。

匕甚しお返信線集・削陀(線集枈: 2023幎05月04日 14:09)

䜿える数字が{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]

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

匕甚しお返信線集・削陀(線集枈: 2023幎05月04日 15:28)

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

匕甚しお返信線集・削陀(未線集)

このスレッドに返信

このスレッドぞの返信は締め切られおいたす。

ロケットBBS

Page Top