# hw15 - Pablo Blanco
# not OK to post

read(`C15.txt`):

# up-and-down permutation:
# If i is odd, then pi(i) < pi(i+1)
# If i is even, then pi(i) > pi(i+1)

# 1. Why is the largest number always at an even index?
# Answer: if the largest were at an odd index i, then pi(i) < pi(i+1) could not be satisfied.

# 2. Satisfying the recurrence: 
# To construct any up-down permutation of length n, we can pick an even index 2*k in which we will place "n".
# Then, before that index you have a UD perm of length a_{2*k-1} and, after, one of length a_{n-2*k}.
# The binomial coefficient determines... how you choose your labels.

# 3. Famous constant: PI !!
#                                    (not factorial).

UDc:=proc(n) local k:
 option remember:
 if n=1 or n=0 then
  return(1):
 fi:

 add(binomial(n-1,2*k-1)*UDc(2*k-1)*UDc(n-2*k),k=1..trunc(n/2)):
end: