cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A051168 Triangular array T(h,k) for 0 <= k <= h read by rows: T(h,k) = number of binary Lyndon words with k ones and h-k zeros.

Original entry on oeis.org

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
Offset: 0

Views

Author

Clark Kimberling

Keywords

Comments

T(h,k) is the number of classes of aperiodic binary words of k ones and h-k zeros; 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.
T(2n, n), T(2n+1, n), T(n, 3) match A022553, A000108, A001840, respectively. Row sums match A001037.
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
0 1 5 22 70 200 497 1144 2424 4862 9225 16796 29372 49742 81686 130750 204248
0 1 6 26 91 273 728 1768 3978 8398 16796 32065 58786 104006 178296 297160 482885
0 1 6 30 112 364 1026 2652 6288 13995 29372 58786 112632 208012 371384 643842
0 1 7 35 140 476 1428 3876 9690 22610 49742 104006 208012 400023 742900 1337220
0 1 7 40 168 612 1932 5537 14520 35530 81686 178296 371384 742900 1432613 2674440
...
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)
Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} A054533(d, v) * binomial((n + k)/d, k/d) = S(k, n, v). This was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 1) = T(n + k, k). - Petros Hadjicostas, Jul 09 2019

Examples

			Triangle begins with:
h=0: 1
h=1: 1, 1
h=2: 0, 1, 0
h=3: 0, 1, 1, 0
h=4: 0, 1, 1, 1,  0
h=5: 0, 1, 2, 2,  1,  0
h=6: 0, 1, 2, 3,  2,  1, 0
h=7: 0, 1, 3, 5,  5,  3, 1, 0
h=8: 0, 1, 3, 7,  8,  7, 3, 1, 0
h=9: 0, 1, 4, 9, 14, 14, 9, 4, 1, 0
...
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.

Links

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, A123223, A124814.

Programs

  • 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, Jul 20 2008 *)
  • 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 */
  • PARI
    T(n,k) = if (n==0, 1, (1/n) * sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d,k/d)));
tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, May 16 2018

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_{d <= 2, d|h, d|k} (h/d)*T(h/d, k/d).
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
The prime rows are given by (1+x)^p/p with noninteger coefficients rounded to zero. E.g., for h = 2 below, (1 + x)^2/2 = (1 + 2*x + x^2)/2 = 0.5 + x + 0.5*x^2 gives (0,1,0). - Tom Copeland, Oct 21 2014
T(n,k) = (1/n) * Sum_{d | gcd(n,k)} mu(d) * binomial(n/d, k/d), for n > 0. - Andrew Howroyd, Mar 26 2017
From Petros Hadjicostas, Jun 16 2019: (Start)
O.g.f. for column k >= 1: (x^k/k) * Sum_{d|k} mu(d)/(1 - x^d)^(k/d).
Bivariate o.g.f.: Sum_{n,k >= 0} T(n, k)*x^n*y^k = 1 - Sum_{d >= 1} (mu(d)/d) *log(1 - x^d * (1 + y^d)).
(End)

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.