cp's OEIS Frontend

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

%I A349740 #41 Jan 18 2024 19:59:23
%S A349740 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 A349740 132,0,1,22,127,302,407,428,429,0,1,29,225,715,1205,1401,1429,1430,0,
%U A349740 1,37,373,1549,3313,4489,4825,4861,4862,0,1,46,586,3106,8398,13690,16210,16750,16795,16796
%N A349740 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 A349740 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 A349740 Alois P. Heinz, <a href="/A349740/b349740.txt">Rows n = 0..200, flattened</a>
%H A349740 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 A349740 T(n,k) = Sum_{j=0..k} A090181(n,j), the partial sum of the Narayana numbers.
%F A349740 T(n,n) = A000108(n), the n-th Catalan number.
%F A349740 G.f.: (1 + x - x*y - sqrt((1-x*(1+y))^2 - 4*y*x^2))/(2*x*(1-y)).
%F A349740 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 A349740 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 A349740 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 A349740 Triangle begins:
%e A349740   1;
%e A349740   0, 1;
%e A349740   0, 1,  2;
%e A349740   0, 1,  4,   5;
%e A349740   0, 1,  7,  13,   14;
%e A349740   0, 1, 11,  31,   41,   42;
%e A349740   0, 1, 16,  66,  116,  131,  132;
%e A349740   0, 1, 22, 127,  302,  407,  428,  429;
%e A349740   0, 1, 29, 225,  715, 1205, 1401, 1429, 1430;
%e A349740   0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862;
%e A349740   ...
%p A349740 b:= proc(x, y, t) option remember; expand(`if`(y<0
%p A349740       or y>x, 0, `if`(x=0, 1, add(b(x-1, y+j, j)*
%p A349740      `if`(t=1 and j<1, z, 1), j=[-1, 1]))))
%p A349740     end:
%p A349740 T:= proc(n, k) option remember; `if`(k<0, 0,
%p A349740       T(n, k-1)+coeff(b(2*n, 0$2), z, k))
%p A349740     end:
%p A349740 seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Nov 28 2021
%t A349740 T[n_, k_] := If[n == 0, 1, Sum[j Binomial[n, j]^2 / (n - j + 1), {j, 0, k}] / n];
%t A349740 Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* _Peter Luschny_, Nov 29 2021 *)
%Y A349740 Columns k=0-4 give (for n>=k): A000007, A000012, A000124(n-1), A116701, A116844.
%Y A349740 Partial sums of A090181 per row.
%Y A349740 Main diagonal is A000108.
%Y A349740 Row sums give A088218.
%Y A349740 T(2*n,n) gives A065097.
%Y A349740 T(n,n-1) gives A001453 for n >= 2.
%Y A349740 Cf. A106396, A137940.
%K A349740 nonn,tabl
%O A349740 0,6
%A A349740 _Ron L.J. van den Burg_, Nov 28 2021