A082951 Number of primitive (aperiodic) word structures of length n using an infinite alphabet.

1, 1, 1, 4, 13, 51, 197, 876, 4125, 21142, 115922, 678569, 4213381, 27644436, 190898444, 1382958489, 10480138007, 82864869803, 682076784814, 5832742205056, 51724158119384, 474869816155870, 4506715737768752, 44152005855084345, 445958869290587567

Offset

0,4

Comments

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

Row sums of triangle A137651. - Gary W. Adamson, Feb 01 2008

Links

Alois P. Heinz, Table of n, a(n) for n = 0..500

Formula

a(n) = sum mu(c)*A000110(d) over all cd=n; equivalently, A000110(n) = sum a(k), where the sum is over all k|n.

1 + Sum_{n>=1} a(n)*x^n/(1 - x^n) is the g.f. of A000110. - Ilya Gutkovskiy, Mar 05 2018

Example

There are A000110(3)=5 word structures of length 3: aaa, aab, aba, abb, abc. The first consists of 3 copies of a word of length 1; the other 4 are primitive. So a(3)=4.

Maple

with(combinat, bell): with(numtheory): newb := proc(n) local s, i; s := 0; for i in divisors(n) do s := s+bell(i)*mobius(n/i): end do: end proc;
# second Maple program:
with(combinat): with(numtheory):
a:= proc(n) option remember;
      bell(n)-add(a(d), d=divisors(n) minus {n})
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 23 2015

Mathematica

a[n_] := DivisorSum[n, BellB[#] MoebiusMu[n/#]&]; a[0]=1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 23 2017 *)

Crossrefs

Cf. A000110, A056277, A056272, A056275, A056274, A056278.

Cf. A137651.

Sequence in context: A056276 A144035 A056277 * A135345 A149462 A151488

Adjacent sequences: A082948 A082949 A082950 * A082952 A082953 A082954

Keyword

easy,nonn

Author

Vadim Ponomarenko (vadim123(AT)gmail.com), May 26 2003

Extensions

More terms from Alois P. Heinz, Jan 23 2015

Status

approved