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,5

Comments

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

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)

Formula

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

Example

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)

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

Prog

(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

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.

Sequence in context: A244124 A183190 A296129 * A214753 A158454 A049243

Adjacent sequences: A276541 A276542 A276543 * A276545 A276546 A276547

Keyword

nonn,tabl

Author

Andrew Howroyd, Apr 09 2017

Status

approved