#C15.txt: Celeberating Pi Day
#
Help15:=proc(): print(`IsUD(pi) , UD(n), ud(n) , udPi(n) `): end:

with(combinat):
#IsUD(pi): Is the permutation pi an up-down permutation?
IsUD:=proc(pi) local n,i:
n:=nops(pi):

for i from 1 to n-1 do
 if i mod 2=1 and pi[i]>pi[i+1] then
    RETURN(false):
 fi:
  
   if i mod 2=0 and  pi[i]<pi[i+1] then
     RETURN(false):
    fi:
 
od:
true:
end:

#UD(n): The set of up-down permutations of length n
UD:=proc(n) local S, pi,G:
S:=permute(n):
G:={}:
for pi in S do
 if IsUD(pi) then
   G:=G union {pi}:
 fi:
od:
G:
end:


#ud(n): The NUMBER OF up-down permutations of length n

#Sum(i=1..trunc(n/2), binomial(n-1, 2*i-1)*ud(2*i-1)*ud(n-2*i)) 
ud:=proc(n) local i:
option remember:
if n=0 or n=1 then
 RETURN(1):
else
 add(binomial(n-1,2*i-1)*ud(2*i-1)*ud(n-2*i),i=1..trunc(n/2)):
fi:

end:

#A (conjectured) approximation to Pi using the Up-Down permutations sequence
udPi:=proc(n)
evalf(2*n*ud(n-1)/ud(n)):
end: