・de Brujin sequence　　 　 　 　 　 　 　 　 　 　 moonlight 氏

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

　例えば、４文字 A、B、C、D を並べた文字列で、その部分文字列が、

　AA、AB、AC、AD、・・・、DD

の１６個の２文字の連鎖パターンをすべて含むようにしたい。１７文字で可能か？

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

　後日、気になって調べていると、ｋ文字を並べた文字列に、ｎ文字の連鎖パターンのすべ
てが部分文字列として含まれているような「循環文字列」という「de Bruijn sequence（デ・ブラ
イン数列）」の話に、検索していて行き当たりました。

　そこでは、ｋ文字を並べた文字列に、ｎ文字の連鎖パターンのすべてが部分文字列として
含まれているような「循環文字列」を、B(ｋ，ｎ) のように表記するとあります。

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

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

　B(3，2)　つまり、A、B、C の３文字で、２文字連鎖... な、AABBCCACB のような循環文字
列だと、(3!)^(2^1)/3^2=3^2*2^2/3^2=2^2=4（通り）な筈ですが、... これでも一寸どう
数えてるのか見当がつきません。どなたかお知恵を貸してください。

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


　GAI さんからのコメントです。（令和５年７月２４日付け）

　B(3，2) で、3!^(3^1)/3^2=6^3/9=216/9=24 （通り）　になりませんか？

　M=[1,1,1,2,2,2,3,3,3] からなる異なる３つの文字（ここでは、1、2、3 としておく。)をランダムに

並べたとき(9!/(3!^3)=1680 (通り)) に、前から２つずつを区切って、２語からなる単語を作って

いくとき(最後の文字に最初の文字をくっつけたものも含む。）、全て異なるものが構成出来る

配列は、次の 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]

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


　ｍｏｏｎｌｉｇｈｔ さんからのコメントです。（令和５年７月２４日付け）

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


　DD++ さんからのコメントです。（令和５年７月２６日付け）

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


　ＧＡＩ さんからのコメントです。（令和５年９月２５日付け）

　Be Bruijn 数列の変形バージョンです。

　１６個のビットの列　0000100110101111　があれば、これを繰り返し並べると、

　00001001101011110000100110101111･････

となり、これを前から連続して４個ずつ横にずらしながら区切っていくと、

0000　、0001　、0010　、0100　、1001　、0011　、0110　、1101　、1010　、0101　、1011　、

0111　、1111　、1110　、1100　、1000

と全て異なる１６（２^4)種類のものが構成されていく。以下同様に元に戻るものが作られて

いく。

0000　、0001　、・・・・・

　そこで、今度は、連続する４個ではなく、元にやはり 0,1 のものからなるある１６個のビット

列があったとき（この１６連の配列は以降同じものが繰り返し並べられていくものとする。）、

見える場所がその配列の 1,2,4,8 番目のみが見える穴あき板に覆われているものとする。

　その板を一コマずつずらしていった時、見える４個の数字列がやはり全て異なる１６個の

種類を繰り返し出現させるような元の１６ビット配列は何かを求めて欲しい。

　上の配列では、

0001　、0011　、0000　、0101　、1010　、0011（ここで重複が起こる)　、0101　、････

が見えてくる数となる。



　　以下、工事中！



　　　　　　　　　　　　　　投稿一覧に戻る