A031164 -id:A031164 - 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.

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

Clark Kimberling

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

			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.

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Freddy Cachazo and Nick Early, Planar Kinematics: Cyclic Fixed Points, Mirror Superpotential, k-Dimensional Catalan Numbers, and Root Polytopes, arXiv:2010.09708 [math.CO], 2020.
A. Elashvili and M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238; MR1691428 (2000c:13006).
A. Elashvili, M. Jibladze, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173-188; MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
Romeo Meštrović, Different classes of binary necklaces and a combinatorial method for their enumerations, arXiv:1804.00992 [math.CO], 2018.
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.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
P. Stanica and S. Maitra, Rotation symmetric boolean functions - count and cryptographic properties, Disc. Appl. Math. 156 (2008) 1567-1580; see h_{n,w} in eq. (3).
Index entries for sequences related to Lyndon words

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.

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

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 *)

{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 */

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

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)

A245558 Square array read by antidiagonals: T(n,k) = number of n-tuples of nonnegative integers (u_0,...,u_{n-1}) satisfying Sum_{j=0..n-1} j*u_j == 1 mod n and Sum_{j=0..n-1} u_j = m.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 5, 5, 3, 1, 1, 3, 7, 8, 7, 3, 1, 1, 4, 9, 14, 14, 9, 4, 1, 1, 4, 12, 20, 25, 20, 12, 4, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1

Offset: 1

N. J. A. Sloane, Aug 07 2014

The array is symmetric; for the entries on or below the diagonal see A245559.
If the congruence in the definition is changed from Sum_{j=0..n-1} j*u_j == 1 mod n  to Sum_{j=0..n-1} j*u_j == 0 mod n we get the array shown in A241926, A047996, and A037306.
Differs from A011847 from row n = 9, k = 4 on; if the rows are surrounded by 0's, this yields A051168 without its rows 0 and 1, i.e., a(1) is A051168(2,1). - M. F. Hasler, Sep 29 2018
This array was first studied by Fredman (1975). - Petros Hadjicostas, Jul 10 2019

			Square array begins:
  1, 1,  1,  1,   1,   1,    1,    1,    1,    1, ...
  1, 1,  2,  2,   3,   3,    4,    4,    5,    5, ...
  1, 2,  3,  5,   7,   9,   12,   15,   18,   22, ...
  1, 2,  5,  8,  14,  20,   30,   40,   55,   70, ...
  1, 3,  7, 14,  25,  42,   66,   99,  143,  200, ...
  1, 3,  9, 20,  42,  75,  132,  212,  333,  497, ...
  1, 4, 12, 30,  66, 132,  245,  429,  715, 1144, ...
  1, 4, 15, 40,  99, 212,  429,  800, 1430, 2424, ...
  1, 5, 18, 55, 143, 333,  715, 1430, 2700, 4862, ...
  1, 5, 22, 70, 200, 497, 1144, 2424, 4862, 9225, ...
  ...
Reading by antidiagonals, we get:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,  1;
  1, 2,  3,  2,  1;
  1, 3,  5,  5,  3,   1;
  1, 3,  7,  8,  7,   3,   1;
  1, 4,  9, 14, 14,   9,   4,  1;
  1, 4, 12, 20, 25,  20,  12,  4,  1;
  1, 5, 15, 30, 42,  42,  30, 15,  5,  1;
  1, 5, 18, 40, 66,  75,  66, 40, 18,  5, 1;
  1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1;
  ...

Taylor Brysiewicz, Necklaces count polynomial parametric osculants, arXiv:1807.03408 [math.AG], 2018.
A. Elashvili, M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006).
A. Elashvili, M. Jibladze, D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173-188. MR1719140 (2000j:05009). See p. 174.
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 1993, 189-215, Theorem 9.4.
J. E. Iglesias, Enumeration of closest-packings by the space group: a simple approach, Z. Krist. 221 (2006) 237-245, eq. (5).

This array is very similar to but different from A011847.
Cf. A051168, A092964, A241926, A047996, A037306, A245559.
Rows include A001840, A006918, A051170, A011796, A011797, A031164. Main diagonal is A022553.

# To produce the first 10 rows and columns (as on page 174 of the Elashvili et al. 1999 reference):
with(numtheory):
cnk:=(n,k) -> add(mobius(n/d)*d, d in divisors(gcd(n,k)));
anmk:=(n,m,k)->(1/(n+m))*add( cnk(d,k)*binomial((n+m)/d,n/d), d in divisors(gcd(n,m))); # anmk(n,m,k) is the value of a_k(n,m) as in Theorem 1, Equation (4), of the Elashvili et al. 1999 reference.
r2:=(n,k)->[seq(anmk(n,m,k),m=1..10)];
for n from 1 to 10 do lprint(r2(n,1)); od:

rows = 12;
cnk[n_, k_] := Sum[MoebiusMu[n/d] d, {d , Divisors[GCD[n, k]]}];
anmk[n_, m_, k_] := (1/(n+m)) Sum[cnk[d, k] Binomial[(n+m)/d, n/d], {d, Divisors[GCD[n, m]]}];
r2[n_, k_] := Table[anmk[n, m, k], {m, 1, rows}];
T = Table[r2[n, 1], {n, 1, rows}];
Table[T[[n-k+1, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 05 2018, from Maple *)

A032094 Number of reversible strings with n-1 beads of 2 colors. 7 beads are black. String is not palindromic.

Original entry on oeis.org

4, 16, 60, 160, 396, 848, 1716, 3200, 5720, 9696, 15912, 25152, 38760, 58080, 85272, 122496, 173052, 240240, 328900, 443872, 592020, 780208, 1017900, 1314560, 1682928, 2135744, 2689808, 3361920, 4173840, 5147328, 6310128, 7689984, 9321780, 11240400

Offset: 9

Christian G. Bower

If the offset is changed to 3, this is the 2nd Witt transform of A000292 [Moree]. - R. J. Mathar, Nov 08 2008
Also 7th column of A159916, i.e., number of 7-element subsets of {1,...,n-1} whose elements add up to an odd integer. - M. F. Hasler, May 02 2009
From Petros Hadjicostas, May 19 2018: (Start)
Let k be an integer >= 2. The g.f. of the BHK[k] transform of the sequence (c(n): n >= 1), with g.f. C(x) = Sum_{n>=1} c(n)*x^n, is A_k(x) = (C(x)^k - C(x^2)^(k/2))/2 if k is even, and A_k(x) = (C(x)/2)*(C(x)^{k-1} - C(x^2)^{(k-1)/2}) if k is odd. This follows easily from the formulae in C. G. Bower's web link below about transforms.
When k is even and c(n) = 1 for all n >= 1, we get C(x) = x/(1-x) and A_k(x) = (1/2)*((x/(1-x))^k - (x^2/(1-x^2))^{k/2}). If (a_k(n): n >= 1) is the output sequence (with g.f. A_k(x)), then it can be proved (using Taylor expansions) that a_k(n) = (1/2)*(binomial(n-1, n-k) - binomial((n/2)-1, (n-k)/2)) for even n >= k+1 and a_k(n) = (1/2)*binomial(n-1, n-k) for odd n >= k+1. (Clearly, a_k(1) = ... = a_k(k) = 0.)
In this sequence, k = 8, and (according to C. G. Bower) a(n) = a_{k=8}(n) is the number of reversible non-palindromic compositions of n with 8 positive parts. If n = b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + b_7 + b_8 is such a composition of n (with b_i >= 1), then it is equivalent to the composition n = b_8 + b_7 + b_6 + b_5 + b_4 + b_3 + b_2 + b_1, and each equivalent class has two elements because here linear palindromes are not allowed as compositions of n.
The fact that we are finding the BHK[8] transform of 1, 1, 1, ... means that each part of each composition of n can have exactly one color (see Bower's link below about transforms).
In each such composition replace each b_i with one black (B) ball followed by b_i - 1 white (W) balls. Then drop the first black (B) ball. We then get a reversible non-palindromic string of length n-1 that has k-1 = 7 black balls and n-k = n-8 white balls. This process, applied to the equivalent compositions n = b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + b_7 + b_8 = b_8 + b_7 + b_6 + b_5 + b_4 + b_3 + b_2 + b_1, gives two strings of length n-1 with 7 black balls and n-8 white balls that are mirror images of each other.
Hence, for n >= 2, a(n) = a_{k=8}(n) is also the number of reversible non-palindromic strings of length n-1 that have k-1 = 7 black balls and n-k = n-8 white balls. (Clearly, a(n) = a_{k=8}(n) > 0 only for n >= 9.)
(End)

Colin Barker, Table of n, a(n) for n = 9..1000
C. G. Bower, Transforms (2)
Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160. - _R. J. Mathar_, Nov 08 2008
Index entries for linear recurrences with constant coefficients, signature (4,-2,-12,17,8,-28,8,17,-12,-2,4,-1).

Cf. A005995, A018210, A032091, A032092, A032093, A159916. - M. F. Hasler, May 02 2009 and Petros Hadjicostas, May 19 2018

f[n_] := Binomial[n - 1, n - 8]/2 - If[ OddQ@ n, 0, Binomial[(n/2) - 1, (n - 8)/2]/2]; Array[f, 36, 9] (* or *)
CoefficientList[ Series[ 4x^9 (x^2 + 1)/((x - 1)^8 (x + 1)^4), {x, 0, 40}], x] (* or *)LinearRecurrence[{4, -2, -12, 17, 8, -28, 8, 17, -12, -2, 4, -1}, {4, 16, 60, 160, 396, 848, 1716, 3200, 5720, 9696, 15912, 25152}, 34] (* Robert G. Wilson v, May 20 2018 *)

A032094(n)=(binomial(n--,7)-if(n%2,binomial(n\2,3)))\2 \\ M. F. Hasler, May 02 2009

Vec(4*x^9*(1+x^2)/((1-x)^8*(1+x)^4) + O(x^100)) \\ Colin Barker, Mar 07 2015

"BHK[ 8 ]" (reversible, identity, unlabeled, 8 parts) transform of 1, 1, 1, 1, ...
From  R. J. Mathar, Nov 08 2008: (Start)
G.f.: 4*x^9*(1+x^2)/((1-x)^8*(1+x)^4).
a(n) = 4*A031164(n-9). (End)
From Colin Barker, Mar 07 2015: (Start)
a(n) = (n^7-28*n^6+322*n^5-1960*n^4+6664*n^3-11872*n^2+8448*n)/10080 if n is even.
a(n) = (n^7-28*n^6+322*n^5-1960*n^4+6769*n^3-13132*n^2+13068*n-5040)/10080 if n is odd.
(End)
From Petros Hadjicostas, May 19 2018: (Start)
a(n) = (1/2)*(binomial(n-1, n-8) - binomial((n/2)-1, (n-8)/2)) if n is even.
a(n) = (1/2)*binomial(n-1, n-8) if n is odd.
G.f.: (1/2)*((x/(1-x))^8 - (x^2/(1-x^2))^4).
These formulae agree with the above formulae by R. J. Mathar and Colin Barker. Clearly, the first two formulae (those about a(n)) can be combined into the one given by M. F. Hasler below in the PROG section.
(End)

A381350 Number of subsets of 8 integers between 1 and n such that their sum is 2 modulo n.

Original entry on oeis.org

1, 5, 15, 42, 99, 217, 429, 808, 1430, 2438, 3978, 6308, 9690, 14550, 21318, 30664, 43263, 60115, 82225, 111038, 148005, 195143, 254475, 328752, 420732, 534076, 672452, 840648, 1043460, 1287036, 1577532, 1922736, 2330445, 2810385, 3372291, 4028178, 4790071, 5672645

Offset: 9

Xavier Roulleau, Feb 21 2025

For s an integer such that GCD(s,8)=2, this is also the number of subsets of 8 integers between 1 and n such that their sum is s modulo n.

			For n=10, there are a(10)=5 order 8 subsets of Z/10Z with sum equal to 2 mod 10.

Stefano Spezia, Table of n, a(n) for n = 9..10000
David Broadhurst and Xavier Roulleau, Number of partitions of modular integers, arXiv:2502.19523 [math.NT], 2025.
Index entries for linear recurrences with constant coefficients, signature (4,-4,-4,12,-12,4,12,-22,12,4,-12,12,-4,-4,4,-1).

Cf. A011796, A031164, A056594, A381289, A381290, A381291.

G.f.: x^9*(1 + x - x^2 + 6*x^3 + 2*x^5 + 6*x^7 - x^8 + x^9 + x^10)/((1 - x)^4*(1 - x^2)^2*(1 - x^4)*(1 - x^8)).

a(n) = (n - 4)*(2520 - 24*(281 + 35*(-1)^n)*n + 5*(1039 + 21*(-1)^n)*n^2 - 2112*n^3 + 452*n^4 - 48*n^5 + 2*n^6 - 2520*A056594(n))/80640. - Stefano Spezia, Feb 21 2025

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A245558 Square array read by antidiagonals: T(n,k) = number of n-tuples of nonnegative integers (u_0,...,u_{n-1}) satisfying Sum_{j=0..n-1} j*u_j == 1 mod n and Sum_{j=0..n-1} u_j = m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A032094 Number of reversible strings with n-1 beads of 2 colors. 7 beads are black. String is not palindromic.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A381350 Number of subsets of 8 integers between 1 and n such that their sum is 2 modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A381351 Number of subsets of 9 integers between 1 and n such that their sum is 3 modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula