login
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)}.
3

%I #14 Nov 08 2022 01:47:04

%S 1,0,1,1,1,2,3,3,6,9,10,19,29,34,63,97,118,215,333,416,749,1165,1485,

%T 2650,4135,5355,9490,14845,19473,34318,53791,71313,125104,196417,

%U 262735,459152,721887,973027,1694914,2667941,3619955,6287896,9907851,13521307,23429158

%N 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)}.

%H Alois P. Heinz, <a href="/A357654/b357654.txt">Table of n, a(n) for n = 0..2500</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>

%F a(n) = Sum_{k=0..floor(n/2)} A120730(n-k, k). - _G. C. Greubel_, Nov 07 2022

%p b:= proc(x, y) option remember; `if`(min(x, y)<0 or y>x, 0,

%p `if`(max(x, y)=0, 1, b(x-1, y)+b(x, y-1)))

%p end:

%p a:= n-> add(b(i, n-2*i), i=ceil(n/3)..floor(n/2)):

%p seq(a(n), n=0..44);

%t A120730[n_, k_]:= If[n>2*k, 0, Binomial[n,k]*(2*k-n+1)/(k+1)];

%t A357654[n_]:= Sum[A120730[n-k,k], {k,0,Floor[n/2]}];

%t Table[A357654[n], {n,0,50}] (* _G. C. Greubel_, Nov 07 2022 *)

%o (Magma)

%o A120730:= func< n, k | n gt 2*k select 0 else Binomial(n, k)*(2*k-n+1)/(k+1) >;

%o A357654:= func< n | (&+[A120730(n-k, k): k in [0..Floor(n/2)]]) >;

%o [A357654(n): n in [0..50]]; // _G. C. Greubel_, Nov 07 2022

%o (SageMath)

%o def A120730(n, k): return 0 if (n>2*k) else binomial(n, k)*(2*k-n+1)/(k+1)

%o def A357654(n): return sum(A120730(n-k,k) for k in range((n//2)+1))

%o [A357654(n) for n in range(51)] # _G. C. Greubel_, Nov 07 2022

%Y Cf. A120730, A165407, A357655.

%K nonn,walk

%O 0,6

%A _Alois P. Heinz_, Oct 07 2022