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