A110438 Triangular array giving the number of NSEW unit step lattice paths of length n with terminal height k subject to the following restrictions. The paths start at the origin (0,0) and take unit steps (0,1)=N(north), (0,-1)=S(south), (1,0)=E(east) and (-1,0)=W(west) such that no paths pass below the x-axis, no paths begin with W, all W steps remain on the x-axis and there are no NS steps.

1, 1, 1, 2, 2, 1, 5, 4, 3, 1, 12, 10, 7, 4, 1, 29, 25, 18, 11, 5, 1, 71, 62, 47, 30, 16, 6, 1, 175, 155, 121, 82, 47, 22, 7, 1, 434, 389, 311, 220, 135, 70, 29, 8, 1, 1082, 979, 799, 584, 378, 212, 100, 37, 9, 1, 2709, 2471, 2051, 1541, 1039, 620, 320, 138, 46, 10, 1

Offset: 0

Author

Asamoah Nkwanta (Nkwanta(AT)jewel.morgan.edu), Aug 10 2005

Keywords

• easy
• nonn
• tabl

Comments

The row sums are the even-indexed Fibonacci numbers.

Matrix product Q^(-1) * P * Q, where P denotes Pascal's triangle A007318 and Q denotes A061554 (formed from P by sorting the rows into descending order). Cf. A158793. - Peter Bala, Jul 14 2021

Examples

			Triangle starts:
  1;
  1,1;
  2,2,1;
  5,4,3,1;
  12,10,7,4,1;
		

References

• A. Nkwanta, A Riordan matrix approach to unifying a selected class of combinatorial arrays, Congressus Numerantium, 160 (2003), pp. 33-55.
• A. Nkwanta, A note on Riordan matrices, Contemporary Mathematics Series, AMS, 252 (1999), pp. 99-107.
• A. Nkwanta, Lattice paths, generating functions and the Riordan group, Ph.D. Thesis, Howard University, Washington DC, 1997.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
• Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
• Tian-Xiao He, A-sequences, Z-sequence, and B-sequences of Riordan matrices, Discrete Mathematics 343.3 (2020): 111718.

Crossrefs

Row sums are A001519(n+1).

Cf. A097724, A158793.

Programs

Maple

A110438 := proc (n, k)
    add((-1)^binomial(n-i+1, 2)*binomial(floor((1/2)*n+(1/2)*i), i)*add(binomial(i, j)*binomial(j, floor((1/2)*j-(1/2)*k)), j = k..i), i = 0..n);
end proc:
seq(seq(A110438(n, k), k = 0..n), n = 0..10); # Peter Bala, Jul 14 2021

PARI

\\ ColGf gives g.f. of k-th column.
ColGf(k,n)={my(g=(1 - x + x^2 - sqrt(1 - 2*x - x^2 - 2*x^3 + x^4 + O(x^(n-k+3))))/(2*x^2)); (1 - x)*g/(1 - x*g)*(x*g)^k}
T(n,k) = {polcoef(ColGf(k,n), n)} \\ Andrew Howroyd, Mar 02 2023

Formula

Recurrence is d(0, 0) = 1, d(1, 0) = 1, d(n+1, 0) = 2*d(n, 0) + Sum_{j>=1} d(n-j, j), n>=1 for leftmost column and d(n+1, k) = d(n, k-1) + d(n, k) + Sum_{j>=1} d(n-j, k+j), n>=2, k>=1 and n>j; Riordan array d(n, k): (((1-z)/(2*z))*(sqrt(1+z+z^2)/sqrt(1-3*z+z^2) - 1), ((1-z+z^2)-sqrt(1-2*z-z^2-2*z^3+z^4))/(2*z)).

Extensions

Terms a(55) and beyond from Andrew Howroyd, Mar 02 2023