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

%I #48 Nov 05 2019 05:59:25

%S 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,

%T 71,502,877,542,142,16,1,1,135,1545,3930,3523,1346,242,20,1,1,271,

%U 4730,17185,21393,11511,2980,390,25,1

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

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

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

%C 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

%D 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]

%H Andrew Howroyd, <a href="/A284949/b284949.txt">Table of n, a(n) for n = 1..1275</a>

%H B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, <a href="https://arxiv.org/abs/1910.12102">Number of Distinguishing Colorings and Partitions</a>, arXiv:1910.12102 [math.CO], 2019.

%H Mohammad Hadi Shekarriz, <a href="/A284949/a284949.txt">GAP Program</a>

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 5, 4, 1;

%e 1, 9, 15, 6, 1;

%e 1, 19, 50, 37, 9, 1;

%e 1, 35, 160, 183, 76, 12, 1;

%e 1, 71, 502, 877, 542, 142, 16, 1;

%e 1, 135, 1545, 3930, 3523, 1346, 242, 20, 1;

%e 1, 271, 4730, 17185, 21393, 11511, 2980, 390, 25, 1;

%t (* achiral color patterns for row of n colors containing k different colors *)

%t Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[0==n, 1, 0], 1, If[n>0, 1, 0],

%t (* else *) _, If[OddQ[n],

%t Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1], {i, 0, (n-1)/2}],

%t Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1] + 2^i Ach[n-2-2i, k-2]),

%t {i, 0, n/2-1}]]]

%t Table[(StirlingS2[n, k] + Ach[n, k])/2, {n, 1, 15}, {k, 1, n}] // Flatten

%t (* _Robert A. Russell_, Feb 10 2018 *)

%o (PARI) \\ see A056391 for Polya enumeration functions

%o T(n,k) = NonequivalentStructsExactly(ReversiblePerms(n), k); \\ _Andrew Howroyd_, Oct 14 2017

%o (PARI) \\ Ach is A304972 as square matrix.

%o 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}

%o T(n)={(matrix(n, n, i, k, stirling(i, k, 2)) + Ach(n))/2}

%o { my(A=T(10)); for(n=1, #A, print(A[n,1..n])) } \\ _Andrew Howroyd_, Sep 18 2019

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

%Y Row sums are A103293.

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

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

%K nonn,tabl

%O 1,5

%A _Andrew Howroyd_, Apr 06 2017