[seqfan] Re: confusion definition of UR paths in A050144

[Neil Sloane]

Richard,  why not consult Clark Kimberling himself?  He is a very active
contributor to the OEIS.
I will copy this to him.

Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com



On Tue, Jul 30, 2024 at 7:18 AM Richard J. Mathar <mathar at mpia-hd.mpg.de>
wrote:

> I don't understand the crossrefs in the lattice paths in A050144.
> The NAME in A050144 defines M(p,q,r) the number of UR paths from
> (0,0) to (p,p-q) that meet the line y=x-r and do not rise above it.
>
> A039599(n,r) are the UR paths from (0,0) to (n,n) that meet the line
> y=x-r but do not *fall* below it.
> i) The use of the sign of r in DEFN of A050144 does not make sense
>    if we start at (0,0) and do not want to rise above y=x-r. For
>    any r>=1, we are already above the line at the start. So apart
>    from some esoteric other parameter combinations, there are no such
> paths.
>
> ii) if we assume that the corrected definition of A050144
>    is "where M(p,q,r) is the number of UR paths from (0,0) to
>    (p,p-q) that meet the line y=x-r and do not fall below it",
>    then the x-refx should say that M(n,0,r) is given by A039599.
>
> I cannot reconcile the M-definition with some brute-force
> enumerations and T(n,k)=M(2n-1,n-1,k-1) at all, even if the
> definition uses the corrected sign of r. Here is my (slow)
> implementation in Maple:
>
> # M= number of UR paths from (0,0) to (p,p-q) that meet
> # the line y=x-r and do not fall below it.
> # Definition in use in A050144
> M := proc(p,q,r)
>     local y,enc,encb,i,a,len,trX,trY ;
>     # no such path initially
>     a :=0 ;
>     # final y-coordinate of the path
>     y := p-q ;
>     # need p steps R and y steps U. Encode path as binary sequence
>     # where U=1, R=0. Path length is p+y. Numbers 0..2^(p+y)-1
>     # Very slow implementation, obviously
>     for enc  from 0 to 2^(p+y)-1 do
>         # encode path in binary
>         encb := convert(enc,base,2) ;
>         # for small numbers pad with trailing zeros
>         # so the path has the full p+y bits.
>         len := nops(encb) ;
>         encb := [op(encb), seq(0,i=1..p+y-len)] ;
>         # Now encb is a binary sequence with p+y bits/steps
>         # Number of 1's = number of U must be y
>         if add(i,i=encb) = y then
>             # start at (0,0) on the trail
>             trX := 0 ;
>             trY := 0 ;
>             # marker of having hit the y=x-r line
>             hits := false ;
>             # marker of staying above or on the y=x-r line
>             above := true ;
>             for i from 1 to nops(encb) do
>                 # 1=U, 0=R steps on the trail
>                 if op(i,encb) = 1 then
>                     trY := trY+1 ;
>                 else
>                     trX := trX+1 ;
>                 end if;
>                 if trY -trX < -r then
>                     # fell below the line
>                     above := false ;
>                 elif trY -trX = -r then
>                     # touched th eline
>                     hits := true ;
>                 end if;
>             end do:
>             # count if touched but not fallen below
>             if hits = true and above = true then
>                 a := a+1 ;
>             end if;
>         end if;
>     end do:
>     a ;
> end proc:
>
> A039599 := proc(n,r)
>     M(n,0,r) ;
> end proc:
> # check correctness of M against table in A039599
> # for n from 0 to 10 do
> #   for k from 0 to 10 do
> #       printf("%d ",A039599(n,k)) ;
> #   end do:
> #   printf("\n") ;
> # end do:
>
> # failing attempts to verify A050144 ??
> A050144 := proc(n,k)
>     # M(2*n-1,n-1,k) ;
>     M(2*n,n-1,k-1) ;
>     # M(n-1,n-1,k-1) ;
> end proc:
>
> for n from 0 to 10 do
>     for k from 0 to 10 do
>         printf("%d ",A050144(n,k)) ;
>     end do:
>     printf("\n") ;
> end do:
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>