login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A145596 Triangular array of generalized Narayana numbers: T(n, k) = 2*binomial(n + 1, k + 1)*binomial(n + 1, k - 1)/(n + 1). 10
1, 2, 2, 3, 8, 3, 4, 20, 20, 4, 5, 40, 75, 40, 5, 6, 70, 210, 210, 70, 6, 7, 112, 490, 784, 490, 112, 7, 8, 168, 1008, 2352, 2352, 1008, 168, 8, 9, 240, 1890, 6048, 8820, 6048, 1890, 240, 9, 10, 330, 3300, 13860, 27720, 27720, 13860, 3300, 330, 10 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
T(n,k) is the number of walks of n unit steps on the square lattice (i.e., each step in the direction either up (U), down (D), right (R) or left (L)) starting from (0,0) and finishing at points on the horizontal line y = 1, 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 = 1 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 row numbering starting at n = 0). For other cases see A145597 (r = 2), A145598 (r = 3) and A145599 (r = 4).
T(n,k) is the number of preimages of the permutation 21345...(n+2) under West's stack-sorting map that have exactly k descents. - Colin Defant, Sep 15 2018
T(n+k+1,k+1) equals the number of tilings of an octagon with internal angles of 135 degrees and sides of lengths n, k, 1, 1, n, k, 1, 1 using unit rhombi with internal angles 45 degrees and 135 degrees. See Elnitzky, Theorem 5.1. - Peter Bala, Apr 25 2022
LINKS
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=1.
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.
Serge Elnitsky, Rhombic tilings of polygons and classes of reduced words in Coxeter groups, J. Combin. Theory Ser. A, 77(2): 193-221, 1997.
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
Toufik Mansour and Yidong Sun, Identities involving Narayana polynomials and Catalan numbers, arXiv:0805.1274 [math.CO], 2008.
Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 20.
FORMULA
T(n,k) = 2/(n + 1)*binomial(n + 1,k + 1)*binomial(n + 1,k - 1) for 1 <= k <= n. In the notation of [Guy], T(n,k) equals w_n(x,y) at (x,y) = (2*k - n - 1,1).
O.g.f. for column (k + 2): 2/(k + 1) * y^(k+2)/(1 - y)^(k+4) * Jacobi_P(k,2,1,(1 + y)/(1 - y)). The column generating functions begin: column 2: 2*y^2/(1 - y)^4; column 3: y^3*(3 + 2*y)/(1 - y)^6; column 4: y^4*(4 + 8*y + 2*y^2)/(1 - y)^8; the polynomials in the numerators are the row generating polynomials of array A108838.
O.g.f. for array: 1/(2*x*y^3) * (((1 + x)*y - 1)*sqrt(1 - 2*(1 + x)*y + (y - x*y)^2) + x^2*y^2 - 2*x*y + (1 - y)^2) = x*y + (2*x + 2*x^2)*y^2 + (3*x + 8*x^2 + 3*x^3)*y^3 + (4*x + 20*x^2 + 20*x^3 + 4*x^4)*y^4 + ... .
Row sums A002057.
Identities for row polynomials R_n(x) = Sum_{k = 1..n} T(n,k)*x^k (compare with the results in section 1 of [Mansour & Sun]):
x*R_(n-1)(x) = 2*(n - 1)/((n + 1)*(n + 2)) * Sum_{k = 0..n} binomial(n + 2,k) * binomial(2*n - k,n) * (x - 1)^k;
R_n(x) = Sum_{k = 0..floor((n-1)/2)} binomial(n, 2*k + 1) * Catalan(k + 1) * x^(k+1)*(1 + x)^(n-2k-1);
Sum_{k = 1..n} (-1)^(n-k)*binomial(n,k)*R_k(x)*(1 + x)^(n-k) = x^m*Catalan(m) if n = 2*m - 1 is odd, otherwise the sum is zero.
Sum_{k = 1..n} (-1)^(k+1)*binomial(n,k)*R_k(x^2)*(1 + x)^(2*(n-k)) = R_n(1)*x^(n+1) = 4/(n + 3)*binomial(2*n + 1,n - 1)*x^(n+1) = A002057(n-1)*x^(n+1).
Row generating polynomial R_(n+1)(x) = 2/(n + 2)*x*(1 - x)^n * Jacobi_P(n,2,2,(1 + x)/(1 - x)). - Peter Bala, Oct 31 2008
G.f. satisfies x^3*y*A(x,y)^2-A(x,y)*(x^2*y^2+(-2)*x*y+x^2+(-2)*x+1)+x = 0. - Vladimir Kruchinin, Oct 11 2020
The array can be extended to negative values of n: T(-n,k) = 2*binomial(-n + 1, k + 1)*binomial(-n + 1, k - 1)/(-n + 1) = -A108838(n+k-1,k-1) for n >= 2. - Peter Bala, Apr 26 2022
EXAMPLE
n\k|..1.....2....3.....4.....5.....6
====================================
.1.|..1
.2.|..2.....2
.3.|..3.....8....3
.4.|..4....20...20.....4
.5.|..5....40...75....40.....5
.6.|..6....70..210...210....70.....6
...
Row 3 entries:
T(3,1) = 3: the 3 walks from (0,0) to (-2,1) of three steps are LLU, LUL and ULL.
T(3,2) = 8: the 8 walks from (0,0) to (0,1) of three steps are UDU, UUD, ULR, URL, RLU, LRU, RUL and LUR.
T(3,3) = 3: the 3 walks from (0,0) to (2,1) of three steps are RRU, RUR and URR.
.
.
*......*......*......y......*......*......*
.
.
*......3......*......8......*......3......*
.
.
*......*......*......o......*......*......* x-axis
.
.
MAPLE
T:= (n, k) -> 2/(n+1)*binomial(n+1, k+1)*binomial(n+1, k-1):
for n from 1 to 10 do seq(T(n, k), k = 1..n) end do;
MATHEMATICA
t[n_, k_]:=2/(n+1) Binomial[n+1, k+1] Binomial[n+1, k-1]; Table[t[n, k], {n, 3, 10}, {k, n}]//Flatten (* Vincenzo Librandi, Sep 15 2018 *)
PROG
(Magma) /* As triangle */ [[2/(n+1)*Binomial(n+1, k+1)*Binomial(n+1, k-1): k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Sep 15 2018
CROSSREFS
Sequence in context: A296952 A141611 A234357 * A186753 A135835 A177696
KEYWORD
easy,nonn,tabl
AUTHOR
Peter Bala, Oct 14 2008
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)