#OK to post homework
#TaerimKim,9/18/2020,Assignment 3

#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}


#2.
NuFP := proc(pi) local i, a, n; 
option remember; 
a := 0; 
n := nops(pi); 
for i to n do 
if op(i, pi) = i then 
a++; 
end if; 
end do; 
print(a); 
end proc;

#examples
NuFP([1, 2, 3, 4]);
                               4
NuFP([0, 2, 2, 4]);
                               2

#3.
#DerL(L);Modified version of MyPermsL;
DerL := proc(L) local n, PL, PL1, i, p; 
option remember; 
n := nops(L); 

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

PL := {}; 

for i to nops(L) do 
PL1 := DerL([op(1 .. i - 1, L), op(i + 1 .. n, L)]); 
PL := {op(PL), seq([L[i], op(p)], p in PL1)}; 
od; 
#`Not printing PL here, instead we carry on the Der statement for printing out the results
end;

#Der(n): target statement
Der := proc(n) local i, s1, s2; 
option remember:  
if n=0 then  
return {}  
fi: #Der(0) is empty set

s1 := {[seq(i, i = 1 .. n)]}; #fixed point subset
s2 := DerL([seq(i, i = 1 .. n)]); #all subsets(fixed point set + derangement sets)
s2 minus s1; 
#`by minusing the subset with fixed points, we get only derangement subsets`

end proc;

#example
Der(3);
    {[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}
Der(4);
   {[1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], 

     [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], 

     [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], 

     [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], 

     [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], 

     [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]}

#4. 
[seq(nops(Der(i)), i = 0 .. 8)];
            [0, 0, 1, 5, 23, 119, 719, 5039, 40319]
#IN OEIS, it is sequence A033312, which has explicit formula of a(n) = n! - 1.

#5. 
[seq(nops(Comps(i)), i = 1 .. 8)];
                 [1, 2, 4, 8, 16, 32, 64, 128]
#From the given seq, we can see that Comps(n) can be formulated into 2^(n - 1)
#Proof:
evalf([seq(nops(Comps(i)), i = 1 .. 8)] = [seq(2^(n - 1), n = 1 .. 8)]);
 [1., 2., 4., 8., 16., 32., 64., 128.] = [1., 2., 4., 8., 16., 
   32., 64., 128.]
evalb([seq(nops(Comps(i)), i = 1 .. 8)] = [seq(2^(n - 1), n = 1 .. 8)]);
                              true