A027376 -id:A027376 - cp's OEIS frontend

A032322 Number of aperiodic necklaces with n labeled beads of 3 colors.

3, 6, 48, 432, 5760, 83520, 1572480, 32659200, 792529920, 21337344000, 642820147200, 21181450752000, 763681830912000, 29769991592140800, 1250889916243968000, 56282514026618880000, 2701972433782702080000

Offset: 1

Christian G. Bower

nonn

C. G. Bower, Transforms (2)
Index entries for sequences related to Lyndon words

"CHJ" (necklace, identity, labeled) transform of 3, 0, 0, 0...

n! * A027376.

A278663 Number of periodic necklaces with n beads of 3 colors.

Original entry on oeis.org

0, 0, 3, 3, 6, 3, 14, 3, 24, 11, 54, 3, 148, 3, 318, 59, 834, 3, 2314, 3, 5952, 323, 16110, 3, 45178, 51, 122646, 2195, 341820, 3, 962634, 3, 2690844, 16115, 7596486, 363, 21568780, 3, 61171662, 122651, 174343026, 3, 498453878, 3, 1426419876, 958819, 4093181694, 3, 11770610128, 315, 33891550302

Offset: 0

Herbert Kociemba, Nov 25 2016

nonn

			Example: The 6 periodic necklaces with 4 beads and the colors A, B and C are AAAA, BBBB, CCCC, ABAB, ACAC and BCBC.

Cf. A001867, A027376, A066656 (2 colors).

mx=40;f[x_,k_]:=Sum[(MoebiusMu[i]-EulerPhi[i])Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,3],{x,0,mx}],x]

G.f.: k=3, Sum_{i>=1} (mu(i) - phi(i))*log(1 - k*x^i)/i.

a(n) = A001867(n) - A027376(n). - Alois P. Heinz, Nov 25 2016

A303980 a(n) is the number of cyclic permutations that admit a [1,1,-1]-gridding.

Original entry on oeis.org

1, 1, 1, 2, 5, 15, 42, 120, 338, 952, 2671, 7494, 21035, 59115, 166432, 469560, 1327802, 3763545, 10692500, 30447858, 86894361, 248506757, 712109662, 2044402512, 5879579540, 16937048040, 48864612667, 141179970820, 408444645375, 1183143522435, 3431241484224, 9961919944284

Offset: 0

Kassie Archer, May 03 2018

nonn

a(n) is the number of cyclic permutations that, when written in their one-line notation, is composed of an increasing segment, followed by another increasing segment, followed by a decreasing segment.

Cf. A027376, A303979, A006575.

t051168(n, k) = if (n==0, 1, (1/n) * sumdiv(gcd(n, k), d, moebius(d) * binomial(n/d, k/d)));
T303979(n, k) = my(t=sum(j=1, k-1, (-1)^(k+j+1)*t051168(n, j))); if (!(n % 2), t += (-1)^(k+1)*sum(j=1, k-1, if (((n-j) % 4) == 2, t051168(n/2, j/2)))); t;
a027376(n) = if(n<1, n==0, sumdiv(n, d, moebius(n/d)*3^d)/n);
a006575(n) = sumdiv( n, d, if ( bitand(d, 1), moebius(d) * (3^(n/d)-1) , 0 ) ) / (2*n);
a(n) = if (n <= 2, 1, res = a027376(n)/2 - sum(i=2, n-1, i*T303979(n,i)); if (!(n%2), res += a006575(n/2)/2); res); \\ Michel Marcus, May 16 2018

a(n) = A027376(n)/2 - Sum_{i=2..n-1} i*A303979(n,i) when n is odd and n>2.

a(n) = (A027376(n)+A006575(n/2))/2 - Sum_{i=2..n-1} i*A303979(n,i) when n is even and n>2.

More terms from Michel Marcus, May 16 2018

A304200 a(n) is the number of cyclic permutations with at most 2 ascents.

Original entry on oeis.org

1, 1, 1, 2, 6, 18, 58, 186, 570, 1680, 4878, 14058, 40200, 114450, 325290, 923846, 2624730, 7465410, 21261828, 60647370, 173288724, 496014934, 1422223506, 4084793082, 11751102060, 33857989968, 97697014590, 282295318536, 816759712080, 2366027865810, 6861964439314

Offset: 0

Kassie Archer, May 07 2018

nonn

a(n) is the number of cyclic permutations with at most two ascents. These permutations can also be characterized as admitting a [1, 1, 1]-gridding, meaning they are composed of three contiguous increasing segments.

K. Archer and S. Elizalde, Cyclic permutations realized by signed shifts, Journal of Combinatorics, 5 (2014), 1-30.
I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 1993, 189-215.

Equals A303117 when n !== 2 (mod 4).

Cf. A001037, A027376.

L2(n) = if(n>1, sumdiv(n, d, moebius(d)*2^(n/d))/n, n+1); \\ A001037
L3(n) = if(n<1, n==0, sumdiv(n, d, moebius(n/d)*3^d)/n);  \\ A027376
a(n) = if (n <=2, 1, if ((n % 4) != 2, L3(n) - n*L2(n), L3(n) + L3(n/2) - n*(L2(n) + L2(n/2)))); \\ Michel Marcus, May 16 2018

a(n) = L(3,n) - n*L(2,n) when n !== 2 (mod 4) and n>2;
a(n) = L(3,n) + L(3,n/2) - n*(L(2,n) + L(2,n/2)) when n == 2 (mod 4) and n>2;
where L(k,n) is the number of k-ary Lyndon words of length n.

A304201 a(n) is the number of cyclic permutations of length n that admit a [1,-1,-1]-gridding.

Original entry on oeis.org

1, 1, 1, 2, 5, 15, 43, 120, 338, 952, 2672, 7494, 21035, 59115, 166433, 469560, 1327802, 3763545, 10692500, 30447858, 86894361, 248506757, 712109663, 2044402512, 5879579540, 16937048040, 48864612668, 141179970820, 408444645375, 1183143522435, 3431241484223, 9961919944284

Offset: 0

Kassie Archer, May 08 2018

nonn

a(n) is the number of permutations of length n that are composed of an increasing segment, followed by a decreasing segment, followed by another decreasing segment. In other words, these permutation have a descent set of the form {i, i+1, ..., n-1} for some i or {i, i+1, ..., n-1}\{j} for some i and j > i.

Cf. A027376, A303979, A133267.

t051168(n, k) = if (n==0, 1, (1/n) * sumdiv(gcd(n, k), d, moebius(d) * binomial(n/d, k/d)));
T303979(n, k) = my(t=sum(j=1, k-1, (-1)^(k+j+1)*t051168(n, j))); if (!(n % 2), t += (-1)^(k+1)*sum(j=1, k-1, if (((n-j) % 4) == 2, t051168(n/2, j/2)))); t;
a027376(n) = if(n<1, n==0, sumdiv(n, d, moebius(n/d)*3^d)/n);
a133267(n) = sumdiv(n, d, moebius(d)*3^(n/d)/n - if (d%2, moebius(d)*(3^(n/d)-1)/(2*n)));
a006575(n) = sumdiv(n, d, if ( bitand(d, 1), moebius(d) * (3^(n/d)-1) , 0 ) ) / (2*n);
a(n) = if (n <= 2, 1, res = a027376(n)/2 - sum(i=2, n-1, (n+1-i)*T303979(n,i)); if (!(n%2), if ((n%4)==2, res += a133267(n/2)/2, res += a006575(n/2)/2)); res); \\ Michel Marcus, May 18 2018

a(n) = A027376(n)/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n is odd and n > 2;
a(n) = (A027376(n) + A133267(n/2))/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n = 2 (mod 4) and n > 2.
a(n) = (A027376(n) + A006575(n/2))/2 - Sum_{i=2..n-1} (n+1-i)*A303979(n,i), when n = 0 (mod 4) and n > 2.

More terms from Michel Marcus, May 19 2018

A346384 Triangle read by rows. T(n,k) is the number of invertible n X n matrices over GF(3) such that the dimension of the eigenspace corresponding to the eigenvalue 1 is k, 0 <= k <= n, n >= 0.

Original entry on oeis.org

1, 1, 1, 27, 20, 1, 6291, 4719, 221, 1, 13589289, 10191960, 477750, 2120, 1, 266377183929, 199782888129, 9364822830, 41559870, 19481, 1, 47123189360124723, 35342392020078780, 1656674625945339, 7352106327720, 3446299857, 176540, 1

Offset: 0

Geoffrey Critzer, Jul 14 2021

			             1;
             1,            1;
            27,           20,          1;
          6291,         4719,        221,        1;
      13589289,     10191960,     477750,     2120,     1;
  266377183929, 199782888129, 9364822830, 41559870, 19481, 1;

Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A051680 (column k=0), A053290 (row sums).

nn = 6; q = 3; b[p_, i_] := Count[p, i]; d[p_, i_] :=  Sum[j b[p, j], {j, 1, i}] + i Sum[b[p, j], {j, i + 1, Total[p]}]; aut[deg_, p_] :=  Product[Product[
   q^(d[p, i] deg) - q^((d[p, i] - k) deg), {k, 1, b[p, i]}], {i, 1, Total[p]}]; A027376 = Table[1/n Sum[MoebiusMu[n/d] q^d, {d, Divisors[n]}], {n, 1, nn}];
g[u_, v_] := Total[Map[v^Length[#] u^Total[#]/aut[1, #] &, Level[Table[IntegerPartitions[n], {n, 0, nn}], {2}]]]; Map[Select[#, # > 0 &] &, Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0,  nn}] CoefficientList[
    Series[(g[u, v] /. v -> 1)*g[u, v]* Product[Product[1/(1 - (u/q^r)^d), {r, 1, \[Infinity]}]^A027376[[d]], {d, 2, nn}], {u, 0, nn}], {u, v}]] // Grid

cp's OEIS Frontend

A032322 Number of aperiodic necklaces with n labeled beads of 3 colors.

Views

Author

Keywords

Links

Formula

A278663 Number of periodic necklaces with n beads of 3 colors.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A303980 a(n) is the number of cyclic permutations that admit a [1,1,-1]-gridding.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

Extensions

A304200 a(n) is the number of cyclic permutations with at most 2 ascents.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A304201 a(n) is the number of cyclic permutations of length n that admit a [1,-1,-1]-gridding.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

Extensions

A346384 Triangle read by rows. T(n,k) is the number of invertible n X n matrices over GF(3) such that the dimension of the eigenspace corresponding to the eigenvalue 1 is k, 0 <= k <= n, n >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica