|
Search: id:A051168
|
|
|
| A051168 |
|
Triangular array T read by rows: T(h,k) = number of classes of aperiodic binary words of k 1's and h-k 0's; words u,v are in the same class if v is a cyclic permutation of u (e.g. u=111000, v=110001) and a word is aperiodic if not a juxtaposition of 2 or more identical subwords. |
|
+0
32
|
|
| 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 3, 2, 1, 0, 0, 1, 3, 5, 5, 3, 1, 0, 0, 1, 3, 7, 8, 7, 3, 1, 0, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 0, 1, 6
(list; table; graph; listen)
|
|
|
OFFSET
|
0,18
|
|
|
COMMENT
|
T(h,k)=number of Lyndon words of k 1's and h-k 0's.
T(2n, n), T(2n+1, n), T(n, 3) match A022553, A000108, A001840, respectively. Row sums match A001037.
1-x-y = Product_{i,j} (1-x^i*y^j)^T(i+j,j) where i>=0,j>=0 are not both zero. - Michael Somos Jul 03 2004
|
|
LINKS
|
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Index entries for sequences related to Lyndon words
|
|
FORMULA
|
T(h, k)=1 for (h, k) in {(0, 0), (1, 0), (1, 1)}; T(h, k)=0 if h>=2 and k=0 or k=h. Otherwise, T(h, k)=(1/h)*(C(h, k)-S(h, k)), where S(h, k)=Sum{(h/d)*T(h/d, k/d): d<=2, d|h, d|k}.
|
|
EXAMPLE
|
T(6,3) counts classes {111000},{110100},{110010}, each of 6 aperiodic. The class {100100} contains 3 periodic words, counted by T(3,1) as {100}, consisting of 3 aperiodic words 100,010,001.
Rows: {1}; {1,1}; {0,1,0}; ...
|
|
PROGRAM
|
(PARI) T(n, k)=local(A, ps, c); if(k<0|k>n, 0, if(n==0&k==0, 1, A=x*O(x^n)+y*O(y^n); ps=1-x-y+A; for(m=1, n, for(i=0, m, c=polcoeff(polcoeff(ps, i, x), m-i, y); if(m==n&i==k, break(2), ps*=(1-y^(m-i)*x^i+A)^c))); -c)) /* Michael Somos Jul 03 2004 */
|
|
CROSSREFS
|
Columns 1-11: A000012, A004526(n-1), A001840(n-4), A006918(n-4), A011795(n-1), A011796(n-6), A011797(n-1), A031164(n-9), A011845, A032168, A032169. See also A000150.
Cf. A047996, A052307, A052314, A092964.
Sequence in context: A131026 A014604 A015199 this_sequence A133418 A029390 A108040
Adjacent sequences: A051165 A051166 A051167 this_sequence A051169 A051170 A051171
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Clark Kimberling (ck6(AT)evansville.edu)
|
|
|
Search completed in 0.003 seconds
|
