A071945 Triangle T(n,k) read by rows giving number of underdiagonal lattice paths from (0,0) to (n,k) using steps R=(1,0), V=(0,1) and D=(2,1).

1, 1, 1, 1, 3, 3, 1, 5, 9, 9, 1, 7, 19, 31, 31, 1, 9, 33, 73, 113, 113, 1, 11, 51, 143, 287, 431, 431, 1, 13, 73, 249, 609, 1153, 1697, 1697, 1, 15, 99, 399, 1151, 2591, 4719, 6847, 6847, 1, 17, 129, 601, 2001, 5201, 11073, 19617, 28161, 28161

Offset

0,5

Comments

Also could be titled: "Table read by antidiagonals upward: T(n,k) is the number of ways to move a chess king from (1,1) to (n,k) in the first quadrant using only right, diagonal up-right, and diagonal up-left moves." - Peter Kagey, Apr 20 2020

Links

Peter Kagey, Table of n, a(n) for n = 0..8255 (first 128 rows, flattened)

D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad J. Math., 49 (1997), 301-320.

Formula

G.f.: (1-q)/[z(1+tz)(2t-1+q)], where q=sqrt(1-4tz-4t^2z^2).

T(n,k) = T(n,k-1) + T(n-1,k) + T(n-2,k-1), T(0,0) = 1, T(n,-1) = T(n,n+1) = 0. - Leonidas Liponis, Dec 08 2025

T(n,k) = Sum_{j=0..floor(n/2)} binomial(n-j,j) * (binomial(n+k-2*j,k-j) - binomial(n+k-2*j,k-j-1)). - Seiichi Manyama, Jun 22 2026

Example

a(3,1)=5 because we have RRRV, RRVR, RVRR, RD and DR.
Triangle begins:
  1;
  1,  1;
  1,  3,   3;
  1,  5,   9,   9;
  1,  7,  19,  31,   31;
  1,  9,  33,  73,  113,  113;
  1, 11,  51, 143,  287,  431,   431;
  1, 13,  73, 249,  609, 1153,  1697,  1697;
  1, 15,  99, 399, 1151, 2591,  4719,  6847,  6847;
  1, 17, 129, 601, 2001, 5201, 11073, 19617, 28161, 28161;

Mathematica

T[n_, k_] := T[n, k] = Piecewise[{{1, (n == 0 && k == 0)} , {0, k == -1 || n - k == -1}, {T[n - 1, k] + T[n, k - 1] + T[n - 2, k - 1], n > 0 && k >= 0 && n - k >= 0}}];
TableForm[Table[T[n, k], {n, 0, 10}, {k, 0, n}], TableAlignments -> Center, TableSpacing -> {1, 1}] (* Leonidas Liponis, Dec 08 2025 *)

Crossrefs

Diagonal entries give A052709.

Row sums give A052705(n+2).

Sequence in context: A339904 A208610 A193823 * A209583 A381883 A144944

Adjacent sequences: A071942 A071943 A071944 * A071946 A071947 A071948

Keyword

nonn,easy,tabl,changed

Author

N. J. A. Sloane, Jun 15 2002

Extensions

Edited by Emeric Deutsch, Dec 21 2003

Status

approved