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
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Apr 06 2017
STATUS
approved