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.

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, 0, 1, 46, 586, 3106, 8398, 13690, 16210, 16750, 16795, 16796

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

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

Partial sums of A090181 per row.

Main diagonal is A000108.

Row sums give A088218.

T(2*n,n) gives A065097.

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

Cf. A106396, A137940.

Sequence in context: A077909 A247126 A342134 * A327117 A359107 A229223

Adjacent sequences: A349737 A349738 A349739 * A349741 A349742 A349743

Keyword

nonn,tabl

Author

Ron L.J. van den Burg, Nov 28 2021

Status

approved