#Ok to post homework
#Tifany Tong, September 20th, 2020, HW #3

#Question 1:

# Bnk(10,5)[20] = [0,0,0,1,1,1,1,0,1,0]
# MyChoose({1,2,3,4,5,6},2)[5] = {1,6}
# MyPermsL([r,u,t,g,e,r,s])[100] = [r, u, s, t, e, r, g]
# WtoS[1,0,0,0,1] = {1,5}


#Question 2:

NuFP:=proc(arr) local n,i,S:
  n:=nops(arr):
  S:=0:
  for i from 1 to n do
    if arr[i] = i then
       S:=S+1:
    fi:
  od:
  S:
  end:

#Question 3:

MyPermsL:=proc(L) local n,PL,PL1,i,p:
option remember:

n:=nops(L):

if n=0 then
 RETURN([[]]):
fi:

 PL:=[]:

for i from 1 to nops(L) do

 PL1:=MyPermsL([op(1..i-1,L),op(i+1..n,L)]):

 PL:=[op(PL),seq([L[i],op(p)], p in PL1)]:

od:

PL:
end:


Der:=proc(n) local L,i,j,S,len:
  L:=MyPermsL([seq(i,i=1..n)]):
  S:=[]:
  len:=nops(L):
  for j from 1 to len do
    if NuFP(L[j]) = 0 then
       S:= [op(S), L[j]]:
    fi:
  od:
  S:
  end:

#Question 4

# The sequence [seq(nops(Der(i)),i=0..8)] = [1, 0, 1, 2, 9, 44, 265, 1854, 14833]. Yes, I can find this in the OEIS as A166. The first search result
# says: "Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points." The sequence I got
# was the first part of the sequence. 

#Question 5

# I conjecture that Comps(i) = 2^(i-1) as doing [seq(nops(Comps(i)), i=1..8)] = [1,2,4,8,16,32,64,128], which is
# [2^0,2^1, 2^2, 2^3, 2^4, 2^5, 2^6, 2^7].