A284949 Triangle read by rows: T(n,k) = number of reversible string structures of length n using exactly k different symbols.

1, 1, 1, 1, 2, 1, 1, 5, 4, 1, 1, 9, 15, 6, 1, 1, 19, 50, 37, 9, 1, 1, 35, 160, 183, 76, 12, 1, 1, 71, 502, 877, 542, 142, 16, 1, 1, 135, 1545, 3930, 3523, 1346, 242, 20, 1, 1, 271, 4730, 17185, 21393, 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.

Number of k-block partitions of an n-set up to reflection.

T(n,k) = pi_k(P_n) which is the number of non-equivalent partitions of the path on n vertices, with exactly k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Mohammad Hadi Shekarriz, Aug 21 2019

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

B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

Mohammad Hadi Shekarriz, GAP Program

Example

Triangle begins:
1;
1,   1;
1,   2,    1;
1,   5,    4,     1;
1,   9,   15,     6,     1;
1,  19,   50,    37,     9,     1;
1,  35,  160,   183,    76,    12,    1;
1,  71,  502,   877,   542,   142,   16,   1;
1, 135, 1545,  3930,  3523,  1346,  242,  20,  1;
1, 271, 4730, 17185, 21393, 11511, 2980, 390, 25, 1;

Mathematica

(* achiral color patterns for row of n colors containing k different colors *)
Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[0==n, 1, 0], 1, If[n>0, 1, 0],
   (* else *) _, If[OddQ[n],
   Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1], {i, 0, (n-1)/2}],
   Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1] + 2^i Ach[n-2-2i, k-2]),
   {i, 0, n/2-1}]]]
Table[(StirlingS2[n, k] + Ach[n, k])/2, {n, 1, 15}, {k, 1, n}] // Flatten
(* Robert A. Russell, Feb 10 2018 *)

Prog

(PARI) \\ see A056391 for Polya enumeration functions
T(n, k) = NonequivalentStructsExactly(ReversiblePerms(n), k); \\ Andrew Howroyd, Oct 14 2017
(PARI) \\ Ach is A304972 as square matrix.
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
T(n)={(matrix(n, n, i, k, stirling(i, k, 2)) + Ach(n))/2}
{ my(A=T(10)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 18 2019

Crossrefs

Columns 2..6 are A056326, A056327, A056328, A056329, A056330.

Row sums are A103293.

Partial row sums include A005418, A001998(n-1), A056323, A056324, A056325.

Cf. A277504, A008277 (set partitions), A152175 (up to rotation), A152176 (up to rotation and reflection), A304972 (achiral patterns).

Sequence in context: A139347 A288620 A263324 * A263294 A241500 A152924

Adjacent sequences: A284946 A284947 A284948 * A284950 A284951 A284952

Keyword

nonn,tabl

Author

Andrew Howroyd, Apr 06 2017

Status

approved