A137651 Triangle read by rows: T(n,k) is the number of primitive (aperiodic) word structures of length n using exactly k different symbols.

1, 0, 1, 0, 3, 1, 0, 6, 6, 1, 0, 15, 25, 10, 1, 0, 27, 89, 65, 15, 1, 0, 63, 301, 350, 140, 21, 1, 0, 120, 960, 1700, 1050, 266, 28, 1, 0, 252, 3024, 7770, 6951, 2646, 462, 36, 1, 0, 495, 9305, 34095, 42524, 22827, 5880, 750, 45, 1, 0, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55, 1

Offset

1,5

Comments

Row sums = A082951: (1, 1, 4, 13, 51, 197, ...).

Links

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

Formula

A054525 * A008277 as infinite lower triangular matrices. A054525 = Mobius transform, A008277 = Stirling2 triangle.

T(n,k) = Sum{d|n} mu(n/d) * Stirling2(d, k). - Andrew Howroyd, Aug 09 2018

Example

First few rows of the triangle are:
  1;
  0,   1;
  0,   3,   1;
  0,   6,   6,    1;
  0,  15,  25,   10,    1;
  0,  27,  89,   65,   15,   1;
  0,  63, 301,  350,  140,  21,  1;
  0, 120, 960, 1700, 1050, 266, 28, 1;
  ...
From Andrew Howroyd, Apr 03 2017: (Start)
Primitive word structures are:
n=1: a => 1
n=2: ab => 1
n=3: aab, aba, abb; abc => 3 + 1
n=4: aaab, aaba, aabb, abaa, abba, abbb => 6 (k=2)
     aabc, abac, abbc, abca, abcb, abcc => 6 (k=3)
(End)

Mathematica

rows = 10; t[n_, k_] := If[Divisible[n, k], MoebiusMu[n/k], 0]; A054525 = Array[t, {rows, rows}]; A008277 = Array[StirlingS2, {rows, rows}]; T = A054525 . A008277; Table[T[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 07 2017 *)

Prog

(PARI) T(n, k)={sumdiv(n, d, moebius(n/d)*stirling(d, k, 2))} \\ Andrew Howroyd, Aug 09 2018
(Sage) # uses[DivisorTriangle from A327029]
# Computes an additional column (1, 0, 0, ...)
# at the left hand side of the triangle.
DivisorTriangle(moebius, stirling_number2, 10) # Peter Luschny, Aug 24 2019

Crossrefs

Columns 2-6 are A056278 (or A000740), A056279, A056280, A056281, A056282.

Row sums are A082951.

Cf. A054525, A008277, A327029.

Sequence in context: A058150 A058151 A257673 * A248826 A058152 A058140

Adjacent sequences: A137648 A137649 A137650 * A137652 A137653 A137654

Keyword

nonn,tabl

Author

Gary W. Adamson, Feb 01 2008

Extensions

Name changed and a(46)-a(66) from Andrew Howroyd, Aug 09 2018

Status

approved