A089072 -id:A089072 - cp's OEIS frontend

A101031 Triangle read by rows: T(n,k) = (1/k) times the number of functions from an n-element set into but not onto a k-element set.

0, 0, 1, 0, 1, 7, 0, 1, 15, 58, 0, 1, 31, 196, 601, 0, 1, 63, 634, 2765, 7656, 0, 1, 127, 1996, 12265, 44136, 116929, 0, 1, 255, 6178, 52925, 248016, 803383, 2092112, 0, 1, 511, 18916, 223801, 1362096, 5432161, 16595776, 43006401, 0, 1, 1023, 57514, 932525

Offset: 0

Clark Kimberling, Nov 26 2004

			T(3,3) = (1/3)*[ #(functions into) - #(functions onto)] = (3^3 - 6)/3 = 7.

T(n, k) = (A089072(n, k)-A019538(n, k))/k (where the two sequences are indexed as triangular arrays).

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

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

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.

			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.

David Callan, Sets, Lists and Noncrossing Partitions, arXiv:0711.4841 [math.CO], 2007-2008.

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.

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

cp's OEIS Frontend

A101031 Triangle read by rows: T(n,k) = (1/k) times the number of functions from an n-element set into but not onto a k-element set.

Views

Author

Keywords

Examples

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula