#OK to post homework
#George Spahn, 3/14/2021, Assignment 15

with(combinat):

#UDbetter(n) smarter method for enumerating up down permutations

UDbetter:=proc(n) local L,rec,ls,rs,s,p,q,k:

if n=1 then
 RETURN({[1]})
fi:
rec:= [seq(UDbetter(i),i=1..n-1)]:

L := {}:
s:={seq([op([op(powerset(n-1))][i])], i = 1 .. 2^(n-1))}:

for ls in s do  #ls contains the numbers to the left of n
 if irem(nops(ls),2) = 0 then
  next:
 fi:
 rs := []:
 for k from 1 to n-1 do
  if not(k in ls) then
   rs := [op(rs),k]:
  fi:
 od:            #rs contains the numbers to the right of n
 for p in rec[nops(ls)] do
  if nops(ls) = n-1 then 
   L := L union {[ op(subs({seq(j=ls[j],j=1..nops(ls))},p)) ,n ]}:
  else
   for q in rec[n-1-nops(ls)] do
    L := L union {[ op(subs({seq(j=ls[j],j=1..nops(ls))},p)) ,n, 
                    op(subs({seq(j=rs[j],j=1..nops(rs))},q)) ]}:
   od:
  fi:
 od:
od:
L:
end: 


#2  cos(x) * (the egf for a(n)) gives an efg for the number of ways to 
# partition [n] into two subsets, sort the first subset into a 
# permutation in increasing order and with even length,
# and sort the second subset into an updown permutation,
# weigted by -1 if the number of elements in the first subset is not 
# divisible by 4

# To make a killer involution we need to move two elements from one 
# side of the ordered pair to the other such that the operation is 
# invertible.

#