|
| |
|
|
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.
|
|
37
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,18
|
|
|
COMMENTS
| 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
Comment from R. J. Mathar, Jul 31 2008. (Start): This triangle may also be regarded as the square array A(r,n), the n-th term of the r-th Witt transform of the all-1 sequence, r>=1, n>=0, read by antidiagonals:
This array begins as follows:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
0 1 2 3 5 7 9 12 15 18 22 26 30 35 40 45 51 57 63
0 1 2 5 8 14 20 30 40 55 70 91 112 140 168 204 240 285 330
0 1 3 7 14 25 42 66 99 143 200 273 364 476 612 775 969 1197 1463
0 1 3 9 20 42 75 132 212 333 497 728 1026 1428 1932 2583 3384 4389 5598
0 1 4 12 30 66 132 245 429 715 1144 1768 2652 3876 5537 7752 10659 14421 19228
0 1 4 15 40 99 212 429 800 1430 2424 3978 6288 9690 14520 21318 30624 43263 60060
0 1 5 18 55 143 333 715 1430 2700 4862 8398 13995 22610 35530 54477 81719 120175 173583
0 1 5 22 70 200 497 1144 2424 4862 9225 16796 29372 49742 81686 130750 204248 312455 468611
0 1 6 26 91 273 728 1768 3978 8398 16796 32065 58786 104006 178296 297160 482885 766935 1193010
0 1 6 30 112 364 1026 2652 6288 13995 29372 58786 112632 208012 371384 643842 1086384 1789515 2882934
0 1 7 35 140 476 1428 3876 9690 22610 49742 104006 208012 400023 742900 1337220 2340135 3991995 6653325
0 1 7 40 168 612 1932 5537 14520 35530 81686 178296 371384 742900 1432613 2674440 4847208 8554275 14732005
...
It is essentially symmetric: A(r,r+i)=A(r,r-i+1).
Some of the diagonals are:
A(r,r+1): A000108
A(r,r): A022553
A(r,r-1): A000108
A(r,r+2): A000150
A(r,r+3): A050181
A(r,r+4): A050182
A(r,r+5): A050183
A(r,r-2): A000150 (End)
|
|
|
LINKS
| Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160.
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}; ...
|
|
|
MAPLE
| A := proc(r, n) local gf, d, genf; genf := 1/(1-x) ; gf := 0 ; for d in numtheory[divisors](r) do gf := gf + numtheory[mobius](d)*(subs(x= x^d, genf))^(r/d) ; od: gf := expand(gf/r) ; coeftayl(gf, x=0, n) ; end proc:
A051168 := proc(n, k) if n<=1 then 1; elif n=0 or n=k then 0; else A(n-k, k) ; end if;
end proc:
seq(seq(A051168(n, k), k=0..n), n=0..10) ; # R. J. Mathar, Mar 29 2011
|
|
|
MATHEMATICA
| Table[If[n===0, 1, 1/n Plus@@(MoebiusMu[ # ]Binomial[n/#, k/# ]&/@ Divisors[GCD[n, k]])], {n, 0, 12}, {k, 0, n}] - Wouter Meeussen (wouter.meeussen(AT)pandora.be), Jul 20 2008
|
|
|
PROG
| (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, A185158.
Sequence in context: A131026 A014604 A015199 * A163528 A160806 A191411
Adjacent sequences: A051165 A051166 A051167 * A051169 A051170 A051171
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Clark Kimberling (ck6(AT)evansville.edu)
|
| |
|
|
