1,2

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 generalised 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).

R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6

T. Mansour, Y. Sun, Identities involving Narayana polynomials and Catalan numbers

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 + 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(2n - k,n) * (x - 1)^k;

R_n(x) = sum {k = 0..floor((n-1)/2)} binomial(n,2k+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(2n+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)). [From Peter Bala (pbala(AT)toucansurf.com), Oct 31 2008]

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

.

.

with(combinat):

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;

A002057 (row sums), A001263, A108838, A145597, A145598, A145599, A145600.

Sequence in context: A110985 A153216 A141611 this_sequence A135835 A134574 A141617

Adjacent sequences: A145593 A145594 A145595 this_sequence A145597 A145598 A145599

easy,nonn,tabl

Peter Bala (pbala(AT)toucansurf.com), Oct 14 2008