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

Author

Gary W. Adamson, Feb 01 2008

Keywords

• nonn
• tabl

Comments

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

Examples

			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)
		

Links

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

Crossrefs

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

Row sums are A082951.

Cf. A054525, A008277, A327029.

Programs

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 *)

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

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

Extensions

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