cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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, 7, 1, 44, 393, 844, 605, 216, 49, 8, 1, 58, 759, 2584, 2725, 1266, 343, 64, 9, 1, 74, 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
Offset: 1

Views

Author

Ron L.J. van den Burg, Dec 13 2021

Keywords

Comments

The sets may be empty. A list is an ordered set. The lists may even contain multiple empty sets.
As a square, the rows are the weighted partial sums of the rows of triangle A089231.
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.

Examples

			T(4, 3) = 75.
There are 3 lists with set sizes 4, 0 and 0: ({1, 2, 3, 4}, {}, {}), ..., ({}, {}, {1, 2, 3, 4}).
There are 4*6 lists with set sizes 3, 1 and 0: ({1, 2, 3}, {4}, {}), ..., ({}, {1}, {2, 3, 4}).
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}).
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}).
There are 6*6 lists with set sizes 2, 1 and 1: ({1, 2}, {3}, {4}), ..., ({2}, {1}, {3, 4}).
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.
		

Crossrefs

T(n, k) is a rowwise weighted sum of A089231.
T(n, k) is a rowwise weighted sum of A001263.
Cf. A349740. Sets of <= k noncrossing sets.

Formula

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