#OK to post homework
#Joseph Koutsoutis, 03-16-2025, Assignment 15

read `C15.txt`:

#1

#We observe that the location of "n" is even since it cannot be placed at 
#position 1 as the next entry must be larger than n, and it cannot be 
#placed at any other odd position as the preceding value must be
#larger than n.

#2

#The number of up-down permutations of length n, a(n), satisfies the recurrence

#a(n)=Sum(binomial(n-1,2*k-1)*a(2*k-1)*a(n-2*k),k=1..trunc(n/2)): 

#since we can understand the terms of this sum as first choosing which even location to
#place n and afterwards choosing which numbers to assign to the left of position 2k and to the right.
#Observing that we obtain an up-down permutation iff the numbers assigned to the left and right
#form up-down permutations implies the recurrence.

#3

UDc := proc(n) local k:
  option remember:
  if n = 0 or n = 1 then:
    return 1:
  fi:
  add(binomial(n-1,2*k-1)*UDc(2*k-1)*UDc(n-2*k), k=1..floor(n/2)):
end:

#evalf([seq(2*n*a(n-1)/a(n),n=1000..1010)]) outputted
#[3.141592654, 3.141592654, 3.141592654, 3.141592654, 3.141592654, 
#3.141592654, 3.141592654, 3.141592654, 3.141592654, 3.141592654, 
#3.141592654]