login
Square array T(n, k) (n>=1, k>=1) read by antidiagonals upwards. T(n, k) is the number of partitions of the set [n] into lists of k noncrossing sets.
0

%I #66 Dec 13 2021 16:31:31

%S 1,1,2,1,4,3,1,8,9,4,1,14,27,16,5,1,22,75,64,25,6,1,32,183,244,125,36,

%T 7,1,44,393,844,605,216,49,8,1,58,759,2584,2725,1266,343,64,9,1,74,

%U 1347,6976,11105,7026,2359,512,81,10,1,92,2235,16804,40325,35976,15547,4040,729,100,11,1,112,3513,36724,129925,166956,95977

%N Square array T(n, k) (n>=1, k>=1) read by antidiagonals upwards. T(n, k) is the number of partitions of the set [n] into lists of k noncrossing sets.

%C The sets may be empty. A list is an ordered set. The lists may even contain multiple empty sets.

%C As a square, the rows are the weighted partial sums of the rows of triangle A089231.

%C Given a partition P of the set {1, 2, ..., n} in a list of sets, a crossing in P are four integers [a, b, c, d] with 1 <= a < b < c < d <= n for which a, c are together in a set, and b, d are together in a different set. A list of noncrossing sets is a partition with no crossings.

%H David Callan, <a href="http://arxiv.org/abs/0711.4841">Sets, Lists and Noncrossing Partitions</a>, arXiv:0711.4841 [math.CO], 2007-2008.

%F T(n, k) = Sum_{j=1..k} binomial(k, j) k! N(n, k), for 1 <= k <= n. Where N(n, k) are the Narayana numbers of A001263.

%F T(n, k) = Sum_{j=1..k} binomial(k, j) A089231, for 1 <= k <= n; the rowwise weighted partial sum of the number of lists of k nonempty noncrossing sets of [n].

%e T(4, 3) = 75.

%e There are 3 lists with set sizes 4, 0 and 0: ({1, 2, 3, 4}, {}, {}), ..., ({}, {}, {1, 2, 3, 4}).

%e There are 4*6 lists with set sizes 3, 1 and 0: ({1, 2, 3}, {4}, {}), ..., ({}, {1}, {2, 3, 4}).

%e There are 6 lists with set sizes 2, 2 and 0 where 1 and 2 are in the same set: ({1, 2}, {3, 4}, {}), ..., ({}, {3, 4}, {1, 2}).

%e There are 6 lists with set sizes 2, 2 and 0 where 1 and 4 are in the same set: ({1, 4}, {2, 3}, {}), ..., ({}, {2, 3}, {1, 4}).

%e There are 6*6 lists with set sizes 2, 1 and 1: ({1, 2}, {3}, {4}), ..., ({2}, {1}, {3, 4}).

%e When adding the 6 list of crossing sets, lists with set sizes 2, 2 and 0 where 1 and 3 are in the same set, ({1, 3}, {2, 4}, {}), ..., ({}, {2, 4}, {1, 3}), then we have 81 partitions of {1, 2, 3, 4} into lists of sets. This is found in A089072(4, 3) = 81.

%Y T(n, k) is a rowwise weighted sum of A089231.

%Y T(n, k) is a rowwise weighted sum of A001263.

%Y Cf. A349740. Sets of <= k noncrossing sets.

%K nonn,tabl

%O 1,3

%A _Ron L.J. van den Burg_, Dec 13 2021