|
| |
|
|
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).
|
|
9
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
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
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)
|
|
|
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
|
|
|
|
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) = Sum_{j=1..k} A284949(n,j).
|
|
|
EXAMPLE
|
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.
|
|
|
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
|
|
|
CROSSREFS
|
As k increases, columns converge to A103293(n+1).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
