A349740 - OEIS

%I #41 Jan 18 2024 19:59:23

%S 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,

%T 132,0,1,22,127,302,407,428,429,0,1,29,225,715,1205,1401,1429,1430,0,

%U 1,37,373,1549,3313,4489,4825,4861,4862,0,1,46,586,3106,8398,13690,16210,16750,16795,16796

%N Number of partitions of set [n] in a set of <= k noncrossing subsets. Number of Dyck n-paths with at most k peaks. Both with 0 <= k <= n, read by rows.

%C 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.

%H Alois P. Heinz, <a href="/A349740/b349740.txt">Rows n = 0..200, flattened</a>

%H David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Callan/callan412.html">Sets, Lists and Noncrossing Partitions</a>, Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3; also on <a href="http://arxiv.org/abs/0711.4841">arXiv</a>, arXiv:0711.4841 [math.CO], 2007-2008.

%F T(n,k) = Sum_{j=0..k} A090181(n,j), the partial sum of the Narayana numbers.

%F T(n,n) = A000108(n), the n-th Catalan number.

%F G.f.: (1 + x - x*y - sqrt((1-x*(1+y))^2 - 4*y*x^2))/(2*x*(1-y)).

%F 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

%e 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}}.

%e 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.

%e Triangle begins:

%e   1;

%e   0, 1;

%e   0, 1,  2;

%e   0, 1,  4,   5;

%e   0, 1,  7,  13,   14;

%e   0, 1, 11,  31,   41,   42;

%e   0, 1, 16,  66,  116,  131,  132;

%e   0, 1, 22, 127,  302,  407,  428,  429;

%e   0, 1, 29, 225,  715, 1205, 1401, 1429, 1430;

%e   0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862;

%e   ...

%p b:= proc(x, y, t) option remember; expand(`if`(y<0

%p       or y>x, 0, `if`(x=0, 1, add(b(x-1, y+j, j)*

%p      `if`(t=1 and j<1, z, 1), j=[-1, 1]))))

%p     end:

%p T:= proc(n, k) option remember; `if`(k<0, 0,

%p       T(n, k-1)+coeff(b(2*n, 0$2), z, k))

%p     end:

%p seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Nov 28 2021

%t T[n_, k_] := If[n == 0, 1, Sum[j Binomial[n, j]^2 / (n - j + 1), {j, 0, k}] / n];

%t Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* _Peter Luschny_, Nov 29 2021 *)

%Y Columns k=0-4 give (for n>=k): A000007, A000012, A000124(n-1), A116701, A116844.

%Y Partial sums of A090181 per row.

%Y Main diagonal is A000108.

%Y Row sums give A088218.

%Y T(2*n,n) gives A065097.

%Y T(n,n-1) gives A001453 for n >= 2.

%Y Cf. A106396, A137940.

%K nonn,tabl

%O 0,6

%A _Ron L.J. van den Burg_, Nov 28 2021