A054721 -id:A054721 - cp's OEIS frontend

A143324 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1).

1, 2, 0, 3, 2, 0, 4, 6, 6, 0, 5, 12, 24, 12, 0, 6, 20, 60, 72, 30, 0, 7, 30, 120, 240, 240, 54, 0, 8, 42, 210, 600, 1020, 696, 126, 0, 9, 56, 336, 1260, 3120, 4020, 2184, 240, 0, 10, 72, 504, 2352, 7770, 15480, 16380, 6480, 504, 0, 11, 90, 720, 4032, 16800, 46410, 78120, 65280, 19656, 990, 0

Offset: 1

Alois P. Heinz, Aug 07 2008

Column k is Dirichlet convolution of mu(n) with k^n.

The coefficients of the polynomial of row n are given by the n-th row of triangle A054525; for example row 4 has polynomial -k^2+k^4.

			T(2,3)=6, because there are 6 primitive words of length 2 over 3-letter alphabet {a,b,c}: ab, ac, ba, bc, ca, cb; note that the non-primitive words aa, bb and cc don't belong to the list; secondly note that the words in the list need not be Lyndon words, for example ba can be derived from ab by a cyclic rotation of the positions.
Table begins:
  1,  2,   3,    4,    5, ...
  0,  2,   6,   12,   20, ...
  0,  6,  24,   60,  120, ...
  0, 12,  72,  240,  600, ...
  0, 30, 240, 1020, 3120, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
C. J. Smyth, A coloring proof of a generalisation of Fermat's little theorem, Amer. Math. Monthly 93, No. 6 (1986), pp. 469-471.
Lucas Vieira Barbosa, Nonclassical Temporal Correlations Under Finite-Memory Constraints, Doctoral Thesis, Univ. Wien (Austria 2024). See p. 35.
Index entries for sequences related to Lyndon words

Columns k=1-10 give: A000007(n-1), A027375, A054718, A054719, A054720, A054721, A218124, A218125, A218126, A218127.
Rows n=1-10 give: A000027, A002378(k-1), A007531(k+1), A047928(k+1), A061167, A218130, A133499, A218131, A218132, A218133.
Main diagonal gives A252764.
Cf. A074650, A143325, A008683, A054525.

