A320750 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).

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, 11, 31, 70, 36, 1, 1, 2, 4, 11, 32, 107, 196, 72, 1, 1, 2, 4, 11, 32, 116, 379, 574, 136, 1, 1, 2, 4, 11, 32, 117, 455, 1451, 1681, 272, 1

Offset: 1

Author

Robert A. Russell, Oct 27 2018

Keywords

• nonn
• tabl
• easy

Comments

Two color patterns are equivalent if the colors are permuted.

In an unoriented row, chiral pairs are counted as one.

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

From Allan Bickle, Apr 05 2022: (Start)

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.)

Recurrences for the columns appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)

Examples

			Array begins with T(1,1):
  1   1     1     1      1      1      1      1      1      1      1 ...
  1   2     2     2      2      2      2      2      2      2      2 ...
  1   3     4     4      4      4      4      4      4      4      4 ...
  1   6    10    11     11     11     11     11     11     11     11 ...
  1  10    25    31     32     32     32     32     32     32     32 ...
  1  20    70   107    116    117    117    117    117    117    117 ...
  1  36   196   379    455    467    468    468    468    468    468 ...
  1  72   574  1451   1993   2135   2151   2152   2152   2152   2152 ...
  1 136  1681  5611   9134  10480  10722  10742  10743  10743  10743 ...
  1 272  5002 22187  43580  55091  58071  58461  58486  58487  58487 ...
  1 528 14884 87979 211659 301633 333774 339764 340359 340389 340390 ...
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.
		

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

• B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
• Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
• Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
• J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
• L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.

Crossrefs

Columns 1-7 are A000012, A005418, A001998(n-1), A056323, A056324, A056325, A345207.

As k increases, columns converge to A103293(n+1).

Cf. transpose of A278984 (oriented), A320751 (chiral), A305749 (achiral).

Partial column sums of A284949.

Programs

Mathematica

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 *)
Table[Sum[StirlingS2[n,j] + Ach[n,j], {j,k-n+1}]/2, {k,15}, {n,k}] // Flatten

Formula

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)).

T(n,k) = (A278984(k,n) + A305749(n,k)) / 2 = A278984(k,n) - A320751(n,k) = A320751(n,k) + A305749(n,k).

T(n,k) = Sum_{j=1..k} A284949(n,j).