A276544 Triangle read by rows: T(n,k) = number of primitive (aperiodic) reversible string structures with n beads using exactly k different colors.

1, 0, 1, 0, 2, 1, 0, 4, 4, 1, 0, 9, 15, 6, 1, 0, 16, 49, 37, 9, 1, 0, 35, 160, 183, 76, 12, 1, 0, 66, 498, 876, 542, 142, 16, 1, 0, 133, 1544, 3930, 3523, 1346, 242, 20, 1, 0, 261, 4715, 17179, 21392, 11511, 2980, 390, 25, 1

Offset: 1

Author

Andrew Howroyd, Apr 09 2017

Keywords

• nonn
• tabl

Comments

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure.

Examples

			Triangle starts
1
0   1
0   2    1
0   4    4     1
0   9   15     6     1
0  16   49    37     9     1
0  35  160   183    76    12    1
0  66  498   876   542   142   16   1
0 133 1544  3930  3523  1346  242  20  1
0 261 4715 17179 21392 11511 2980 390 25 1
...
Primitive reversible word structures are:
n=1: a => 1
n=2: ab => 1
n=3: aab, aba; abc => 2 + 1
n=4: aaab, aaba, aabb, abba => 4 (k=2)
     aabc, abac, abbc, abca => 4 (k=3)
		

References

• M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Links

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

Crossrefs

Columns 2-6 are A056336, A056337, A056338, A056339, A056340.

Partial row sums include A056331, A056332, A056333, A056334, A056335.

Row sums are A276549.

Cf. A284871, A284949, A277504, A137651, A107424, A276543.

Programs

Mathematica

Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[n == 0, 1, 0], 1, If[n > 0, 1, 0], _, If[OddQ[n], Sum[Binomial[(n - 1)/2, i] Ach[n - 1 - 2 i, k - 1], {i, 0, (n - 1)/2}], Sum[Binomial[n/2 - 1, i] (Ach[n - 2 - 2 i, k - 1] + 2^i Ach[n - 2 - 2 i, k - 2]), {i, 0, n/2 - 1}]]]
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] (StirlingS2[#, k] + Ach[#, k])/2& ];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 29 2018, after Robert A. Russell and Andrew Howroyd *)

PARI

\\ here Ach is A304972 as matrix.
Ach(n,m=n)={my(M=matrix(n, m, i, k, i>=k)); for(i=3, n, for(k=2, m, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
T(n,m=n)={my(M=matrix(n, m, i, k, stirling(i, k, 2)) + Ach(n,m)); matrix(n, m, i, k, sumdiv(i, d, moebius(i/d)*M[d,k]))/2}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Jan 09 2020

Formula

T(n, k) = Sum_{d|n} mu(n/d) * A284949(d, k).