A320088 -id:A320088 - 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.

A295505 a(n) = Sum_{d|n} mu(n/d)*4^(d-1).

Original entry on oeis.org

1, 3, 15, 60, 255, 1005, 4095, 16320, 65520, 261885, 1048575, 4193220, 16777215, 67104765, 268435185, 1073725440, 4294967295, 17179802640, 68719476735, 274877644740, 1099511623665, 4398045462525, 17592186044415, 70368739967040, 281474976710400

Offset: 1

Seiichi Manyama, Nov 23 2017

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1661

Sum_{d|n} mu(n/d)*k^(d-1): A000740 (k=2), A034741 (k=3), this sequence (k=4), A295506 (k=5).
Column k=4 of A143325.
First differences of A320088.
Cf. A054719.

Table[Sum[MoebiusMu[n/d]4^(d-1),{d,Divisors[n]}],{n,30}] (* Harvey P. Dale, Nov 08 2020 *)
nmax = 20; Rest[CoefficientList[Series[Sum[MoebiusMu[k] * x^k / (1 - 4*x^k), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Dec 11 2020 *)

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

a(n) = A054719(n)/4 for n > 0.

G.f.: Sum_{k>=1} mu(k)*x^k/(1 - 4*x^k). - Ilya Gutkovskiy, Oct 25 2018

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