OFFSET
0,13
COMMENTS
T(n,k) is the least integer t such that, for all finite colorings of the k-subsets of w^n, there exists some S, an order-equivalent subset to w^n, where that coloring restricted to the k-subsets of S outputs at most t colors.
By Ramsey's theorem, the first row T(1,k)=1 for all k.
The second row T(2,k) coincides with A000311.
The second column T(n,2) coincides with A079309.
REFERENCES
Dragan Mašulovic and Branislav Šobot, Countable ordinals and big Ramsey degrees, Combinatorica, 41 (2021), 425-446.
Alexander S. Kechris, Vladimir G. Pestov, and Stevo Todorčević, Fraïssé Limits, Ramsey Theory, and topological dynamics of automorphism groups, Geometric & Functional Analysis, 15 (2005), 106-189.
LINKS
Joanna Boyland, William Gasarch, Nathan Hurtig, and Robert Rust, Big Ramsey Degrees of Countable Ordinals, arXiv:2305.07192 [math.CO], 2023.
Eric Weisstein's World of Mathematics, Ordinal Number.
FORMULA
T(n,k) = Sum_{p=0..n*k} P(p,n,k), where for n >= 2 and k >= 1,
P(0,n,k) = 0, and for p >= 1,
P(p,n,k) = Sum_{j=1..k} Sum_{0..p-1} binomial(p-1,i)*P(i,n-1,j)*P(p-1-i,n,k-j).
EXAMPLE
The data is organized in a table beginning with row n = 0 and column k = 0. The data is read by descending antidiagonals. T(2,3)=26.
The table T(n,k) begins:
[n/k] 0 1 2 3 4 5 ...
--------------------------------------------------------------------
[0] 1, 1, 0, 0, 0, 0, ...
[1] 1, 1, 1, 1, 1, 1, ...
[2] 1, 1, 4, 26, 236, 2572, ...
[3] 1, 1, 14, 509, 35839, 4154652, ...
[4] 1, 1, 49, 10340, ...
[5] 1, 1, 175, 222244, ...
[6] 1, 1, 637, ...
PROG
(Haskell)
pp p n k
| n == 0 && k >= 2 = 0
| k == 0 && p == 0 = 1
| k == 0 && p >= 1 = 0
| n == 0 && k == 1 && p == 0 = 1
| n == 0 && k == 1 && p >= 1 = 0
| n == 1 && k >= 1 && k == p = 1
| n == 1 && k >= 1 && k /= p = 0
| n >= 2 && k >= 1 = sum [binom (p-1) i * pp i (n-1) j * pp (p-1-i) n (k-j) | i <- [0..p-1], j <- [1..k]]
binom n 0 = 1
binom 0 k = 0
binom n k = binom (n-1) (k-1) * n `div` k
a364026 n k =
sum [pp p n k | p <- [0..n*k]]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Nathan Hurtig, Jul 01 2023
STATUS
approved