A143326 -id:A143326 - cp's OEIS frontend

A143327 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words (n,k >= 1) with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

1, 1, 1, 1, 2, 1, 1, 3, 5, 1, 1, 4, 11, 11, 1, 1, 5, 19, 35, 26, 1, 1, 6, 29, 79, 115, 53, 1, 1, 7, 41, 149, 334, 347, 116, 1, 1, 8, 55, 251, 773, 1339, 1075, 236, 1, 1, 9, 71, 391, 1546, 3869, 5434, 3235, 488, 1, 1, 10, 89, 575, 2791, 9281, 19493, 21754, 9787, 983, 1, 1, 11

Offset: 1

Alois P. Heinz, Aug 07 2008

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

			T(3,3) = 11, because 11 words of length <=3 over 3-letter alphabet {a,b,c} are primitive and earlier than others derived by cyclic shifts of the alphabet: a, ab, ac, aab, aac, aba, abb, abc, aca, acb, acc.
Table begins:
  1,   1,    1,     1,     1,      1,      1,       1, ...
  1,   2,    3,     4,     5,      6,      7,       8, ...
  1,   5,   11,    19,    29,     41,     55,      71, ...
  1,  11,   35,    79,   149,    251,    391,     575, ...
  1,  26,  115,   334,   773,   1546,   2791,    4670, ...
  1,  53,  347,  1339,  3869,   9281,  19543,   37367, ...
  1, 116, 1075,  5434, 19493,  55936, 137191,  299510, ...
  1, 236, 3235, 21754, 97493, 335656, 960391, 2396150, ...

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

Columns k=1-10 give: A000012, A085945, A320087, A320088, A320089, A320090, A320091, A320092, A320093, A320094.
Rows n=1-4 give: A000012, A000027, A028387, A003777.
Main diagonal gives A320095.
Cf. A143325, A143326, A134541, A008683.

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

t[n_, k_] := Sum[k^(d-1)*MoebiusMu[j/d], {j, 1, n}, {d, Divisors[j]}]; Table[t[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Dec 13 2013 *)

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

A320087 Number of primitive (=aperiodic) ternary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 3, 11, 35, 115, 347, 1075, 3235, 9787, 29387, 88435, 265315, 796755, 2390347, 7173227, 21519947, 64566667, 193700035, 581120523, 1743362283, 5230145947, 15690440099, 47071499707, 141214499227, 423644035627, 1270932113627, 3812797935395, 11438393826035

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Column k=3 of A143327.
Partial sums of A034741.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 3^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 3*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = sum(j=1, n, sumdiv(j, d, 3^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 3^(d-1) * mu(j/d).
a(n) = A143327(n,3).
a(n) = Sum_{j=1..n} A143325(j,3).
a(n) = A143326(n,3) / 3.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 3*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320088 Number of primitive (=aperiodic) 4-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 4, 19, 79, 334, 1339, 5434, 21754, 87274, 349159, 1397734, 5590954, 22368169, 89472934, 357908119, 1431633559, 5726600854, 22906403494, 91625880229, 366503524969, 1466015148634, 5864060611159, 23456246655574, 93824986622614, 375299963333014, 1501199853398419

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Column k=4 of A143327.
Partial sums of A295505.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 4^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 4*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = sum(j=1, n, sumdiv(j, d, 4^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 4^(d-1) * mu(j/d).
a(n) = A143327(n,4).
a(n) = Sum_{j=1..n} A143325(j,4).
a(n) = A143326(n,4) / 4.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 4*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320089 Number of primitive (=aperiodic) 5-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 5, 29, 149, 773, 3869, 19493, 97493, 488093, 2440589, 12206213, 61031093, 305171717, 1525859213, 7629374189, 38146874189, 190734764813, 953673824213, 4768371089837, 23841855464717, 119209287089693, 596046435527189, 2980232226542813, 14901161132714813

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Column k=5 of A143327.
Partial sums of A295506.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 5^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 5*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = sum(j=1, n, sumdiv(j, d, 5^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 5^(d-1) * mu(j/d).
a(n) = A143327(n,5).
a(n) = Sum_{j=1..n} A143325(j,5).
a(n) = A143326(n,5) / 5.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 5*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320090 Number of primitive (=aperiodic) 6-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 6, 41, 251, 1546, 9281, 55936, 335656, 2015236, 12091631, 72557806, 435346876, 2612129211, 15672776566, 94036939331, 564221643971, 3385331551426, 20311989308806, 121871945977221, 731231675909811, 4387390115926096, 26324340695837771, 157946044538104906

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Column k=6 of A143327.
Partial sums of A320071.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 6^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

nmax = 20; Rest[CoefficientList[Series[1/(1-x) * Sum[MoebiusMu[k] * x^k / (1 - 6*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

a(n) = sum(j=1, n, sumdiv(j, d, 6^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 6^(d-1) * mu(j/d).
a(n) = A143327(n,6).
a(n) = Sum_{j=1..n} A143325(j,6).
a(n) = A143326(n,6) / 6.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 6*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320091 Number of primitive (=aperiodic) 7-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 7, 55, 391, 2791, 19543, 137191, 960391, 6725143, 47076343, 329551591, 2306861191, 16148148391, 113037041143, 791260111543, 5538820797943, 38771751367543, 271402259573191, 1899815857483639, 13298711002502839, 93090977299997143, 651636841100805895

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Column k=7 of A143327.
Partial sums of A320072.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 7^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

a(n) = sum(j=1, n, sumdiv(j, d, 7^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 7^(d-1) * mu(j/d).
a(n) = A143327(n,7).
a(n) = Sum_{j=1..n} A143325(j,7).
a(n) = A143326(n,7) / 7.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 7*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320092 Number of primitive (=aperiodic) 8-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 8, 71, 575, 4670, 37367, 299510, 2396150, 19173302, 153386927, 1227128750, 9817030070, 78536506805, 628292058542, 5026338565487, 40210708557167, 321685685267822, 2573485482143150, 20587883991625133, 164703071933262773, 1317624576539847542

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Column k=8 of A143327.
Partial sums of A320073.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 8^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

a(n) = sum(j=1, n, sumdiv(j, d, 8^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 8^(d-1) * mu(j/d).
a(n) = A143327(n,8).
a(n) = Sum_{j=1..n} A143325(j,8).
a(n) = A143326(n,8) / 8.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 8*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320093 Number of primitive (=aperiodic) 9-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 9, 89, 809, 7369, 66329, 597769, 5380009, 48426649, 435840569, 3922624969, 35303624809, 317733161289, 2859598458169, 25736390906489, 231627518218169, 2084647707070009, 18761829363630889, 168856464660630009, 1519708181946200889, 13677373641002598169

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Column k=9 of A143327.
Partial sums of A320074.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 9^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

a(n) = sum(j=1, n, sumdiv(j, d, 9^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 9^(d-1) * mu(j/d).
a(n) = A143327(n,9).
a(n) = Sum_{j=1..n} A143325(j,9).
a(n) = A143326(n,9) / 9.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 9*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320094 Number of primitive (=aperiodic) 10-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 10, 109, 1099, 11098, 110989, 1110988, 11109988, 111109888, 1111099879, 11111099878, 111110998888, 1111110998887, 11111109998878, 111111109988779, 1111111099988779, 11111111099988778, 111111110999888878, 1111111110999888877, 11111111109999887887

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Column k=10 of A143327.
Partial sums of A320075.
Cf. A008683, A143325, A143326.

b:= n-> add(`if`(d=n, 10^(n-1), -b(d)), d=numtheory[divisors](n)):
a:= proc(n) option remember; b(n)+`if`(n<2, 0, a(n-1)) end:
seq(a(n), n=1..30);

a(n) = sum(j=1, n, sumdiv(j, d, 10^(d-1)*moebius(j/d))); \\ Michel Marcus, Dec 11 2020

a(n) = Sum_{j=1..n} Sum_{d|j} 10^(d-1) * mu(j/d).
a(n) = A143327(n,10).
a(n) = Sum_{j=1..n} A143325(j,10).
a(n) = A143326(n,10) / 10.
G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - 10*x^k). - Ilya Gutkovskiy, Dec 11 2020

A320095 Number of primitive (=aperiodic) n-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Original entry on oeis.org

1, 2, 11, 79, 773, 9281, 137191, 2396150, 48426649, 1111099879, 28531150811, 810554312866, 25239591811405, 854769747700454, 31278135014945519, 1229782937960902111, 51702516367459973873, 2314494592652832016030, 109912203092221714132219, 5518821052631039996623577

Offset: 1

Alois P. Heinz, Oct 05 2018

nonn

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

Main diagonal of A143327.

Cf. A143325, A143326.

b:= (n, k)-> add(`if`(d=n, k^(n-1), -b(d, k)), d=numtheory[divisors](n)):
g:= proc(n, k) option remember; b(n, k)+`if`(n<2, 0, g(n-1, k)) end:
a:= n-> g(n$2):
seq(a(n), n=1..23);

a[n_] := Sum[n^(d-1)*MoebiusMu[j/d], {j, 1, n}, {d, Divisors[j]}];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Oct 25 2022, after A143327 *)

a(n) = sum(j=1, n, sumdiv(j, d, n^(d-1) * moebius(j/d))); \\ Michel Marcus, Feb 16 2020

a(n) = Sum_{j=1..n} Sum_{d|j} n^(d-1) * mu(j/d).
a(n) = A143327(n,n).
a(n) = Sum_{j=1..n} A143325(j,n).
a(n) = A143326(n,n) / n.
a(n) = [x^n] (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - n*x^k). - Ilya Gutkovskiy, Feb 16 2020

cp's OEIS Frontend

A143327 Table T(n,k) by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary words (n,k >= 1) with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320087 Number of primitive (=aperiodic) ternary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A320088 Number of primitive (=aperiodic) 4-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A320089 Number of primitive (=aperiodic) 5-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A320090 Number of primitive (=aperiodic) 6-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A320091 Number of primitive (=aperiodic) 7-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A320092 Number of primitive (=aperiodic) 8-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A320093 Number of primitive (=aperiodic) 9-ary words with length less than or equal to n which are earlier in lexicographic order than any other word derived by cyclic shifts of the alphabet.

Views

Author