%I #35 Feb 25 2024 15:53:46
%S 1,1,1,1,2,1,1,2,3,1,1,2,4,6,1,1,2,4,10,10,1,1,2,4,11,25,20,1,1,2,4,
%T 11,31,70,36,1,1,2,4,11,32,107,196,72,1,1,2,4,11,32,116,379,574,136,1,
%U 1,2,4,11,32,117,455,1451,1681,272,1
%N Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented row of length n using k or fewer colors (subsets).
%C Two color patterns are equivalent if the colors are permuted.
%C In an unoriented row, chiral pairs are counted as one.
%C T(n,k) = Pi_k(P_n) which is the number of non-equivalent partitions of the path on n vertices, with at most 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
%C From _Allan Bickle_, Apr 05 2022: (Start)
%C The columns count unlabeled k-paths with n+k+2 vertices. (A k-path with order n at least k+2 is a k-tree with exactly two k-leaves (vertices of degree k). It can be constructed from a clique with k+1 vertices by iteratively adding a new degree k vertex adjacent to an existing clique containing an existing k-leaf.)
%C Recurrences for the columns appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)
%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 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 Allan Bickle, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Bickle/bickle5.html">How to Count k-Paths</a>, J. Integer Sequences, 25 (2022) Article 22.5.6.
%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H J. Eckhoff, <a href="https://doi.org/10.1002/jgt.3190170112">Extremal interval graphs</a>, J. Graph Theory 17 1 (1993), 117-127.
%H L. Markenzon, O. Vernet, and P. R. da Costa Pereira, <a href="https://www.sciencedirect.com/science/article/pii/S0166218X0800228X">A clique-difference encoding scheme for labelled k-path graphs</a>, Discrete Appl. Math. 156 (2008), 3216-3222.
%F T(n,k) = Sum_{j=1..k} (S2(n,j) + Ach(n,j))/2, where S2 is the Stirling subset number A008277 and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
%F T(n,k) = (A278984(k,n) + A305749(n,k)) / 2 = A278984(k,n) - A320751(n,k) = A320751(n,k) + A305749(n,k).
%F T(n,k) = Sum_{j=1..k} A284949(n,j).
%e Array begins with T(1,1):
%e 1 1 1 1 1 1 1 1 1 1 1 ...
%e 1 2 2 2 2 2 2 2 2 2 2 ...
%e 1 3 4 4 4 4 4 4 4 4 4 ...
%e 1 6 10 11 11 11 11 11 11 11 11 ...
%e 1 10 25 31 32 32 32 32 32 32 32 ...
%e 1 20 70 107 116 117 117 117 117 117 117 ...
%e 1 36 196 379 455 467 468 468 468 468 468 ...
%e 1 72 574 1451 1993 2135 2151 2152 2152 2152 2152 ...
%e 1 136 1681 5611 9134 10480 10722 10742 10743 10743 10743 ...
%e 1 272 5002 22187 43580 55091 58071 58461 58486 58487 58487 ...
%e 1 528 14884 87979 211659 301633 333774 339764 340359 340389 340390 ...
%e For T(4,3)=10, the patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, AAAB, AABA, AABC, ABAC, the last four being chiral with partners ABBB, ABAA, ABCC, and ABCB.
%t Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
%t Table[Sum[StirlingS2[n,j] + Ach[n,j], {j,k-n+1}]/2, {k,15}, {n,k}] // Flatten
%Y Columns 1-7 are A000012, A005418, A001998(n-1), A056323, A056324, A056325, A345207.
%Y As k increases, columns converge to A103293(n+1).
%Y Cf. transpose of A278984 (oriented), A320751 (chiral), A305749 (achiral).
%Y Partial column sums of A284949.
%K nonn,tabl,easy
%O 1,5
%A _Robert A. Russell_, Oct 27 2018