A137940 -id:A137940 - cp's OEIS frontend

A106396 Triangle read by rows, generated from the Narayana triangle as a matrix.

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

Offset: 1

Gary W. Adamson, May 01 2005

The n-th column starting from the top has the first n terms in the Catalan sequence: (1, 2, 5, 14, ...)

			Col. 2 offset = 1, 2, 4, 7, 11, 16, 22, ... since P * [1, 1, 0, 0, 0, ...] = 1, 2, 4, 7, 11, ...
First few rows of the triangle are:
  1;
  1,  1;
  1,  2,  1;
  1,  4,  2,  1;
  1,  7,  5,  2,  1;
  1, 11, 13,  5,  2,  1;
  1, 16, 31, 14,  5,  2,  1;
  ...
Second column = A000124.

Cf. A000108, A000124, A001263, A137940.

n-th column (offset) is generated by P * V; P = the Narayana triangle as an infinite lower triangular matrix, V = vector for n-th column comprising n leading 1's and the rest zeros (e.g., V for 3rd column = [1, 1, 1, 0, 0, 0, ...]).

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

A106396 Triangle read by rows, generated from the Narayana triangle as a matrix.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula