A027376 -id:A027376 - cp's OEIS frontend

A290277 Inverse Euler Transform of the Motzkin Numbers.

1, 1, 2, 4, 10, 22, 56, 136, 348, 890, 2332, 6136, 16380, 43988, 119170, 324720, 890290, 2452752, 6789308, 18868520, 52635730, 147323176, 413618614, 1164510896, 3287073450, 9300500508, 26372968632, 74937133488, 213333642442, 608400799010, 1737954608280

Offset: 1

R. J. Mathar, Jul 25 2017

nonn

The Multiset Transform of this sequence generates a triangle with rows n >= 0, columns k >= 0:
  1;
  0,     1;
  0,     1,     1;
  0,     2,     1,     1;
  0,     4,     3,     1,    1;
  0,    10,     6,     3,    1,    1;
  0,    22,    17,     7,    3,    1,    1;
  0,    56,    40,    19,    7,    3,    1,   1;
  0,   136,   108,    47,   20,    7,    3,   1,   1;
  0,   348,   276,   130,   49,   20,    7,   3,   1,  1;
  0,   890,   739,   340,  137,   50,   20,   7,   3,  1,  1;
  0,  2332,  1954,   929,  362,  139,   50,  20,   7,  3,  1, 1;
  0,  6136,  5275,  2511,  998,  369,  140,  50,  20,  7,  3, 1, 1;
  0, 16380, 14232,  6893, 2717, 1020,  371, 140,  50, 20,  7, 3, 1, 1;
  0, 43988, 38808, 18911, 7520, 2786, 1027, 372, 140, 50, 20, 7, 3, 1, 1;
where a(n) defines the column k=1, and where the row sums are the Motzkin numbers, A001006. The question is: what set of or statistics on Motzkin paths of length n do the entries in row n of the triangle describe/refine?
a(n) is the number of Lyndon words of length n of a 3-letter alphabet {0,1,2} where the frequency of the first letter of the alphabet equals the frequency of the second letter of the alphabet (subset of the words in A027376). For n=1 this is (2), for n=2 this is (01), for n=3 these are (012), (021), for n=4 these are  (0011) (0122) (0212) (0221), for n=5 these are (00112) (00121) (00211) (01012) (01021) (01102) (01222) (02122) (02212) (02221). - R. J. Mathar, Oct 26 2021

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for sequences related to Lyndon words

Cf. A001006.

read(transforms); # https://oeis.org/transforms.txt
[seq(A001006(n),n=1..20)] ;
EULERi(%) ;

