A074650 -id:A074650 - cp's OEIS frontend

A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors.

1, 1, 2, 4, 5, 4, 18, 31, 18, 8, 108, 208, 153, 56, 16, 778, 1700, 1397, 616, 160, 32, 6756, 15980, 14668, 7197, 2196, 432, 64, 68220, 172326, 171976, 93293, 31564, 7208, 1120, 128

Offset: 1

Gus Wiseman, Dec 11 2017

A finite sequence is normal if its union is an initial interval of positive integers.

			The T(3,2) = 5 normal sequences are {2,1,2}, {1,2,1}, {2,1,3}, {2,3,1}, {3,1,2}.
Triangle begins:
     1;
     1,     2;
     4,     5,     4;
    18,    31,    18,     8;
   108,   208,   153,    56,    16;
   778,  1700,  1397,   616,   160,    32;
  6756, 15980, 14668,  7197,  2196,   432,    64;

Andrew Howroyd, Rows n = 1..50 of triangle, flattened
Wikipedia, Lyndon word: Standard factorization

Row sums are A000670.
First column is A060223.
Cf. A000740, A001045, A008965, A019536, A059966, A074650, A185700, A228369, A232472, A277427, A281013, A296373.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
allnorm[n_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Length[Select[Join@@Permutations/@allnorm[n],Length[qit[#]]===k&]],{n,5},{k,n}]

\\ here U(n,k) is A074650(n,k).
EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
U(n,k)={sumdiv(n, d, moebius(n/d) * k^d)/n}
A(n)={[Vecrev(p/y) | p<-sum(k=1, n, EulerMT(vector(n, n, y*U(n,k)))*sum(j=k, n, (-1)^(k-j)*binomial(j,k)))]}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 08 2018

Example and program corrected by Gus Wiseman, Dec 08 2018

A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 9, 6, 0, 0, 6, 30, 48, 24, 0, 0, 9, 89, 260, 300, 120, 0, 0, 18, 258, 1200, 2400, 2160, 720, 0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040, 0, 0, 56, 2016, 20720, 92680, 211680, 258720, 161280, 40320

Offset: 0

Alois P. Heinz, Jan 23 2015

Turning over the necklaces is not allowed.

With other words: T(n,k) is the number of normal Lyndon words of length n and maximum k, where a finite sequence is normal if it spans an initial interval of positive integers. - Gus Wiseman, Dec 22 2017

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 0,  1;
  0, 0,  2,   2;
  0, 0,  3,   9,    6;
  0, 0,  6,  30,   48,    24;
  0, 0,  9,  89,  260,   300,   120;
  0, 0, 18, 258, 1200,  2400,  2160,   720;
  0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040;
  ...
The T(4,3) = 9 normal Lyndon words of length 4 with maximum 3 are: 1233, 1323, 1332, 1223, 1232, 1322, 1123, 1132, 1213. - _Gus Wiseman_, Dec 22 2017

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

Columns k=0-10 give: A000007, A063524, A001037 (for n>1), A056288, A056289, A056290, A056291, A254079, A254080, A254081, A254082.
Row sums give A060223.
Main diagonal and lower diagonal give: A000142, A074143.
T(2n,n) gives A254083.
Cf. A074650, A087854.
Cf. A000670, A000740, A008683, A019536, A059966, A185700, A296372, A296373, A296657.

with(numtheory):
b:= proc(n, k) option remember; `if`(n=0, 1,
      add(mobius(n/d)*k^d, d=divisors(n))/n)
    end:
T:= (n, k)-> add(b(n, k-j)*binomial(k,j)*(-1)^j, j=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[MoebiusMu[n/d]*k^d, {d, Divisors[n]}]/n]; T[n_, k_] := Sum[b[n, k-j]*Binomial[k, j]*(-1)^j, {j, 0, k}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)
LyndonQ[q_]:=q==={}||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
allnorm[n_,k_]:=If[k===0,If[n===0,{{}}, {}],Join@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Select[Subsets[Range[n-1]+1],Length[#]===k-1&]];
Table[Length[Select[allnorm[n,k],LyndonQ]],{n,0,7},{k,0,n}] (* Gus Wiseman, Dec 22 2017 *)

T(n,k) = Sum_{j=0..k} (-1)^j * C(k,j) * A074650(n,k-j).

T(n,k) = Sum_{d|n} mu(d) * A087854(n/d, k) for n >= 1 and 1 <= k <= n. - Petros Hadjicostas, Aug 20 2019

A107424 Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 17, 13, 3, 1, 0, 9, 43, 50, 20, 3, 1, 0, 16, 124, 220, 136, 36, 4, 1, 0, 28, 338, 866, 773, 296, 52, 4, 1, 0, 51, 941, 3435, 4280, 2303, 596, 78, 5, 1, 0, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 0, 170, 7234, 51061

Offset: 1

David Wasserman, May 26 2005

This classification is concerned with which beads are the same color, not with the colors themselves, so bbabcd is the same structure as aabacd. Cyclic permutations are also the same structure, e.g. abacda is also the same structure. However, order matters: the reverse of aabacd is equivalent to aabcad, which is also on the list.

			T(6, 4) = 13: {aaabcd, aabacd, aabcad, abacad, aabbcd, aabcbd, aabcdb, aacbbd, aacbdb, ababcd, abacbd, acabdb, abcabd}.
From _Andrew Howroyd_, Apr 09 2017 (Start)
Triangle starts:
1
0  1
0  1   1
0  2   2    1
0  3   5    2    1
0  5  17   13    3    1
0  9  43   50   20    3   1
0 16 124  220  136   36   4  1
0 28 338  866  773  296  52  4 1
0 51 941 3435 4280 2303 596 78 5 1
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Columns 2-6 are A056303, A056304, A056305, A056306, A056307.
Partial row sums include A000048, A002075, A056300, A056301, A056302.
Row sums are A276547.
Cf. A074650, A152175, A276543, A137651, A276544.

A[d_, n_] := A[d, n] = Which[n == 0, 1, n == 1, DivisorSum[d, x^# &], d == 1, Sum[StirlingS2[n, k] x^k, {k, 0, n}], True, Expand[A[d, 1] A[d, n-1] + D[A[d, n-1], x] x]];
B[n_, k_] := Coefficient[DivisorSum[n, EulerPhi[#] A[#, n/#]&]/n/x, x, k];
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] B[#, k]&];
Table[T[n, k], {n, 1, 12}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jun 06 2018, after Andrew Howroyd and Robert A. Russell *)

\\ here R(n) is A152175 as square matrix.
R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n) = {my(M=R(n)); matrix(n, n, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020

T(n, k) = Sum_{d|n} mu(n/d) * A152175(d, k). - Andrew Howroyd, Apr 09 2017

A208536 Number of 5-bead necklaces of n colors not allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

0, 0, 6, 48, 204, 624, 1554, 3360, 6552, 11808, 19998, 32208, 49764, 74256, 107562, 151872, 209712, 283968, 377910, 495216, 639996, 816816, 1030722, 1287264, 1592520, 1953120, 2376270, 2869776, 3442068, 4102224, 4859994, 5725824, 6710880

Offset: 1

R. H. Hardin, Feb 27 2012

This sequence would be better defined as a(n) = (n^5-n)/5 with offset 0, which is an integer by Fermat's little theorem. - N. J. A. Sloane, Nov 13 2023

			All solutions for n=3:
..1....1....1....1....1....1
..3....3....2....2....2....2
..1....2....1....3....3....1
..3....3....3....2....1....2
..2....2....2....3....3....3

R. H. Hardin, Table of n, a(n) for n = 1..210
Jack Jeffries, Differentiating by prime numbers, Notices Amer. Math. Soc., 70:11 (2023), 1772-1779.
Wikipedia, p-derivation.
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Row 5 of A208535.
Also, row 5 (with different offset) of A074650. - Eric M. Schmidt, Dec 08 2017
Cf. A208537.

A208536[n_]:=((n-1)^5-(n-1))/5;Array[A208536,50] (* Paolo Xausa, Nov 14 2023 *)

Vec(6*x^3*(1 + x)^2 / (1 - x)^6 + O(x^40)) \\ Colin Barker, Nov 11 2017

Empirical: a(n) = (1/5)*n^5 - 1*n^4 + 2*n^3 - 2*n^2 + (4/5)*n.
Equivalently: a(n) = ((n-1)^5 - (n-1))/5. - M. F. Hasler, Mar 05 2016
Empirical formula confirmed by Petros Hadjicostas, Nov 05 2017 (see A208535).
a(n+2) = delta(-n) = -delta(n) for n >= 0, where delta is the p-derivation over the integers with respect to prime p = 5. - Danny Rorabaugh, Nov 10 2017
From Colin Barker, Nov 11 2017: (Start)
G.f.: 6*x^3*(1 + x)^2 / (1 - x)^6.
a(n) = 6*a(n-1) - 15*a(n-2) + 20*a(n-3) - 15*a(n-4) + 6*a(n-5) - a(n-6) for n>6.
(End)

A208537 Number of 7-bead necklaces of n colors not allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

0, 0, 18, 312, 2340, 11160, 39990, 117648, 299592, 683280, 1428570, 2783880, 5118828, 8964072, 15059070, 24408480, 38347920, 58619808, 87460002, 127695960, 182857140, 257298360, 356336838, 486403632, 655210200, 871930800, 1147401450

Offset: 1

R. H. Hardin, Feb 27 2012

This sequence would be better defined as a(n) = (n^7-n)/7 with offset 0, which is an integer by Fermat's little theorem. - N. J. A. Sloane, Nov 13 2023
Row 7 of A208535.
Also, row 7 (with different offset) of A074650. - Eric M. Schmidt, Dec 08 2017

			All solutions for n=3:
..1...1...1...1...1...1...1...1...1...1...1...1...1...1...1...1...1...1
..2...2...2...3...2...2...2...2...2...3...3...3...2...2...2...2...2...2
..1...1...1...1...1...1...3...3...3...2...2...1...3...1...3...1...3...1
..2...3...2...3...3...3...2...1...2...3...1...3...2...2...1...3...1...2
..3...2...1...2...1...2...1...3...3...2...3...1...3...3...3...1...2...1
..1...3...3...3...2...1...3...1...2...3...2...3...1...2...2...3...3...2
..3...2...2...2...3...3...2...3...3...2...3...2...3...3...3...2...2...3

J. Jeffries, Differentiating by prime numbers, Notices Amer. Math. Soc., 70:11 (2023), 1772-1779.

R. H. Hardin, Table of n, a(n) for n = 1..210
Wikipedia, p-derivation.
Index entries for linear recurrences with constant coefficients, signature (8,-28,56,-70,56,-28,8,-1).

Cf. A208535.

A208537[n_]:=((n-1)^7-(n-1))/7;Array[A208537,50] (* Paolo Xausa, Nov 14 2023 *)

Vec(6*x^3*(3 + 28*x + 58*x^2 + 28*x^3 + 3*x^4) / (1 - x)^8 + O(x^40)) \\ Colin Barker, Nov 11 2017

Empirical: a(n) = (1/7)*n^7 - 1*n^6 + 3*n^5 - 5*n^4 + 5*n^3 - 3*n^2 + (6/7)*n.
Empirical formula confirmed by Petros Hadjicostas, Nov 05 2017 (see A208535).
a(n+2) = delta(-n) = -delta(n) for n >= 0, where delta is the p-derivation over the integers with respect to prime p = 7. - Danny Rorabaugh, Nov 10 2017
From Colin Barker, Nov 11 2017: (Start)
G.f.: 6*x^3*(3 + 28*x + 58*x^2 + 28*x^3 + 3*x^4) / (1 - x)^8.
a(n) = 8*a(n-1) - 28*a(n-2) + 56*a(n-3) - 70*a(n-4) + 56*a(n-5) - 28*a(n-6) + 8*a(n-7) - a(n-8) for n>8.
(End)
a(n) = ((n-1)^7 - (n-1))/7. (inspired by Hassler's formula in A208536) - Eric M. Schmidt, Dec 08 2017

A006173 Witt vector *2!.

Original entry on oeis.org

2, 1, 4, 13, 44, 135, 472, 1492, 5324, 17405, 63944, 215096, 799416, 2752909, 10310384, 36443256, 137263244, 489166324, 1860249448, 6739795717, 25596173800, 93596253769, 357974884304, 1319325363658, 5056389932088

Offset: 1

Simon Plouffe

nonn

If c is the Witt transform of b then b(n) = Sum_{d|n} A074650(n/d, c(d)).

The Somos transform sends sequence {a(n)} to sequence with g.f. Product_{i=1..n} 1/(1-a(i)*x^i).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

H. Gaudier, Relèvement des coefficients binomiaux dans les vecteurs de Witt, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 16 (1988), 358/S-18, pp. 93-108.
H. Gaudier, Relèvement des coefficients binomiaux dans les vecteurs de Witt, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 16 (1988), 358/S-18, pp. 93-107. (Annotated scanned copy)

Cf. A006177, A006973.

Inverse Somos transform of A000108 shifted left. - Wouter Meeussen, Aug 20 2002

Witt transform of A060165. - Sean A. Irvine, Jan 15 2017

Edited by Christian G. Bower, Aug 20 2002

A032164 Number of aperiodic necklaces of n beads of 6 colors; dimensions of free Lie algebras.

Original entry on oeis.org

1, 6, 15, 70, 315, 1554, 7735, 39990, 209790, 1119720, 6045837, 32981550, 181394535, 1004668770, 5597420295, 31345665106, 176319264240, 995685849690, 5642219252460, 32071565263710, 182807918979777

Offset: 0

Christian G. Bower

From Petros Hadjicostas, Aug 31 2018: (Start)
For each m >= 1, the CHK[m] transform of sequence (c(n): n>=1) has generating function B_m(x) = (1/m)*Sum_{d|m} mu(d)*C(x^d)^{m/d}, where C(x) = Sum_{n>=1} c(n)*x^n is the g.f. of (c(n): n >= 1). As a result, the CHK transform of sequence (c(n): n >= 1) has generating function B(x) = Sum_{m >= 1} B_m(x) = -Sum_{n >= 1} (mu(n)/n)*log(1 - C(x^n)).
For n, k >= 1, let a_k(n) = number of aperiodic necklaces of n beads of k colors. We then have (a_k(n): n >= 1) = CHK(c_k(n): n >= 1), where c_k(1) = k and c_k(n) = 0 for all n >= 2, with g.f. C_k(x) = Sum_{n >= 1} c_k(n)*x^n = k*x. The g.f. of (a_k(n): n >= 1) is A_k(x) = Sum_{n >= 1} a_k(n)*x^n = -Sum_{n >= 1} (mu(n)/n)*log(1-k*x^n), which is Herbert Kociemba's general formula below (except for the initial term a_k(0) = 1).
For the current sequence, k = 6.
(End)

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

Seiichi Manyama, Table of n, a(n) for n = 0..1289 (terms 0..200 from T. D. Noe)
C. G. Bower, Transforms (2)
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
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]
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
Index entries for sequences related to Lyndon words

Column 6 of A074650.
Cf. A001037, A001692 (5 colors).
Cf. A054721.

f[d_] := MoebiusMu[d]*6^(n/d)/n; a[n_] := Total[f /@ Divisors[n]]; a[0] = 1; Table[a[n], {n, 0, 20}](* Jean-François Alcover, Nov 07 2011 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,6],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

a(n) = if (n==0, 1, sumdiv(n, d, moebius(d)*6^(n/d)/n)); \\ Michel Marcus, Dec 01 2015

"CHK" (necklace, identity, unlabeled) transform of 6, 0, 0, 0...
a(n) = Sum_{d|n} mu(d)*6^(n/d)/n, for n>0.
G.f.: k=6, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016

A102660 List of Lyndon words on {1,2,3} sorted first by length and then lexicographically.

Original entry on oeis.org

1, 2, 3, 12, 13, 23, 112, 113, 122, 123, 132, 133, 223, 233, 1112, 1113, 1122, 1123, 1132, 1133, 1213, 1222, 1223, 1232, 1233, 1322, 1323, 1332, 1333, 2223, 2233, 2333, 11112, 11113, 11122, 11123, 11132, 11133, 11212, 11213, 11222, 11223, 11232

Offset: 1

N. J. A. Sloane, Feb 03 2005

A Lyndon word is primitive (not a power of another word) and is earlier in lexicographic order than any of its cyclic shifts.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
F. Bassino, J. Clement and C. Nicaud, The standard factorization of Lyndon words: an average point of view, Discrete Math. 290 (2005), 1-25.
Reinhard Zumkeller, Haskell programs for some sequences concerning Lyndon words
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words

Cf. A074650, A001037, A102659, A210584, A210585.

Cf. A027376.

Haskell
```
cf. link.
```

is_A102660(n)=is_A239016(n)&&is_A239017(n)
for(n=1, 5, p=vector(n, i, 10^(n-i))~; forvec(d=vector(n, i, [1, 3]), is_A102660(m=d*p)&&print1(m", "))) \\ M. F. Hasler, Mar 09 2014

Equals A239016 intersect A239017. - M. F. Hasler, Mar 09 2014

More terms from John W. Layman, Jan 24 2006

Definition improved by Reinhard Zumkeller, Mar 23 2012

A075147 Number of Lyndon words (aperiodic necklaces) with n beads of n colors.

Original entry on oeis.org

1, 1, 8, 60, 624, 7735, 117648, 2096640, 43046640, 999989991, 25937424600, 743008120140, 23298085122480, 793714765724595, 29192926025339776, 1152921504338411520, 48661191875666868480, 2185911559727674682148, 104127350297911241532840, 5242879999999487999992020

Offset: 1

Christian G. Bower, Sep 04 2002

nonn

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

Main diagonal of A074650 and A143325.

Cf. A000169, A008683, A306173.

with(numtheory):
a:= n-> add(n^d *mobius(n/d), d=divisors(n))/n:
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 21 2014

Table[Total@Map[ MoebiusMu[#1] n^(n/#1 - 1) &, Divisors[n]], {n, 20}] (* Olivier Gérard, Aug 05 2016 *)

a(n) = sumdiv(n, d, moebius(n/d) * n^d) / n; \\ Amiram Eldar, May 29 2025

a(n) = (1/n) * Sum_{d|n} mu(n/d)*n^d.
Asymptotic to n^(n-1) = A000169(n).
a(n) is the n-th term of the inverse Euler transform of j-> n^j. - Alois P. Heinz, Jun 23 2018
a(n) = [x^n] Sum_{k>=1} mu(k)*log(1/(1 - n*x^k))/k. - Ilya Gutkovskiy, May 20 2019

A143328 Table T(n,k) read by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary Lyndon words (n,k >= 1) with length less than or equal to n.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 6, 5, 1, 5, 10, 14, 8, 1, 6, 15, 30, 32, 14, 1, 7, 21, 55, 90, 80, 23, 1, 8, 28, 91, 205, 294, 196, 41, 1, 9, 36, 140, 406, 829, 964, 508, 71, 1, 10, 45, 204, 728, 1960, 3409, 3304, 1318, 127, 1, 11, 55, 285, 1212, 4088, 9695, 14569, 11464, 3502, 226, 1

Offset: 1

Alois P. Heinz, Aug 07 2008

			T(3,2) = 5, because 5 words of length <=3 over 2-letter alphabet {a,b} are primitive Lyndon words: a, b, ab, aab, abb.
Table begins:
  1,  2,  3,   4,   5,  ...
  1,  3,  6,  10,  15,  ...
  1,  5, 14,  30,  55,  ...
  1,  8, 32,  90, 205,  ...
  1, 14, 80, 294, 829,  ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to Lyndon words

Columns k=1-5 give: A000012, A062692, A114945, A114946, A114947.
Rows n=1-4 give: A000027, A000217, A000330, A132117.
Main diagonal gives A215475.
Cf. A143324, A074650, A008683.

with(numtheory):
f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k),
        d=divisors(n)minus{n}), k)
     end:
f2:= proc(n) option remember; unapply(f0(n)(x)/n, x) end:
g2:= proc(n) option remember; unapply(add(f2(j)(x), j=1..n), x) end:
T:= (n,k)-> g2(n)(k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

f0[n_] := f0[n] = Function[k, k^n-Sum[f0[d][k], {d, Divisors[n]//Most}]]; f2[n_] := f2[n] = Function[x, f0[n][x]/n]; g2[n_] := g2[n] = Function[x, Sum[f2[j][x], {j, 1, n}]]; T[n_, k_] := g2[n][k]; Table[T[n, 1+d-n], {d, 1, 12}, {n, 1, d}]//Flatten (* Jean-François Alcover, Feb 12 2014, translated from Maple *)

T(n,k) = Sum_{1<=j<=n} (1/j) * Sum_{d|j} mu(j/d)*k^d.

T(n,k) = Sum_{1<=j<=n} A074650(j,k).

cp's OEIS Frontend

A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A107424 Triangle read by rows: T(n, k) is the number of primitive (period n) n-bead necklace structures with k different colors. Only includes structures that contain all k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A208536 Number of 5-bead necklaces of n colors not allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A208537 Number of 7-bead necklaces of n colors not allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A006173 Witt vector *2!.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A032164 Number of aperiodic necklaces of n beads of 6 colors; dimensions of free Lie algebras.

Views

Author

Keywords

Comments

References

Links

Crossrefs