# Please do not post homework
# Ravali Bommanaboina, 9/20/20, HW3
# 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(L1) local pi,i,j:
option remember:
i:=1;
j:=0;
for pi in L1 do:
	if pi=i then
		j:=j+1;
	fi:
i:=i+1;
end do;

RETURN(j);
end:

# Question 3---------------------------------------------

#MyPermsL(L): The list of permutations in the list L, in LEXICOGRAPHIC order given by L.  For example,
#MyPermsL([1,2]) outputs [[1,2],[2,1]].
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:

#MyPerms(n): The list of permutations of [1,2..., n]. For example
#MyPerms(2) outputs [[1,2],[2,1]]
MyPerms:=proc(n) local i:
 MyPermsL([seq(i,i=1..n)]):
end:

Der:=proc(i) local L1,L2,L3:
L3:={};
	L1:=MyPerms(i);
	for L2 in L1 do
		if NuFP(L2)=0 then
			L3:=[op(L3),L2];
		fi:
	end do:
RETURN(convert(L3,set));
end:

# Question 4---------------------------------------------

#[seq(nops(Der(i)), i = 0 .. 8)]; -> [1, 0, 1, 2, 9, 44, 265, 1854, 14833]
# Each element in the returned list is the number of derangements for Der(i) (a list of length i) when i = [0..8]

# yes. I was able to enter the above sequence into OEIS. It correctly identified that I was returning the number of derangements.
# I copied what OEIS returned below.
#a(n) is the number of Derangements of length n. A derangement of length n is a permutation p of {1,2,...,n} for which the smallest of all the ascents of p (taken to be n if there are no ascents) is even. Example: a(3) = 2 because we have 213 and 312 (smallest ascents at i = 2). See the J. Désarménien link and the Bona reference (p. 118). - Emeric Deutsch, Dec 28 2007

# Question 5---------------------------------------------
# 1, 1, 2, 4, 8, 16, 32...
#a(0)=1
#a(n)=2^(n-1)