#OK to post homework
#William Wang, 9/12/2020, As

#1.
Bnk := proc(n, k) local S1, S2, s:
option remember:
if n = 0 then 
 if k = 0 then 
  RETURN({[]}):
 else
  RETURN({}):
 fi:
fi:
S1 := Bnk(n - 1, k):
S2 := Bnk(n - 1, k - 1):
{seq([op(s), 0], s in S1), seq([op(s), 1], s in S2)}:
end:

Bnk(10, 5)[20];
                 [0, 0, 0, 1, 1, 1, 1, 0, 1, 0]


MyChoose := proc(S, k) local a, S1, s, P1, P2:
option remember:
if S = {} then 
 if k = 0 then 
  RETURN({{}}):
 else
  RETURN({}):
 fi:
fi:
a := S[1]:
S1 := S minus {a}:
P1 := MyChoose(S1, k):
P2 := MyChoose(S1, k - 1):
P1 union {seq(s union {a}, s in P2)}:
end:

MyChoose({1, 2, 3, 4, 5, 6}, 2)[5];
                             {1, 6}


MyPermsL := 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 := 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:

MyPermsL([r, u, t, g, e, r, s])[100];
                     [r, u, s, t, e, r, g]


WtoS := proc(w) local n, i, S:
n := nops(w):
S := {}:
for i to n do
 if w[i] = 1 then
  S := S union {i}:
 fi:
od:
S:
end:

WtoS([1, 0, 0, 0, 1]);
                             {1, 5}


#2.
#Write a procedure NuFP(pi) that inputs a permutation pi of [1,...,n] and outputs the number of fixed points of pi.
#For example, NuFP([1,2,3,4]) = 4, NuFP([2,1,3,4]) = 2, NuFP([3,4,1,2]) = 0

NuFP := proc(L) local x, n, i:
x := 0;
n := nops(L);
for i to n do
 if i = L[i] then
  ++x:
 fi:
od:
x:
end:

NuFP([1, 2, 3, 4]);
                               4

NuFP([2, 1, 3, 4]);
                               2

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


#3.
#A permutation is called a derangement if it has no fixed points. For example, [2,3,1] is a derangement. Use procedure MyPerms(n) to write a procedure Der(n) that inputs a nonnegative integer n and outputs the set of derangements of length n.
#For example, Der(2) = {[2,1]}, Der(3) = {[2,3,1],[3,1,2]}

MyPerms := proc(n) local i:
 MyPermsL([seq(i, i = 1 .. n)]):
end:

Der := proc(n) local S, D, i, j:
S := MyPerms(n);
D := {};
for i to nops(S) do
 if 0 = NuFP(S[i]) then
  D := D union {S[i]}:
 fi:
od:
D:
end:

Der(2);
                            {[2, 1]}

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


#4.
#What is the sequence [seq(nops(Der(i)),i=0..8)]? Can you find it in the OEIS (Online Encyclopedia of Integer Sequences)?

[seq(nops(Der(i)), i = 0 .. 8)];
             [1, 0, 1, 2, 9, 44, 265, 1854, 14833]


#Yes, it can be found at https://oeis.org/A000166

#5.
#Study the code for Comps(n) and understand it. What is [seq(nops(Comps(i)),i=1..8)]?

Comps := proc(n) local S, S1, i, s:
option remember:
if n < 0 then
 RETURN({}):
fi:
if n = 0 then
 RETURN({[]}):
fi:
S := {}:
for i to n do
 S1 := Comps(n - i):
 S := S union {seq([op(s), i], s in S1)}:
od:
end:

[seq(nops(Comps(i)), i = 1 .. 8)];
                 [1, 2, 4, 8, 16, 32, 64, 128]

#Conjecture: The number of compositions of n is equal to 2^(n-1).

#6.
#Proof of the above conjecture: