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,4

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

References

He, Tian-Xiao. "A-sequences, Z-sequence, and B-sequences of Riordan matrices." Discrete Mathematics 343.3 (2020): 111718.

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.

Formula

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

Example

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

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

Prog

(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

Crossrefs

Row sums are A001519(n+1).

Cf. A097724, A158793.

Sequence in context: A226059 A353738 A127742 * A184051 A121460 A105292

Adjacent sequences: A110435 A110436 A110437 * A110439 A110440 A110441

Keyword

easy,nonn,tabl

Author

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

Extensions

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

Status

approved