# OK to post homework
# Aurora Hiveley, 3/14/25, Assignment 15

Help := proc(): print(`UDc(n)`): end:

with(combinat):

## problem 1
# By looking at UDset(7) and Udset(8), observer that the location of "n" the largest entry (7 and 8 respectively) are always at EVEN locations. Why?

# the largest entry "n" must form an "up" because there are no numbers larger than it in the permutation. thus it must be sandwiched between two smaller 
# numbers to form a peak. in order for the permutation to be up-down, a peak must be in an even position since a shift from an odd to an even must be an up 
# and a shift from an even to an odd must be a down. since UDset consists of up-down permutations, the peaks (including "n" itself) must occur in even positions.



## problem 2 
# Using this fact, explain why the number of up-down permutations of length n (that is computed by brute force using UD(n)), let's call it a(n), 
# satisfies the non-linear recurrence a(n)=Sum(binomial(n-1,2*k-1)*a(2*k-1)*a(n-2*k),k=1..trunc(n/2)):
# (subject to the initial condition a(1)=1).

# to form an up-down permutation of length n, we first choose an even index position for n. we call this position j (= 2k for some k.) 
# to the left of "n", there are j-1 permutation entries, where we note that j-1 is odd. this sub-permutation of length j-1 must also be up-down, 
# and we observe that the last two entries form a "down" since we go from an even position to an odd one. furthermore, it does not matter what the (j-1)-th 
# entry is -- any possible entry will form the necessary "up" with "n" in position j. 
# there are binomial(n-1,j-l) = binomial(n-1,2k-1) ways to choose the permutation entries which are to the left of "n", and a(j-1) = a(2k-1) ways to form 
# an up-down sub-permutation with those entries.
# this leaves (n-1)-(j-1) = n-2k entries to the right of "n", and there are a(n-2k) ways to form an up-down sub-permutation from those entries. note again
# that since "n" is in an even position, it does not matter what entry the right sub-permutation starts with, it will always form the necessary "down" from position 
# j to j+1, and then the sub-permutation begins with an "up" from position j+1 to j+2 by construction. 
# we sum this expression across all possible even indices where "n" may go by letting k range from 1 to n/2, and we have the desired recurrence!



## problem 3  
# UDc(n) (clever version of UD(n)) using the recurrence, with `option remember`

UDc := proc(n) local k:
option remember:

if n <= 1 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:




# Make sure that UDc(n) and UD(n) coincide for 1<=n<=8.
# [seq(UD(n), n=1..8)];
# output: [1, 1, 2, 5, 16, 61, 272, 1385]
# [seq(UDc(n), n=1..8)];
# output: [1, 1, 2, 5, 16, 61, 272, 1385]
# yay! 

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

# Does it seem to converge to any famous constant?
# hey, that looks like pi :)










### copied from C15.txt 

#C15.txt, March 13, 2025
Help15:=proc(n): print(`A(n), IsID(pi),UD(n), UDset(n) `):end:

A:=proc(n)
1/(binomial(2*n,n)*sqrt(n)/4^n)^2;
end:

#IsUD(pi): Is the permutation pi up-down
IsUD:=proc(pi) local n,i:
n:=nops(pi):
for i from 1 to n-1 do

if i mod 2=1 then
if pi[i]>pi[i+1] then
  RETURN(false):
fi:
fi:

if i mod 2=0 then
if pi[i]<pi[i+1] then
  RETURN(false):
fi:
fi:

od:
true:
end:

with(combinat):
#UD(n): the number of up-down permutations of length n the stupid way
UD:=proc(n) local s,S:
S:=permute(n):
coeff(add(IsUD(s), s in S),true,1):
end:

#UDset(n): the set of up-down permutations of length n the stupid way
UDset:=proc(n) local s,S,G:
S:=permute(n):
G:={}:

for s in S do
 if IsUD(s) then
  G:=G union {s}:
 fi:
od:
G:
end: