MENU
176,388

スレッドNo.1328

de Brujin sequence について

「あそびをせんとや」というホームページは大変興味深くよく眺めているのですが,
先日そこにこのような問題が紹介されていました。

例えば4文字A,B,C,Dを並べた文字列で, その部分文字列が, AA,AB,AC,AD,...,DDの
16個の2文字の連鎖パターンをすべて含むようにしたい。17文字で可能か？

2文字A,BであればAABBAだとAA,AB,BB,BAが全て含まれていて, 5文字だから最短という例も紹介されてました。

後日気になって調べていると, k文字を並べた文字列にn文字の連鎖パターンのすべてが部分文字列として含まれているような「循環文字列」という「de Bruijn sequence」という話に検索していて行き当たりました。
そこではk文字を並べた文字列にn文字の連鎖パターンのすべてが部分文字列として含まれているような「循環文字列」をB(k,n)のように表記するとあります。

グラフ理論を用いるなどして, 任意のk,nについてB(k,n)が「可能である」ことは納得できたのですが,
このB(k,n)な循環文字列が(k!)^(k^(n-1))/k^n通りあると書いてあり, その数え方が分かりませんでした。

一番簡単そうなB(2,2), つまりA,Bの2文字で2文字の連鎖パターンをすべて含むAABBのような循環文字列だと,
(2!)^(2^1)/2^2=2^2/2^2=1通りで, なるほど確かにそうだとなるわけです。

B(3,2), つまりA,B,Cの3文字で2文字連鎖... なAABBCCACBのような循環文字列だと,
(3!)^(2^1)/3^2=3^2*2^2/3^2=2^2=4通りな筈ですが, ... これでも一寸どう数えてるのか見当がつきません。

どなたかお知恵を貸してください。

No.1328moonlight2023年7月24日 14:15…
引用して返信編集・削除(未編集)

職場でこの質問を投げたと思うてたのですがどうもネット環境か制限に引っ掛かっていたようで投稿できていませんでした。「あそびをせんとや」さんでは少し解説がされましたが矢張り数え方については言及がありませんでした。どうかよろしくお願いします。

No.1329moonlight2023年7月24日 14:19…
引用して返信編集・削除(未編集)

B(3,2), つまりA,B,Cの3文字で2文字連鎖... なAABBCCACBのような循環文字列だと,
(3!)^(2^1)/3^2=3^2*2^2/3^2=2^2=4通りな筈ですが, ... これでも一寸どう数えてるのか見当がつきません。
と計算されていますが、
これは
B(3,2)=3!^(3^1)/3^2=6^3/9=216/9=24通りになりませんか？
M=[1,1,1,2,2,2,3,3,3]
からなる異なる3つの文字(ここでは1,2,3としておく。)をランダムに並べたとき(9!/(3!^3)=1680(通り))に
前から2つずつを区切って2語からなる単語を作っていくとき(最後の文字に最初の文字をくっつけたものも含む。）
、全て異なるものが構成出来る配列は次の216通りが可能であるが、各配列は9個をサイクリックにずらしていくと
各配列が同じものが9通りずつ次の216(通り)の中に現れる。(例えば1,27,91,57,187,115,133,193,145が同じ配列)
したがって216/9=24(通り)が実質的に異なる配列方法を持つことになる。

1;[1, 1, 2, 1, 3, 2, 2, 3, 3]
2;[1, 1, 2, 1, 3, 3, 2, 2, 3]
3;[1, 1, 2, 2, 1, 3, 2, 3, 3]
4;[1, 1, 2, 2, 1, 3, 3, 2, 3]
5;[1, 1, 2, 2, 3, 1, 3, 3, 2]
6;[1, 1, 2, 2, 3, 2, 1, 3, 3]
7;[1, 1, 2, 2, 3, 3, 1, 3, 2]
8;[1, 1, 2, 2, 3, 3, 2, 1, 3]
9;[1, 1, 2, 3, 1, 3, 3, 2, 2]
10;[1, 1, 2, 3, 2, 2, 1, 3, 3]
11;[1, 1, 2, 3, 3, 1, 3, 2, 2]
12;[1, 1, 2, 3, 3, 2, 2, 1, 3]
13;[1, 1, 3, 1, 2, 2, 3, 3, 2]
14;[1, 1, 3, 1, 2, 3, 3, 2, 2]
15;[1, 1, 3, 2, 1, 2, 2, 3, 3]
16;[1, 1, 3, 2, 2, 1, 2, 3, 3]
17;[1, 1, 3, 2, 2, 3, 3, 1, 2]
18;[1, 1, 3, 2, 3, 3, 1, 2, 2]
19;[1, 1, 3, 3, 1, 2, 2, 3, 2]
20;[1, 1, 3, 3, 1, 2, 3, 2, 2]
21;[1, 1, 3, 3, 2, 1, 2, 2, 3]
22;[1, 1, 3, 3, 2, 2, 1, 2, 3]
23;[1, 1, 3, 3, 2, 2, 3, 1, 2]
24;[1, 1, 3, 3, 2, 3, 1, 2, 2]
25;[1, 2, 1, 1, 3, 2, 2, 3, 3]
26;[1, 2, 1, 1, 3, 3, 2, 2, 3]
27;[1, 2, 1, 3, 2, 2, 3, 3, 1]
28;[1, 2, 1, 3, 3, 2, 2, 3, 1]
29;[1, 2, 2, 1, 1, 3, 2, 3, 3]
30;[1, 2, 2, 1, 1, 3, 3, 2, 3]
31;[1, 2, 2, 1, 3, 2, 3, 3, 1]
32;[1, 2, 2, 1, 3, 3, 2, 3, 1]
33;[1, 2, 2, 3, 1, 1, 3, 3, 2]
34;[1, 2, 2, 3, 1, 3, 3, 2, 1]
35;[1, 2, 2, 3, 2, 1, 1, 3, 3]
36;[1, 2, 2, 3, 2, 1, 3, 3, 1]
37;[1, 2, 2, 3, 3, 1, 1, 3, 2]
38;[1, 2, 2, 3, 3, 1, 3, 2, 1]
39;[1, 2, 2, 3, 3, 2, 1, 1, 3]
40;[1, 2, 2, 3, 3, 2, 1, 3, 1]
41;[1, 2, 3, 1, 1, 3, 3, 2, 2]
42;[1, 2, 3, 1, 3, 3, 2, 2, 1]
43;[1, 2, 3, 2, 2, 1, 1, 3, 3]
44;[1, 2, 3, 2, 2, 1, 3, 3, 1]
45;[1, 2, 3, 3, 1, 1, 3, 2, 2]
46;[1, 2, 3, 3, 1, 3, 2, 2, 1]
47;[1, 2, 3, 3, 2, 2, 1, 1, 3]
48;[1, 2, 3, 3, 2, 2, 1, 3, 1]
49;[1, 3, 1, 1, 2, 2, 3, 3, 2]
50;[1, 3, 1, 1, 2, 3, 3, 2, 2]
51;[1, 3, 1, 2, 2, 3, 3, 2, 1]
52;[1, 3, 1, 2, 3, 3, 2, 2, 1]
53;[1, 3, 2, 1, 1, 2, 2, 3, 3]
54;[1, 3, 2, 1, 2, 2, 3, 3, 1]
55;[1, 3, 2, 2, 1, 1, 2, 3, 3]
56;[1, 3, 2, 2, 1, 2, 3, 3, 1]
57;[1, 3, 2, 2, 3, 3, 1, 1, 2]
58;[1, 3, 2, 2, 3, 3, 1, 2, 1]
59;[1, 3, 2, 3, 3, 1, 1, 2, 2]
60;[1, 3, 2, 3, 3, 1, 2, 2, 1]
61;[1, 3, 3, 1, 1, 2, 2, 3, 2]
62;[1, 3, 3, 1, 1, 2, 3, 2, 2]
63;[1, 3, 3, 1, 2, 2, 3, 2, 1]
64;[1, 3, 3, 1, 2, 3, 2, 2, 1]
65;[1, 3, 3, 2, 1, 1, 2, 2, 3]
66;[1, 3, 3, 2, 1, 2, 2, 3, 1]
67;[1, 3, 3, 2, 2, 1, 1, 2, 3]
68;[1, 3, 3, 2, 2, 1, 2, 3, 1]
69;[1, 3, 3, 2, 2, 3, 1, 1, 2]
70;[1, 3, 3, 2, 2, 3, 1, 2, 1]
71;[1, 3, 3, 2, 3, 1, 1, 2, 2]
72;[1, 3, 3, 2, 3, 1, 2, 2, 1]
73;[2, 1, 1, 2, 2, 3, 1, 3, 3]
74;[2, 1, 1, 2, 2, 3, 3, 1, 3]
75;[2, 1, 1, 2, 3, 1, 3, 3, 2]
76;[2, 1, 1, 2, 3, 3, 1, 3, 2]
77;[2, 1, 1, 3, 1, 2, 2, 3, 3]
78;[2, 1, 1, 3, 1, 2, 3, 3, 2]
79;[2, 1, 1, 3, 2, 2, 3, 3, 1]
80;[2, 1, 1, 3, 2, 3, 3, 1, 2]
81;[2, 1, 1, 3, 3, 1, 2, 2, 3]
82;[2, 1, 1, 3, 3, 1, 2, 3, 2]
83;[2, 1, 1, 3, 3, 2, 2, 3, 1]
84;[2, 1, 1, 3, 3, 2, 3, 1, 2]
85;[2, 1, 2, 2, 3, 1, 1, 3, 3]
86;[2, 1, 2, 2, 3, 3, 1, 1, 3]
87;[2, 1, 2, 3, 1, 1, 3, 3, 2]
88;[2, 1, 2, 3, 3, 1, 1, 3, 2]
89;[2, 1, 3, 1, 1, 2, 2, 3, 3]
90;[2, 1, 3, 1, 1, 2, 3, 3, 2]
91;[2, 1, 3, 2, 2, 3, 3, 1, 1]
92;[2, 1, 3, 2, 3, 3, 1, 1, 2]
93;[2, 1, 3, 3, 1, 1, 2, 2, 3]
94;[2, 1, 3, 3, 1, 1, 2, 3, 2]
95;[2, 1, 3, 3, 2, 2, 3, 1, 1]
96;[2, 1, 3, 3, 2, 3, 1, 1, 2]
97;[2, 2, 1, 1, 2, 3, 1, 3, 3]
98;[2, 2, 1, 1, 2, 3, 3, 1, 3]
99;[2, 2, 1, 1, 3, 1, 2, 3, 3]
100;[2, 2, 1, 1, 3, 2, 3, 3, 1]
101;[2, 2, 1, 1, 3, 3, 1, 2, 3]
102;[2, 2, 1, 1, 3, 3, 2, 3, 1]
103;[2, 2, 1, 2, 3, 1, 1, 3, 3]
104;[2, 2, 1, 2, 3, 3, 1, 1, 3]
105;[2, 2, 1, 3, 1, 1, 2, 3, 3]
106;[2, 2, 1, 3, 2, 3, 3, 1, 1]
107;[2, 2, 1, 3, 3, 1, 1, 2, 3]
108;[2, 2, 1, 3, 3, 2, 3, 1, 1]
109;[2, 2, 3, 1, 1, 2, 1, 3, 3]
110;[2, 2, 3, 1, 1, 3, 3, 2, 1]
111;[2, 2, 3, 1, 2, 1, 1, 3, 3]
112;[2, 2, 3, 1, 3, 3, 2, 1, 1]
113;[2, 2, 3, 2, 1, 1, 3, 3, 1]
114;[2, 2, 3, 2, 1, 3, 3, 1, 1]
115;[2, 2, 3, 3, 1, 1, 2, 1, 3]
116;[2, 2, 3, 3, 1, 1, 3, 2, 1]
117;[2, 2, 3, 3, 1, 2, 1, 1, 3]
118;[2, 2, 3, 3, 1, 3, 2, 1, 1]
119;[2, 2, 3, 3, 2, 1, 1, 3, 1]
120;[2, 2, 3, 3, 2, 1, 3, 1, 1]
121;[2, 3, 1, 1, 2, 1, 3, 3, 2]
122;[2, 3, 1, 1, 2, 2, 1, 3, 3]
123;[2, 3, 1, 1, 3, 3, 2, 1, 2]
124;[2, 3, 1, 1, 3, 3, 2, 2, 1]
125;[2, 3, 1, 2, 1, 1, 3, 3, 2]
126;[2, 3, 1, 2, 2, 1, 1, 3, 3]
127;[2, 3, 1, 3, 3, 2, 1, 1, 2]
128;[2, 3, 1, 3, 3, 2, 2, 1, 1]
129;[2, 3, 2, 1, 1, 3, 3, 1, 2]
130;[2, 3, 2, 1, 3, 3, 1, 1, 2]
131;[2, 3, 2, 2, 1, 1, 3, 3, 1]
132;[2, 3, 2, 2, 1, 3, 3, 1, 1]
133;[2, 3, 3, 1, 1, 2, 1, 3, 2]
134;[2, 3, 3, 1, 1, 2, 2, 1, 3]
135;[2, 3, 3, 1, 1, 3, 2, 1, 2]
136;[2, 3, 3, 1, 1, 3, 2, 2, 1]
137;[2, 3, 3, 1, 2, 1, 1, 3, 2]
138;[2, 3, 3, 1, 2, 2, 1, 1, 3]
139;[2, 3, 3, 1, 3, 2, 1, 1, 2]
140;[2, 3, 3, 1, 3, 2, 2, 1, 1]
141;[2, 3, 3, 2, 1, 1, 3, 1, 2]
142;[2, 3, 3, 2, 1, 3, 1, 1, 2]
143;[2, 3, 3, 2, 2, 1, 1, 3, 1]
144;[2, 3, 3, 2, 2, 1, 3, 1, 1]
145;[3, 1, 1, 2, 1, 3, 2, 2, 3]
146;[3, 1, 1, 2, 1, 3, 3, 2, 2]
147;[3, 1, 1, 2, 2, 1, 3, 2, 3]
148;[3, 1, 1, 2, 2, 1, 3, 3, 2]
149;[3, 1, 1, 2, 2, 3, 2, 1, 3]
150;[3, 1, 1, 2, 2, 3, 3, 2, 1]
151;[3, 1, 1, 2, 3, 2, 2, 1, 3]
152;[3, 1, 1, 2, 3, 3, 2, 2, 1]
153;[3, 1, 1, 3, 2, 1, 2, 2, 3]
154;[3, 1, 1, 3, 2, 2, 1, 2, 3]
155;[3, 1, 1, 3, 3, 2, 1, 2, 2]
156;[3, 1, 1, 3, 3, 2, 2, 1, 2]
157;[3, 1, 2, 1, 1, 3, 2, 2, 3]
158;[3, 1, 2, 1, 1, 3, 3, 2, 2]
159;[3, 1, 2, 2, 1, 1, 3, 2, 3]
160;[3, 1, 2, 2, 1, 1, 3, 3, 2]
161;[3, 1, 2, 2, 3, 2, 1, 1, 3]
162;[3, 1, 2, 2, 3, 3, 2, 1, 1]
163;[3, 1, 2, 3, 2, 2, 1, 1, 3]
164;[3, 1, 2, 3, 3, 2, 2, 1, 1]
165;[3, 1, 3, 2, 1, 1, 2, 2, 3]
166;[3, 1, 3, 2, 2, 1, 1, 2, 3]
167;[3, 1, 3, 3, 2, 1, 1, 2, 2]
168;[3, 1, 3, 3, 2, 2, 1, 1, 2]
169;[3, 2, 1, 1, 2, 2, 3, 1, 3]
170;[3, 2, 1, 1, 2, 2, 3, 3, 1]
171;[3, 2, 1, 1, 3, 1, 2, 2, 3]
172;[3, 2, 1, 1, 3, 3, 1, 2, 2]
173;[3, 2, 1, 2, 2, 3, 1, 1, 3]
174;[3, 2, 1, 2, 2, 3, 3, 1, 1]
175;[3, 2, 1, 3, 1, 1, 2, 2, 3]
176;[3, 2, 1, 3, 3, 1, 1, 2, 2]
177;[3, 2, 2, 1, 1, 2, 3, 1, 3]
178;[3, 2, 2, 1, 1, 2, 3, 3, 1]
179;[3, 2, 2, 1, 1, 3, 1, 2, 3]
180;[3, 2, 2, 1, 1, 3, 3, 1, 2]
181;[3, 2, 2, 1, 2, 3, 1, 1, 3]
182;[3, 2, 2, 1, 2, 3, 3, 1, 1]
183;[3, 2, 2, 1, 3, 1, 1, 2, 3]
184;[3, 2, 2, 1, 3, 3, 1, 1, 2]
185;[3, 2, 2, 3, 1, 1, 2, 1, 3]
186;[3, 2, 2, 3, 1, 2, 1, 1, 3]
187;[3, 2, 2, 3, 3, 1, 1, 2, 1]
188;[3, 2, 2, 3, 3, 1, 2, 1, 1]
189;[3, 2, 3, 1, 1, 2, 2, 1, 3]
190;[3, 2, 3, 1, 2, 2, 1, 1, 3]
191;[3, 2, 3, 3, 1, 1, 2, 2, 1]
192;[3, 2, 3, 3, 1, 2, 2, 1, 1]
193;[3, 3, 1, 1, 2, 1, 3, 2, 2]
194;[3, 3, 1, 1, 2, 2, 1, 3, 2]
195;[3, 3, 1, 1, 2, 2, 3, 2, 1]
196;[3, 3, 1, 1, 2, 3, 2, 2, 1]
197;[3, 3, 1, 1, 3, 2, 1, 2, 2]
198;[3, 3, 1, 1, 3, 2, 2, 1, 2]
199;[3, 3, 1, 2, 1, 1, 3, 2, 2]
200;[3, 3, 1, 2, 2, 1, 1, 3, 2]
201;[3, 3, 1, 2, 2, 3, 2, 1, 1]
202;[3, 3, 1, 2, 3, 2, 2, 1, 1]
203;[3, 3, 1, 3, 2, 1, 1, 2, 2]
204;[3, 3, 1, 3, 2, 2, 1, 1, 2]
205;[3, 3, 2, 1, 1, 2, 2, 3, 1]
206;[3, 3, 2, 1, 1, 3, 1, 2, 2]
207;[3, 3, 2, 1, 2, 2, 3, 1, 1]
208;[3, 3, 2, 1, 3, 1, 1, 2, 2]
209;[3, 3, 2, 2, 1, 1, 2, 3, 1]
210;[3, 3, 2, 2, 1, 1, 3, 1, 2]
211;[3, 3, 2, 2, 1, 2, 3, 1, 1]
212;[3, 3, 2, 2, 1, 3, 1, 1, 2]
213;[3, 3, 2, 2, 3, 1, 1, 2, 1]
214;[3, 3, 2, 2, 3, 1, 2, 1, 1]
215;[3, 3, 2, 3, 1, 1, 2, 2, 1]
216;[3, 3, 2, 3, 1, 2, 2, 1, 1]

と解釈すればよいと思います。

No.1331GAI2023年7月24日 18:58…
引用して返信編集・削除(編集済: 2023年07月24日 19:23)

暑い中での投稿で計算間違いや思い違いがあったかもしれません。
どう考えればあの計算式が得られるのかが知りたいのです。（適当な例を挙げたのが間違いだったかもしれません。）

No.1332moonlight2023年7月24日 22:01…
引用して返信編集・削除(未編集)

「数学感動秘話」>「目指せ！最長不倒」
の話ですかね？

No.1333DD++2023年7月26日 10:44…
引用して返信編集・削除(未編集)

このスレッドに返信

ロケットBBS

Page Top