OFFSET
0,6
COMMENTS
Given a partition P of the set {1,2,...,n}, 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 block, and b, d are together in a different block. A noncrossing partition is a partition with no crossings.
LINKS
Alois P. Heinz, Rows n = 0..200, flattened
David Callan, Sets, Lists and Noncrossing Partitions, Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3; also on arXiv, arXiv:0711.4841 [math.CO], 2007-2008.
FORMULA
T(n,k) = Sum_{j=0..k} A090181(n,j), the partial sum of the Narayana numbers.
T(n,n) = A000108(n), the n-th Catalan number.
G.f.: (1 + x - x*y - sqrt((1-x*(1+y))^2 - 4*y*x^2))/(2*x*(1-y)).
T(n,k) = (1/n)*Sum_{j=0..k} j*binomial(n,j)^2 / (n-j+1) for n >= 1. - Peter Luschny, Nov 29 2021
EXAMPLE
For n=4 the T(4,3)=13 partitions are {{1,2,3,4}}, {{1,2,3},{4}}, {{1,2,4},{3}}, {{1,3,4},{2}}, {{2,3,4},{1}}, {{1,2},{3,4}}, {{1,4},{2,3}}, {{1,2},{3},{4}}, {{1,3},{2},{4}}, {{1,4},{2},{3}}, {{1},{2,3},{4}}, {{1},{2,4},{3}}, {{1},{2},{3,4}}.
The set of sets {{1,3},{2,4}} is missing because it is crossing. If you add the set of 4 sets, {{1},{2},{3},{4}}, you get T(4, 4) = 14 = A000108(4), the 4th Catalan number.
Triangle begins:
1;
0, 1;
0, 1, 2;
0, 1, 4, 5;
0, 1, 7, 13, 14;
0, 1, 11, 31, 41, 42;
0, 1, 16, 66, 116, 131, 132;
0, 1, 22, 127, 302, 407, 428, 429;
0, 1, 29, 225, 715, 1205, 1401, 1429, 1430;
0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862;
...
MAPLE
b:= proc(x, y, t) option remember; expand(`if`(y<0
or y>x, 0, `if`(x=0, 1, add(b(x-1, y+j, j)*
`if`(t=1 and j<1, z, 1), j=[-1, 1]))))
end:
T:= proc(n, k) option remember; `if`(k<0, 0,
T(n, k-1)+coeff(b(2*n, 0$2), z, k))
end:
seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Nov 28 2021
MATHEMATICA
T[n_, k_] := If[n == 0, 1, Sum[j Binomial[n, j]^2 / (n - j + 1), {j, 0, k}] / n];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Peter Luschny, Nov 29 2021 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Ron L.J. van den Burg, Nov 28 2021
STATUS
approved