cp's OEIS Frontend

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.

%I A051168 #107 Feb 05 2021 21:15:26
%S A051168 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,
%T A051168 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,
%U A051168 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
%N 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.
%C A051168 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.
%C A051168 T(2n, n), T(2n+1, n), T(n, 3) match A022553, A000108, A001840, respectively. Row sums match A001037.
%C A051168 From _R. J. Mathar_, Jul 31 2008: (Start)
%C A051168 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:
%C A051168 This array begins as follows:
%C A051168 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
%C A051168 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
%C A051168 0 1 2 3 5 7 9 12 15 18 22 26 30 35 40 45 51 57 63
%C A051168 0 1 2 5 8 14 20 30 40 55 70 91 112 140 168 204 240 285 330
%C A051168 0 1 3 7 14 25 42 66 99 143 200 273 364 476 612 775 969 1197 1463
%C A051168 0 1 3 9 20 42 75 132 212 333 497 728 1026 1428 1932 2583 3384 4389 5598
%C A051168 0 1 4 12 30 66 132 245 429 715 1144 1768 2652 3876 5537 7752 10659 14421 19228
%C A051168 0 1 4 15 40 99 212 429 800 1430 2424 3978 6288 9690 14520 21318 30624 43263 60060
%C A051168 0 1 5 18 55 143 333 715 1430 2700 4862 8398 13995 22610 35530 54477 81719 120175
%C A051168 0 1 5 22 70 200 497 1144 2424 4862 9225 16796 29372 49742 81686 130750 204248
%C A051168 0 1 6 26 91 273 728 1768 3978 8398 16796 32065 58786 104006 178296 297160 482885
%C A051168 0 1 6 30 112 364 1026 2652 6288 13995 29372 58786 112632 208012 371384 643842
%C A051168 0 1 7 35 140 476 1428 3876 9690 22610 49742 104006 208012 400023 742900 1337220
%C A051168 0 1 7 40 168 612 1932 5537 14520 35530 81686 178296 371384 742900 1432613 2674440
%C A051168 ...
%C A051168 It is essentially symmetric: A(r,r+i) = A(r,r-i+1).
%C A051168 Some of the diagonals are:
%C A051168 A(r,r+1): A000108
%C A051168 A(r,r): A022553
%C A051168 A(r,r-1): A000108
%C A051168 A(r,r+2): A000150
%C A051168 A(r,r+3): A050181
%C A051168 A(r,r+4): A050182
%C A051168 A(r,r+5): A050183
%C A051168 A(r,r-2): A000150 (End)
%C A051168 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
%H A051168 Andrew Howroyd, <a href="/A051168/b051168.txt">Table of n, a(n) for n = 0..1274</a>
%H A051168 Freddy Cachazo and Nick Early, <a href="https://arxiv.org/abs/2010.09708">Planar Kinematics: Cyclic Fixed Points, Mirror Superpotential, k-Dimensional Catalan Numbers, and Root Polytopes</a>, arXiv:2010.09708 [math.CO], 2020.
%H A051168 A. Elashvili and M. Jibladze, <a href="http://dx.doi.org/10.1016/S0019-3577(98)80021-9">Hermite reciprocity for the regular representations of cyclic groups</a>, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238; MR1691428 (2000c:13006).
%H A051168 A. Elashvili, M. Jibladze, and D. Pataraia, <a href="http://dx.doi.org/10.1023/A:1018727630642">Combinatorics of necklaces and "Hermite reciprocity"</a>, J. Algebraic Combin. 10 (1999), no. 2, 173-188; MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
%H A051168 M. L. Fredman, <a href="https://doi.org/10.1016/0097-3165(75)90008-4">A symmetry relationship for a class of partitions</a>, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
%H A051168 Romeo Meštrović, <a href="https://arxiv.org/abs/1804.00992">Different classes of binary necklaces and a combinatorial method for their enumerations</a>, arXiv:1804.00992 [math.CO], 2018.
%H A051168 Pieter Moree, <a href="http://dx.doi.org/10.1016/j.disc.2005.03.004">The formal series Witt transform</a>, Discr. Math. no. 295 vol. 1-3 (2005) 143-160.
%H A051168 F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A051168 F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A051168 P. Stanica and S. Maitra, <a href="https://doi.org/10.1016/j.dam.2007.04.029">Rotation symmetric boolean functions - count and cryptographic properties</a>, Disc. Appl. Math. 156 (2008) 1567-1580; see h_{n,w} in eq. (3).
%H A051168 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F A051168 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).
%F A051168 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
%F A051168 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
%F A051168 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
%F A051168 From _Petros Hadjicostas_, Jun 16 2019: (Start)
%F A051168 O.g.f. for column k >= 1: (x^k/k) * Sum_{d|k} mu(d)/(1 - x^d)^(k/d).
%F A051168 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)).
%F A051168 (End)
%e A051168 Triangle begins with:
%e A051168 h=0: 1
%e A051168 h=1: 1, 1
%e A051168 h=2: 0, 1, 0
%e A051168 h=3: 0, 1, 1, 0
%e A051168 h=4: 0, 1, 1, 1,  0
%e A051168 h=5: 0, 1, 2, 2,  1,  0
%e A051168 h=6: 0, 1, 2, 3,  2,  1, 0
%e A051168 h=7: 0, 1, 3, 5,  5,  3, 1, 0
%e A051168 h=8: 0, 1, 3, 7,  8,  7, 3, 1, 0
%e A051168 h=9: 0, 1, 4, 9, 14, 14, 9, 4, 1, 0
%e A051168 ...
%e A051168 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.
%p A051168 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:
%p A051168 A051168 := proc(n,k) if n<=1 then 1; elif n=0 or n=k then 0; else A(n-k,k) ; end if;
%p A051168 end proc:
%p A051168 seq(seq(A051168(n,k),k=0..n),n=0..10) ; # _R. J. Mathar_, Mar 29 2011
%t A051168 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 *)
%o A051168 (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 */
%o A051168 (PARI) T(n,k) = if (n==0, 1, (1/n) * sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d,k/d)));
%o A051168 tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ _Michel Marcus_, May 16 2018
%Y A051168 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.
%Y A051168 Cf. A047996, A052307, A052314, A092964, A185158, A123223, A124814.
%K A051168 nonn,tabl
%O A051168 0,18
%A A051168 _Clark Kimberling_