with(numtheory): f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k), d=divisors(n)minus{n}), k) end; T:= (n,k)-> f0(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, Complement[Divisors[n], {n}]}]]; t[n_, k_] := f0[n][k]; Table[Table[t[n, 1 + d - n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)

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

T(n,k) = k^n - Sum_{d

T(n,k) = A143325(n,k) * k.

T(n,k) = A074650(n,k) * n.

So Sum_{d|n} k^d * mu(n/d) == 0 (mod n), this is a generalization of Fermat's little theorem k^p - k == 0 (mod p) for primes p to an arbitrary modulus n (see the Smyth link). - Franz Vrabec, Feb 09 2021

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

A054718 Number of ternary sequences with primitive period n.

Original entry on oeis.org

1, 3, 6, 24, 72, 240, 696, 2184, 6480, 19656, 58800, 177144, 530640, 1594320, 4780776, 14348640, 43040160, 129140160, 387400104, 1162261464, 3486725280, 10460350992, 31380882456, 94143178824, 282428998560, 847288609200, 2541864234000, 7625597465304

Offset: 0

N. J. A. Sloane, Apr 20 2000

nonn

Equivalently, output sequences with primitive period n from a simple cycling shift register.

Seiichi Manyama, Table of n, a(n) for n = 0..2095 (terms 0..650 from Alois P. Heinz)
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column k=3 of A143324.

Cf. A027375, A054719, A054720, A054721.

with(numtheory):
a:= n-> `if`(n=0, 1, add(mobius(d)*3^(n/d), d=divisors(n))):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 21 2012

a[0] = 1; a[n_] := Sum[MoebiusMu[d]*3^(n/d), {d, Divisors[n]}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)

a(n) = if(n==0,1,sumdiv(n,d, moebius(d) * 3^(n/d) )); \\ Joerg Arndt, Apr 14 2013

a(n) = Sum_{d|n} mu(d)*3^(n/d).
a(0) = 1, a(n) = n * A027376(n).
a(n) = 3 * A034741(n).
G.f.: 1 + 3 * Sum_{k>=1} mu(k) * x^k / (1 - 3*x^k). - Ilya Gutkovskiy, Apr 14 2021

A056271 Number of primitive (aperiodic) words of length n which contain exactly six different symbols.

Original entry on oeis.org

0, 0, 0, 0, 0, 720, 15120, 191520, 1905120, 16435440, 129230640, 953028720, 6711344640, 45674173440, 302899156560, 1969146930240, 12604139926560, 79694818842240, 499018753280880, 3100376788241040

Offset: 1

Marks R. Nester

nonn

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Cf. A000400, A000920, A054721.

Sum mu(d)*A000920(n/d) where d|n.

A056277 Number of primitive (aperiodic) word structures of length n using a 6-ary alphabet.

Original entry on oeis.org

1, 1, 4, 13, 51, 197, 875, 4096, 20643, 109246, 601491, 3402911, 19628063, 114699438, 676207572, 4010086352, 23874362199, 142508702805, 852124263683, 5101098123207, 30560194492576, 183176169456214

Offset: 1

Marks R. Nester

nonn

Permuting the alphabet will not change a word structure. Thus aabc and bbca have the same structure.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Cf. A054721.

sum mu(d)*A056273(n/d) where d|n and n>0.

A363916 Array read by descending antidiagonals. A(n, k) = Sum_{d=0..k} A363914(k, d) * n^d.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 2, 1, 0, 0, 2, 3, 1, 0, 0, 6, 6, 4, 1, 0, 0, 12, 24, 12, 5, 1, 0, 0, 30, 72, 60, 20, 6, 1, 0, 0, 54, 240, 240, 120, 30, 7, 1, 0, 0, 126, 696, 1020, 600, 210, 42, 8, 1, 0, 0, 240, 2184, 4020, 3120, 1260, 336, 56, 9, 1

Offset: 0

Peter Luschny, Jul 04 2023

Row n gives the number of n-ary sequences with primitive period k.

See A074650 and A143324 for combinatorial interpretations.

			Array A(n, k) starts:
[0] 1, 0,  0,   0,    0,     0,      0,       0,        0, ... A000007
[1] 1, 1,  0,   0,    0,     0,      0,       0,        0, ... A019590
[2] 1, 2,  2,   6,   12,    30,     54,     126,      240, ... A027375
[3] 1, 3,  6,  24,   72,   240,    696,    2184,     6480, ... A054718
[4] 1, 4, 12,  60,  240,  1020,   4020,   16380,    65280, ... A054719
[5] 1, 5, 20, 120,  600,  3120,  15480,   78120,   390000, ... A054720
[6] 1, 6, 30, 210, 1260,  7770,  46410,  279930,  1678320, ... A054721
[7] 1, 7, 42, 336, 2352, 16800, 117264,  823536,  5762400, ... A218124
[8] 1, 8, 56, 504, 4032, 32760, 261576, 2097144, 16773120, ... A218125
A000012|A002378| A047928   |   A218130     |      A218131
    A001477,A007531,    A061167,        A133499,   (diagonal A252764)
.
Triangle T(n, k) starts:
[0] 1;
[1] 0, 1;
[2] 0, 1,  1;
[3] 0, 0,  2,   1;
[4] 0, 0,  2,   3,   1;
[5] 0, 0,  6,   6,   4,   1;
[6] 0, 0, 12,  24,  12,   5,  1;
[7] 0, 0, 30,  72,  60,  20,  6, 1;
[8] 0, 0, 54, 240, 240, 120, 30, 7, 1;

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Variant: A143324.
Rows: A000007 (n=0), A019590 (n=1), A027375 (n=2), A054718 (n=3), A054719 (n=4), A054720, A054721, A218124, A218125.
Columns: A000012 (k=0), A001477 (k=1), A002378 (k=2), A007531(k=3), A047928, A061167, A218130, A133499, A218131.
Cf. A252764 (main diagonal), A074650, A363914.

A363916 := (n, k) -> local d; add(A363914(k, d) * n^d, d = 0 ..k):
for n from 0 to 9 do seq(A363916(n, k), k = 0..8) od;

def A363916(n, k): return sum(A363914(k, d) * n^d for d in range(k + 1))
for n in range(9): print([A363916(n, k) for k in srange(9)])
def T(n, k): return A363916(k, n - k)

If k > 0 then k divides A(n, k), see the transposed array of A074650.

If k > 0 then n divides A(n, k), see the transposed array of A143325.

Showing 1-6 of 6 results.

cp's OEIS Frontend

A143324 Table T(n,k) by antidiagonals. T(n,k) is the number of length n primitive (=aperiodic or period n) k-ary words (n,k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A054718 Number of ternary sequences with primitive period n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A056271 Number of primitive (aperiodic) words of length n which contain exactly six different symbols.

Views

Author

Keywords

References

Crossrefs

Formula

A056277 Number of primitive (aperiodic) word structures of length n using a 6-ary alphabet.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

A363916 Array read by descending antidiagonals. A(n, k) = Sum_{d=0..k} A363914(k, d) * n^d.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

SageMath

Formula