a(n) ~ 3^(n + 1/2) / (2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 09 2019

Conjecture: n*a(n) = Sum_{d|n} mobius(d)*A002426(n/d) where mobius=A008683. - R. J. Mathar, Nov 05 2021

A006168 Number of factorization patterns of polynomials of degree n over F_3.

Original entry on oeis.org

1, 3, 5, 10, 15, 29, 42, 72, 107, 170, 246, 383, 542, 810, 1145, 1662, 2311, 3305, 4537, 6363, 8677, 11974, 16159, 22068, 29504, 39811, 52887, 70632, 93102, 123362, 161473, 212198, 276185, 360270, 466090, 604267, 777399, 1001656, 1282456

Offset: 1

N. J. A. Sloane

nonn

R. A. Hultquist, G. L. Mullen and H. Niederreiter, Association schemes and derived PBIB designs of prime power order, Ars. Combin., 25 (1988), 65-82.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..1000
R. A. Hultquist, G. L. Mullen and H. Niederreiter, Association schemes and derived PBIB designs of prime power order, Ars. Combin., 25 (1988), 65-82. (Annotated scanned copy)

Cf. A006167-A006171.

Cf. A027376.

Euler transform of sequence b(n) = sum_{d|n, A027376(d)>=n/d} 1. - Franklin T. Adams-Watters, Jun 19 2006

More terms from Franklin T. Adams-Watters, Jun 19 2006

A114945 Number of monic irreducible polynomials over GF(3) of degree <= n.

Original entry on oeis.org

3, 6, 14, 32, 80, 196, 508, 1318, 3502, 9382, 25486, 69706, 192346, 533830, 1490406, 4180416, 11776896, 33299124, 94470780, 268807044, 766918996, 2193322744, 6286504432, 18054379372, 51945923740, 149709932740, 432139468492, 1249167599632, 3615732336352

Offset: 1

Gary L Mullen (mullen(AT)math.psu.edu) and Ken Hicks, Jan 06 2006

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..650

Partial sums of A027376. 3rd column of A143328. - Alois P. Heinz, Sep 23 2008

with(numtheory):
b:= n-> add(mobius(d) *3^(n/d)/n, d=divisors(n)):
a:= n-> add(b(k), k=1..n):
seq(a(n), n=1..30);  # Alois P. Heinz, Sep 23 2008

f[n_] := DivisorSum[n, MoebiusMu[#] * 3^(n/#) &] / n; Accumulate[Array[f, 30]] (* Amiram Eldar, Aug 24 2023 *)

a(n)=sum(m=1,n, 1/m* sumdiv(m, d, moebius(d)*3^(m/d) ) );/* Joerg Arndt, Jul 04 2011 */

a(n) ~ 3^(n+1) / (2*n). - Vaclav Kotesovec, Sep 05 2014

More terms from Alois P. Heinz, Sep 23 2008

A123223 Triangle read by rows: T(n,k) = number of ternary Lyndon words of length n with exactly k 1's.

Original entry on oeis.org

1, 2, 1, 1, 2, 0, 2, 4, 2, 0, 3, 8, 5, 2, 0, 6, 16, 16, 8, 2, 0, 9, 32, 38, 26, 9, 2, 0, 18, 64, 96, 80, 40, 12, 2, 0, 30, 128, 220, 224, 137, 56, 13, 2, 0, 56, 256, 512, 596, 448, 224, 74, 16, 2, 0, 99, 512, 1144, 1536, 1336, 806, 332, 96, 17, 2, 0, 186, 1024, 2560, 3840, 3840

Offset: 0

Mike Zabrocki, Nov 05 2006

Sum of rows equal to number of ternary Lyndon words A027376 first column (k=0) is equal to the number of binary Lyndon words A001037 third through sixth column (k=2,3,4,5) equal to A124720, A124721, A124722, A124723 T(n+1,n-1) entry equal to A042948.

			Triangle begins:
   1;
   2,  1;
   1,  2,  0;
   2,  4,  2,  0;
   3,  8,  5,  2,  0;
   6, 16, 16,  8,  2,  0;
   9, 32, 38, 26,  9,  2, 0;
  18, 64, 96, 80, 40, 12, 2, 0;
T(n,1) = 2^(n-1) because all words beginning with a 1 and consisting of the rest 2's or 3's are ternary Lyndon words with exactly one 1.

Alois P. Heinz, Rows n = 0..140, flattened.

Cf. A027376, A001037, A124720, A124721, A124722, A124723, A051168, A042948.

G.f. for columns (except for k=0) given by 1/k*Sum_{d|k} mu(d) x^k/(1-2*x^d)^(k/d) T(0,0) = 1 and T(n,0) = 1/n*Sum_{d|n} mu(d)*2^(n/d) T(n,n) = 0 if n>1, T(n,n-1) = 2.

A185171 Dimensions of primitive Lie algebras connected with the Mantaci-Reutenauer algebra MR^(2).

Original entry on oeis.org

2, 3, 8, 18, 48, 116, 312, 810, 2184, 5880, 16104, 44220, 122640, 341484, 956576, 2690010, 7596480, 21522228, 61171656, 174336264, 498111952, 1426403748, 4093181688, 11767874940, 33891544368, 97764009000, 282429535752, 817028131140, 2366564736720

Offset: 1

N. J. A. Sloane, Jan 23 2012

Maybe the definition should say: "Number of generators of degree n ...". The paper is a little unclear.
From Petros Hadjicostas, Jun 18 2019: (Start)
An unmarked cyclic composition of n >= 1 is an equivalence class of ordered partitions of n such that two such ordered partitions are equivalent iff one can be obtained from the other by rotation.
Here, a(n) is the number of aperiodic unmarked cyclic compositions of n where up to two colors can be used.
It is also the CHK (circular, identity, unlabeled) transform of the sequence 2, 2, 2, ... See the link by Bowers about such transforms.
If c = (c(n): n >= 1) is the input sequence with g.f. C(x) = Sum_{n >= 1} c(n)*x^n, then the g.f. of the output sequence ((CHK c)d: d >= 1) is -Sum{d >= 1} (mu(d)/d) * log(1 - C(x^d)). Here, c(n) = 2 for all n >= 1, and thus, C(x) = 2*x/(1 - x). It follows that the g.f. of the output sequence is -Sum_{d >= 1} (mu(d)/d) * log(1 - 2*x^d/(1 - x^d)).
(End)

			From _Petros Hadjicostas_, Jun 18 2019: (Start)
Suppose we have two colors, say, A and B. Here, a(1) = 2 because we have the following aperiodic unmarked cyclic compositions of n = 1: 1_A and 1_B.
We have a(2) = 3 because we have the following aperiodic unmarked cyclic compositions of n = 2: 2_A, 2_B, and 1_A + 1_B.
We have a(3) = 8 because we have the following aperiodic unmarked cyclic compositions of n = 3: 3_A and 3_B; 1_X + 2_Y, where (X, Y) \in {(A, A), (A, B), (B, A), (B, B)}; 1_A + 1_B + 1_B and 1_B + 1_A + 1_A.
(End)

G. C. Greubel, Table of n, a(n) for n = 1..2000
J. Blumlein, Structural relations of harmonic sums and Mellin transforms up to weight 5, Comp. Phys. Com. 180 (2009) 2218-2249 eq. 4.2
C. G. Bower, Transforms (2).
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, arXiv:0806.3682 [math.CO], 2008. See Eqs. (93) and (95).
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, Discrete Math. 310 (2010), no. 24, 3584-3606. See Eqs. (98) and (100).

Cf. A024023, A032251, A185172.

Essentially the same as A027376.

a[1] = 2; a[n_] := DivisorSum[n, MoebiusMu[#]*3^(n/#)&]/n; Array[a, 29] (* Jean-François Alcover, Dec 07 2015, adapted from PARI *)

a(l=2,n) = if (n==1, l, sumdiv(n, d, moebius(d)*(1+l)^(n/d))/n); \\ Michel Marcus, Feb 09 2013

From Petros Hadjicostas, Jun 18 2019: (Start)
a(1) = 2 and a(n) = (1/n) * Sum_{d|n} mu(d) * 3^(n/d) for n > 1 (from Eq. (95) in Novelli and Thibon (2008) or Eq. (100) in Novelli and Thibon (2010)).
a(n) = (1/n) * Sum_{d|n} mu(d) * (3^(n/d) - 1) = (1/n) * Sum_{d|n} mu(d) * A024023(n/d) for n >= 1.
G.f.: -Sum_{d >= 1} (mu(d)/d) * log(1 - 2*x^d/(1 - x^d)) = -x - Sum_{d >= 1} (mu(d)/d) * log(1 - 3*x^d).
(End)

More terms from Michel Marcus, Feb 09 2013

Name edited by Petros Hadjicostas, Jun 18 2019

A210323 Number of 2-divided words of length n over a 3-letter alphabet.

Original entry on oeis.org

0, 3, 16, 57, 192, 599, 1872, 5727, 17488, 53115, 161040, 487073, 1471680, 4441167, 13392272, 40355877, 121543680, 365895947, 1101089808, 3312442185, 9962240928, 29954639751, 90049997136, 270661616363, 813397065024, 2444101696683, 7343167947040, 22059763982001, 66263812628160

Offset: 1

N. J. A. Sloane, Mar 20 2012

nonn

See A210109 for further information.
It appears that A027376 gives the number of 2-divided words that have a unique division into two parts. - David Scambler, Mar 21 2012
Row sums of the following irregular triangle W(n,k) which shows how many words of length n over a 3-letter alphabet are 2-divided in k>=1 different ways (3-letter analog of A209919):
3;
8, 8;
18, 21, 18;
48, 48, 48, 48;
116, 124, 119, 124, 116;
312, 312, 312, 312, 312, 312;
810, 828, 810, 831, 810, 828, 810;
2184, 2184, 2192, 2184, 2184, 2192, 2184, 2184;
5880, 5928, 5880, 5928, 5883, 5928, 5880, 5928, 5880;
First column of the following triangle D(n,k) which shows how many words of length n over a 3-letter alphabet are k-divided:
3;
16, 1;
57, 16, 0;
192, 78, 6, 0;
599, 324, 56, 0, 0;
1872, 1141, 343, 15, 0, 0;
5727, 3885, 1534, 166, 0, 0, 0;
17488, 12630, 6067, 1135, 20, 0, 0, 0;
53115, 40315, 22162, 5865, 351, 0, 0, 0, 0;
161040, 126604, ...
- R. J. Mathar, Mar 25 2012
Speculation: W(2n+1,2)=W(2n+1,1) and W(2n,2) = W(2n,1)+W(n,1). W(3n+1,3)=W(3n+1,1); W(3n+2,3)=W(3n+1,1); W(3n,3) = W(3n,1)+W(n,1). - R. J. Mathar, Mar 27 2012

Cf. A210109, A209970, A001867.

a(n) = 3^n - A001867(n) (see A209970 for proof).

a(1)-a(12) computed by David Scambler, Mar 19 2012; a(13) onwards from N. J. A. Sloane, Mar 20 2012

A295521 a(n) = (1/n) * Sum_{d|n} mu(n/d)*(4^d - 3^d - 2^d + 1).

Original entry on oeis.org

0, 2, 10, 39, 150, 545, 2010, 7320, 26880, 98775, 365010, 1353185, 5038950, 18830145, 70623958, 265737270, 1002976350, 3796197160, 14406059010, 54801140307, 208932573650, 798218035245, 3055417070010, 11716354754030, 45002103387120, 173117601112575

Offset: 1

Seiichi Manyama, Nov 23 2017

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1666
Wikipedia, Möbius function

Cf. A001037, A008683, A020988, A027376, A027377.

a[n_] := DivisorSum[n, MoebiusMu[n/#] * (4^# - 3^# - 2^# + 1) &] / n; Array[a, 26] (* Amiram Eldar, Oct 04 2023 *)

{a(n) = sumdiv(n, d, moebius(n/d)*(4^d-3^d-2^d+1))/n}

a(n) = A027377(n) - A027376(n) - A001037(n) for n > 1.

A346209 Number of n X n matrices over GF(3) with no eigenvalues in GF(3), i.e., neither 0 nor 1 nor 2 is an eigenvalue.

Original entry on oeis.org

1, 0, 18, 3456, 7619508, 149200289280, 26394940582090344, 42062797470468915399168, 603463180651533072058654437264, 77927374189849689541269666899007713280, 90570450400853976077932766909301405665963077152

Offset: 0

Geoffrey Critzer, Jul 10 2021

nonn

Equivalently, a(n) is the number of n X n matrices over GF(3) whose characteristic polynomial has no linear factors.

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

Cf. A002820, A051680, A027376, A053290.

nn = 10; q = 3; \[Nu] = Table[1/n Sum[MoebiusMu[n/d] q^d, {d, Divisors[n]}], {n, 1, nn}];Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0, nn}] CoefficientList[Series[Product[Product[1/(1 - u^d/q^(r d)), {r, 1, \[Infinity]}]^\[Nu][[d]], {d, 2, nn}], {u, 0, nn}], u]

Sum_{n>=0} a(n)*x^n/A053290(n) = Product_{d>=2} (Product_{r>=1} 1/(1-x^d/3^(r*d)))^A027376(d).

A136703 Number of Lyndon words on {1,2,3} with an even number of 1's and an even number of 2's.

Original entry on oeis.org

1, 0, 2, 3, 12, 26, 78, 195, 546, 1452, 4026, 11010, 30660, 85254, 239144, 672195, 1899120, 5379738, 15292914, 43581852, 124527988, 356594898, 1023295422, 2941952130, 8472886092, 24440956260, 70607383938

Offset: 1

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Jan 16 2008

nonn

A Lyndon word is the aperiodic necklace representative which is lexicographically earliest among its cyclic shifts. Thus we can apply the fixed density formulas: L_k(n,d)=sum L(n-d, n_1,..., n_(k-1)); n_1+...+n_(k-1)=d where L(n_0, n_1,...,n_(k-1))=(1/n)sum mu(j)*[(n/j)!/((n_0/j)!(n_1/j)!...(n_(k-1)/j)!)]; j|gcd(n_0, n_1,...,n_(k-1)). For this sequence, sum over n_0,n_1=even.

			For n=3, out of 8 possible Lyndon words: 112, 113, 122, 123, 132, 133, 223, 233, only 113 and 223 have an even number of both 1's and 2's. Thus a(3)=2.

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
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]
F. Ruskey and J. Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.
M. Zabrocki, MATH5020 York University Course Website

Cf. A006575; A027376; A133267; A136704.

a(1)=1; for n>1, if n=odd then a(n)= sum(mu(d)*3^(n/d))/(4n); d|n. If n=even, then a(n)= sum(mu(d)*3^(n/d))/n; d|n -(3/4)*sum(mu(d)*(3^(n/d)-1))/n; d|n, d odd.

A303117 a(n) is the number of cyclic permutations with at most two descents.

Original entry on oeis.org

1, 1, 1, 2, 6, 18, 62, 186, 570, 1680, 4890, 14058, 40200, 114450, 325230, 923846, 2624730, 7465410, 21260652, 60647370, 173288724, 496014934, 1422211494, 4084793082, 11751102060, 33857989968, 97696908330, 282295318536, 816759712080, 2366027865810, 6861963548198, 19922800783578, 57902584654650

Offset: 0

Kassie Archer, Apr 18 2018

nonn

The number of cyclic permutations with at most 2 descents is equal to L(3,n)-n*L(2,n) where L(k,n) is the number of primitive necklaces (equivalently, the number of Lyndon words) of length n on k letters.

I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 189-215, (1993).

Cf. A027376, A001037.

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) = L3(n)-n*L2(n); \\ Michel Marcus, May 17 2018

a(n) = A027376(n) - n*A001037(n).

a(n) = L(3,n)-n*L(2,n) where L(k,n) is the number of primitive k-ary necklaces (or equivalently, Lyndon words) of length n.

cp's OEIS Frontend

A290277 Inverse Euler Transform of the Motzkin Numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A006168 Number of factorization patterns of polynomials of degree n over F_3.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A114945 Number of monic irreducible polynomials over GF(3) of degree <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A123223 Triangle read by rows: T(n,k) = number of ternary Lyndon words of length n with exactly k 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A185171 Dimensions of primitive Lie algebras connected with the Mantaci-Reutenauer algebra MR^(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A210323 Number of 2-divided words of length n over a 3-letter alphabet.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A295521 a(n) = (1/n) * Sum_{d|n} mu(n/d)*(4^d - 3^d - 2^d + 1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A346209 Number of n X n matrices over GF(3) with no eigenvalues in GF(3), i.e., neither 0 nor 1 nor 2 is an eigenvalue.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs