Help14:=proc(): print(` LC(p) , LDie(A), Paths(m,n), GPaths(m,n), NuPaths(m,n), NuGPaths(m,n) , RPath(m,n)  , CycShi(L) , DvoMot(n), DrawP(P) `): end:

#LC(p): inputs a rational number p outputs 1 with probability p (and 0 otherwise)
#LC is short for "Loaded Coin"
LC:=proc(p) local a,b,r:
a:=numer(p):
b:=denom(p):
r:=rand(1..b)():
if  r<=a then
  RETURN(1):
else
 RETURN(0):
fi:
end:


#LDie(A): inputs a list of non-negative integers [a[1],..., a[k]] (say) outputs i with probability a[i]/(a[1]+...+a[k]). Try
#LDie([1,2,3]);
#LDie is short for "Loaded die"
LDie:=proc(A) local N,i,j,r:

N:=add(A[i],i=1..nops(A)):
r:=rand(1..N)():

for i from 1 to nops(A) while add(A[j],j=1..i-1)<r do od:
i-1:

end:

#Paths(m,n): The set of lattice paths from [0,0] to [m,n] with atomic steps [1,0] (Called 1) , [0,1] (called -1)
Paths:=proc(m,n) local S1,S2,s:
option remember:

if m<0 or n<0 then
 RETURN({}):
fi:
if m=0 and n=0 then
 RETURN({[]}):
fi:
S1:=Paths(m-1,n):
S2:= Paths(m,n-1):
{seq([op(s),1], s in S1)  , seq([op(s),-1], s in S2)  }:
end:



#GPaths(m,n): The set of lattice paths from [0,0] to [m,n] with atomic steps [1,0] (Called 1) , [0,1] (called -1)
#that stay in m>=n
GPaths:=proc(m,n) local S1,S2,s:
option remember:

if ( m<0 or n<0 or m<n) then
 RETURN({}):
fi:
if m=0 and n=0 then
 RETURN({[]}):
fi:
S1:=GPaths(m-1,n):
S2:= GPaths(m,n-1):
{seq([op(s),1], s in S1)  , seq([op(s),-1], s in S2)  }:
end:


NuPaths:=proc(m,n) option remember:
if m<0 or n<0 then 
0:
elif m=0 and n=0 then
1:
else
NuPaths(m-1,n)+NuPaths(m,n-1):
fi:
end:


NuGPaths:=proc(m,n) option remember:
if (m<0 or n<0 or m<n)  then 
0:
elif m=0 and n=0 then
1:
else
NuGPaths(m-1,n)+NuGPaths(m,n-1):
fi:
end:



#RPath(m,n): A (uniformaly random) path from [0,0] to [m,n]. Try:
#RPath(6,5);
RPath:=proc(m,n) local c:
if m=0 and n=0 then
 RETURN([]):
fi:

c:=LDie([NuPaths(m-1,n),NuPaths(m,n-1)]):

if c=1 then
 [op(RPath(m-1,n)),1]:
else
 [op(RPath(m,n-1)),2]:
fi:
end:


#RGPath(m,n): A (uniformaly random) path from [0,0] to [m,n]. Try:
#RGPath(6,5);
RGPath:=proc(m,n) local c:
if m=0 and n=0 then
 RETURN([]):
fi:

c:=LDie([NuGPaths(m-1,n),NuGPaths(m,n-1)]):

if c=1 then
 [op(RGPath(m-1,n)),1]:
else
 [op(RGPath(m,n-1)),2]:
fi:
end:



#CycShi(L): The set of cyclic shifts of the list L
CycShi:=proc(L) local i:
{seq([op(i..nops(L),L),op(1..i-1,L)],i=1..nops(L))}:
end:


#DvoMot(n): illustration and empirical confirmation of the Dvoretzky-Motzkin proof that
#the number of good paths (namely NuGPaths(n,n) ) is given by the Catalan number
#(2*n+1)!/(n!*(n+1)!) by showing that the associated set of GPaths(n,n) when 1 is
#appended to the end, all have distinct cyclic shifts (so 2*n+1 of them) and
#their union is Paths(n+1,n) whose number of elements is binomial(2*n+1,n)=(2*n+1)!/(n!*(n+1)!)
DvoMot:=proc(n) local S,s:

#S is the set of Good paths from [0,0] to [n,n]
S:=GPaths(n,n):
#Now we consider the associated set where we append 1 to each
S:={seq([op(s),1], s in S)}:

#Now we check empirically that all the cyclic shifts are distinct

for s in S do

if nops(CycShi(s))<>2*n+1 then
  print(`Something is wrong`):
 RETURN(false):
fi:
od:


#We now check that the union of the cyclic shifts of the members of S is Paths(n+1,n)

evalb({seq(op(CycShi(s)), s in S)}=Paths(n+1,n)):
end:

#DrawP(P): Draws the path P
DrawP:=proc(P) local P1,Pt,i:
P1:=[[0,0]]:
Pt:=[0,0]:
for i from 1 to nops(P) do
if P[i]=1 then
 Pt:=Pt+[1,0]:
else
 Pt:=Pt+[0,1]:
fi:
P1:=[op(P1),Pt]:
od:

plot(P1,axes=none):

end: