A145597 Generalized Narayana numbers, T(n, k) = 3/(n + 1)*binomial(n + 1, k + 2)*binomial(n + 1, k - 1), triangular array read by rows.

1, 3, 3, 6, 15, 6, 10, 45, 45, 10, 15, 105, 189, 105, 15, 21, 210, 588, 588, 210, 21, 28, 378, 1512, 2352, 1512, 378, 28, 36, 630, 3402, 7560, 7560, 3402, 630, 36, 45, 990, 6930, 20790, 29700, 20790, 6930, 990, 45, 55, 1485, 13068, 50820, 98010, 98010

Offset: 2

Author

Peter Bala, Oct 15 2008

Keywords

• easy
• nonn
• tabl

Comments

T(n,k) is the number of walks of n unit steps, each step in the direction either up (U), down (D), right (R) or left (L), starting from (0,0) and finishing at lattice points on the horizontal line y = 2 and which remain in the upper half-plane y >= 0. An example is given in the Example section below.

The current array is the case r = 2 of the generalized Narayana numbers N_r(n,k) := (r + 1)/(n + 1)*binomial(n + 1,k + r)*binomial(n + 1,k - 1), which count walks of n steps from the origin to points on the horizontal line y = r that remain in the upper half-plane. Case r = 0 gives the table of Narayana numbers A001263 (but with an offset of 0 in the row numbering). For other cases see A145596 (r = 1), A145598 (r = 3) and A145599 (r = 4).

T(n,k) is the number of preimages of the permutation 3214567...(n+3) under West's stack-sorting map that have exactly k+1 descents. - Colin Defant, Sep 15 2018

Examples

			Triangle starts
n\k|..1.....2....3.....4.....5.....6
====================================
.2.|..1
.3.|..3.....3
.4.|..6....15....6
.5.|.10....45...45....10
.6.|.15...105..189...105....15
.7.|.21...210..588...588...210....21
...
Row 4: T(4,1) = 6: the 6 walks of length 4 from (0,0) to (-2,2) are LLUU, LULU, LUUL, ULLU, ULUL and UULL. Changing L to R in these walks gives the 6 walks from (0,0) to (2,2).
T(4,2) = 15: the 15 walks of length 4 from (0,0) to (0,2) are UUUD, UULR, UURL, UUDU,URUL, ULUR, URLU, ULRU, RUUL, LUUR, RLUU, LRUU, RULU, LURU and UDUU.
.
.
*......*......*......y......*......*......*
.
.
*......6......*.....15......*......6......*
.
.
*......*......*......*......*......*......*
.
.
*......*......*......o......*......*......* x axis
.
		

Links

• Harvey P. Dale, Table of n, a(n) for n = 2..1000
• F. Cai, Q.-H. Hou, Y. Sun, and A. L. B. Yang, Combinatorial identities related to 2x2 submatrices of recursive matrices, arXiv:1808.05736 [math.CO], 2018; Table 2.1 for k=2.
• Colin Defant, Preimages under the stack-sorting algorithm, arXiv:1511.05681 [math.CO], 2015-2018; Graphs Combin., 33 (2017), 103-122.
• Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
• Richard K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Crossrefs

Cf. A003517 (row sums), A001263, A145596, A145598, A145599, A145601.

Programs

Maple

with(combinat):
T:= (n,k) -> 3/(n+1)*binomial(n+1,k+2)*binomial(n+1,k-1):
for n from 2 to 11 do
seq(T(n,k),k = 1..n-1);
end do;

Mathematica

Table[3/(n+1) Binomial[n+1,k+2]Binomial[n+1,k-1],{n,2,20},{k,n-1}]//Flatten (* Harvey P. Dale, Aug 12 2023 *)

Formula

T(n,k) = (3/(n+1))*binomial(n+1,k+2)*binomial(n+1,k-1) for n >=2 and 1 <= k <= n-1. In the notation of [Guy], T(n,k) equals w_n(x,y) at (x,y) = (2*k - n,2). Row sums A003517.

O.g.f. for column k+2: 3/(k + 1) * y^(k+3)/(1 - y)^(k+5) * Jacobi_P(k,3,1,(1 + y)/(1 - y)).

Identities for row polynomials R_n(x) := sum {k = 1..n-1} T(n,k)*x^k:

x^2*R_(n-1)(x) = 3*(n-1)*(n-2)/((n+1)*(n+2)*(n+3)) * Sum_{k = 0..n} binomial(n + 3,k) * binomial(2n - k,n) * (x - 1)^k;

Sum_{k = 1..n} (-1)^k*binomial(n,k)*R_k(x^2)*(1 + x)^(2*(n-k)) = R_n(1)*x^n = 6/(n+4)*binomial(2n+1,n-2)*x^n = A003517(n)*x^n.

Row generating polynomial R_(n+2)(x) = 3/(n+3)*x*(1-x)^n * Jacobi_P(n,3,3,(1+x)/(1-x)). [Peter Bala, Oct 31 2008]

G.f.: x*y*A001263(x,y)^3. - Vladimir Kruchinin, Nov 14 2020