A106396 -id:A106396 - cp's OEIS frontend

A137940 Triangle read by rows, antidiagonals of an array formed by A000012 * A001263 (transform).

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 5, 7, 1, 1, 2, 5, 13, 11, 1, 1, 2, 5, 14, 31, 16, 1, 1, 2, 5, 14, 41, 66, 22, 1, 1, 2, 5, 14, 42, 116, 127, 29, 1, 1, 2, 5, 14, 42, 131, 302, 225, 37, 1, 1, 2, 5, 14, 42, 132, 407, 715, 373, 46, 1, 1, 2, 5, 14, 42, 132, 428, 1205, 1549, 586, 56, 1

Offset: 1

Gary W. Adamson, Feb 24 2008

Rows of the array tend to the Catalan sequence, A000108 starting (1, 2, 5, 14, 42, ...).

			First few rows of the array:
  1, 1, 1,  1,  1, ...
  1, 2, 4,  7, 11, ...
  1, 2, 5, 13, 31, ...
  1, 2, 5, 14, 41, ...
  1, 2, 5, 14, 42, ...
  ...
First few rows of the triangle:
  1;
  1, 1;
  1, 2, 1;
  1, 2, 4,  1;
  1, 2, 5,  7,  1;
  1, 2, 5, 13, 11,   1;
  1, 2, 5, 14, 31,  16,   1;
  1, 2, 5, 14, 41,  66,  22,   1;
  1, 2, 5, 14, 42, 116, 127,  29,   1;
  1, 2, 5, 14, 42, 131, 302, 225,  37,  1;
  1, 2, 5, 14, 42, 132, 407, 715, 373, 46, 1;
  ...

Antonio Bernini, Matteo Cervetti, Luca Ferrari, Einar Steingrimsson, Enumerative combinatorics of intervals in the Dyck pattern poset, arXiv:1910.00299 [math.CO], 2019. See Table 1 p. 4.

Cf. A001263, A000108, A106396.

Antidiagonals of an array formed by A000012 * A001263(transform), as infinite triangular matrices. A000012 = (1; 1,1; 1,1,1; 1,1,1,1; ...), A001263 = the Narayana triangle.

More terms from Alois P. Heinz, Nov 28 2021

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.

Original entry on oeis.org

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

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

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.

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

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.

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.

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

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 *)

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

cp's OEIS Frontend

A137940 Triangle read by rows, antidiagonals of an array formed by A000012 * A001263 (transform).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions