#OK to post
#Yuxuan Yang, March 14th, Assignment 15

with(combinat):
#1
UDbetter:=proc(n) local pn,S,i,j,A,B,k,p,C,Ckco:
option remember:
if n=0 then 
RETURN({[]}):
fi:
if n=1 then 
RETURN({[1]}):
fi:
S:={}:
for pn from 2 by 2 to n do 
A:=UDbetter(pn-1):
B:=UDbetter(n-pn):
C:=choose({seq(1..n-1)},pn-1):
for i from 1 to nops(A) do
for j from 1 to nops(B) do
for k from 1 to nops(C) do
Ckco:={seq(1..n-1)} minus C[k]:
S:=S union {[seq(C[k][A[i][p]],p=1..pn-1),n,seq(Ckco[B[j][p]],p=1..n-pn)]}:
od:
od:
od:
od:
S:
end:





#2

# to prove cos(x)*add(ud(n)/n! * x^n)=1+sin(x)
# consider writing {1,2,...,n} in the following form
# a_1<a_2<a_3<..<a_(2k) and b_1<b_2>b_3<b_4>...b_m
# an even-length increasing sequence and a up-down sequence
# a_1,a_2,...,a_(2k),b_1,...b_m are distinct and compose {1..n}.
# each one of these ordered pair of sequence has weight (-1)^k in cos(x)*add(ud(n)/n! * x^n)
# Here is the killer-involution for
# a_1<a_2<a_3<..<a_(2k) and b_1<b_2>b_3<b_4>...b_m
# (1) if a_(2k)<b_1 or k=0, map it to  a_1<a_2<a_3<..<a_(2k)<b_1<b_2 and b_3<b_4>...b_m                     (need m>=2)
# (2) if a_(2k)>b_1 or m=0, map it to  a_1<a_2<a_3<..<a_(2k-2) and a_(2k-1)<a_(2k)>b_1<b_2>b_3<b_4>...b_m   (need k>=1)    
# the sign of weight is reversed by the map, so they are cancelled in cos(x)*add(ud(n)/n! * x^n)
# the remaining terms which are not cancelled are:
#  if m=0, then k=0, the corresponding egf is 1
#  if m=1, then a_(2k)<b_1 or k=0, it is an increasing odd-length sequence a_1<a_2<a_3<..<a_(2k)<b_1 with weight (-1)^k, the corresponding egf is sin(x)
# Therefore, cos(x)*add(ud(n)/n! * x^n)=1+sin(x).










#3
PiJG:=proc(dig) local i,j:
Digits:=3*dig+10:
i:=13:
for j from 1 to dig do
i:=evalf(i+(-1)^j*binomial(2*j,j)^5*(820*j^2+180*j+13)/2^(20*j)): 
od:
Digits:=dig:
evalf(sqrt(128/i)):
end:

#PiJG(10000) gives the same output as Digits:=10000:evalf(Pi): on my computer.











#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:

#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: