cp's OEIS Frontend

A145596 Triangular array of generalized Narayana numbers: T(n, k) = 2*binomial(n + 1, k + 1)*binomial(n + 1, k - 1)/(n + 1).

%I A145596 #62 Dec 30 2024 17:16:11
%S A145596 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,
%T A145596 490,112,7,8,168,1008,2352,2352,1008,168,8,9,240,1890,6048,8820,6048,
%U A145596 1890,240,9,10,330,3300,13860,27720,27720,13860,3300,330,10
%N A145596 Triangular array of generalized Narayana numbers: T(n, k) = 2*binomial(n + 1, k + 1)*binomial(n + 1, k - 1)/(n + 1).
%C A145596 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.
%C A145596 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).
%C A145596 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
%C A145596 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
%H A145596 F. Cai, Q.-H. Hou, Y. Sun, and A. L. B. Yang, <a href="http://arxiv.org/abs/1808.05736">Combinatorial identities related to 2x2 submatrices of recursive matrices</a>, arXiv:1808.05736 [math.CO],2018; Table 2.1 for k=1.
%H A145596 Colin Defant, <a href="https://arxiv.org/abs/1511.05681">Preimages under the stack-sorting algorithm</a>, arXiv:1511.05681 [math.CO], 2015-2018; Graphs Combin., 33 (2017), 103-122.
%H A145596 Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%H A145596 Serge Elnitsky, <a href="https://doi.org/10.1006/jcta.1997.2723">Rhombic tilings of polygons and classes of reduced words in Coxeter groups</a>, J. Combin. Theory Ser. A, 77(2): 193-221, 1997.
%H A145596 R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
%H A145596 Toufik Mansour and Yidong Sun, <a href="http://arxiv.org/abs/0805.1274">Identities involving Narayana polynomials and Catalan numbers</a>, arXiv:0805.1274 [math.CO], 2008.
%H A145596 Tad White, <a href="https://arxiv.org/abs/2401.01462">Quota Trees</a>, arXiv:2401.01462 [math.CO], 2024. See p. 20.
%F A145596 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).
%F A145596 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.
%F A145596 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 + ... .
%F A145596 Row sums A002057.
%F A145596 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]):
%F A145596 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;
%F A145596 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);
%F A145596 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.
%F A145596 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).
%F A145596 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
%F A145596 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
%F A145596 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
%F A145596 From _Sergii Voloshyn_, Dec 18 2024: (Start)
%F A145596 Let E be the operator x^2*D*(1/x)*D, where D denotes the derivative operator d/dx. Then 48(1+n)/((n+2)!(n+4)!)* E^n(x^2/(1 - x)^5) = (row n generating polynomial)/(1 - x)^(2*n+5) = 2*binomial(n + 1, k + 1)*binomial(n + 1, k - 1)/(n + 1).
%F A145596 For example, when n = 3 we have 1/3150*E^3(x^2/(1 - x)^5) = x^2 (4 + 20x + 20x^2 + 4x^3)/(1 - x)^11. (End)
%e A145596 n\k|..1.....2....3.....4.....5.....6
%e A145596 ====================================
%e A145596 .1.|..1
%e A145596 .2.|..2.....2
%e A145596 .3.|..3.....8....3
%e A145596 .4.|..4....20...20.....4
%e A145596 .5.|..5....40...75....40.....5
%e A145596 .6.|..6....70..210...210....70.....6
%e A145596 ...
%e A145596 Row 3 entries:
%e A145596 T(3,1) = 3: the 3 walks from (0,0) to (-2,1) of three steps are LLU, LUL and ULL.
%e A145596 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.
%e A145596 T(3,3) = 3: the 3 walks from (0,0) to (2,1) of three steps are RRU, RUR and URR.
%e A145596 .
%e A145596 .
%e A145596 *......*......*......y......*......*......*
%e A145596 .
%e A145596 .
%e A145596 *......3......*......8......*......3......*
%e A145596 .
%e A145596 .
%e A145596 *......*......*......o......*......*......* x-axis
%e A145596 .
%e A145596 .
%p A145596 T:= (n, k) -> 2/(n+1)*binomial(n+1, k+1)*binomial(n+1, k-1):
%p A145596 for n from 1 to 10 do seq(T(n,k), k = 1..n) end do;
%t A145596 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 *)
%o A145596 (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
%Y A145596 Cf. A002057 (row sums), A001263, A108838, A145597, A145598, A145599, A145600.
%K A145596 easy,nonn,tabl
%O A145596 1,2
%A A145596 _Peter Bala_, Oct 14 2008