A357654 Number of lattice paths from (0,0) to (i,n-2*i) that do not go above the diagonal x=y using steps in {(1,0), (0,1)}.

1, 0, 1, 1, 1, 2, 3, 3, 6, 9, 10, 19, 29, 34, 63, 97, 118, 215, 333, 416, 749, 1165, 1485, 2650, 4135, 5355, 9490, 14845, 19473, 34318, 53791, 71313, 125104, 196417, 262735, 459152, 721887, 973027, 1694914, 2667941, 3619955, 6287896, 9907851, 13521307, 23429158

Offset: 0

Author

Alois P. Heinz, Oct 07 2022

Keywords

• nonn
• walk

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2500
• Wikipedia, Counting lattice paths

Crossrefs

Cf. A120730, A165407, A357655.

Programs

Magma

A120730:= func< n, k | n gt 2*k select 0 else Binomial(n, k)*(2*k-n+1)/(k+1) >;
A357654:= func< n | (&+[A120730(n-k, k): k in [0..Floor(n/2)]]) >;
[A357654(n): n in [0..50]]; // G. C. Greubel, Nov 07 2022

Maple

b:= proc(x, y) option remember; `if`(min(x, y)<0 or y>x, 0,
      `if`(max(x, y)=0, 1, b(x-1, y)+b(x, y-1)))
    end:
a:= n-> add(b(i, n-2*i), i=ceil(n/3)..floor(n/2)):
seq(a(n), n=0..44);

Mathematica

A120730[n_, k_]:= If[n>2*k, 0, Binomial[n,k]*(2*k-n+1)/(k+1)];
A357654[n_]:= Sum[A120730[n-k,k], {k,0,Floor[n/2]}];
Table[A357654[n], {n,0,50}] (* G. C. Greubel, Nov 07 2022 *)

SageMath

def A120730(n, k): return 0 if (n>2*k) else binomial(n, k)*(2*k-n+1)/(k+1)
def A357654(n): return sum(A120730(n-k,k) for k in range((n//2)+1))
[A357654(n) for n in range(51)] # G. C. Greubel, Nov 07 2022

Formula

a(n) = Sum_{k=0..floor(n/2)} A120730(n-k, k). - G. C. Greubel, Nov 07 2022