#OK to post homework
#Sam Minkin, 09/20, Assignment 3

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


Problem 2:

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

c:

end:

Problem 3:

Der:=proc(n) local S, s, i, l, R, isDer:
S:=MyPerms(n):
R:={}:

for s in S do
	l:=nops(s):
	isDer:=true:
	for i from 1 to l do
		if s[i] = i then
			isDer:=false:
		fi:
	od:
	if isDer = true then
		R:=R union {s}:
	fi:
od:

R:

end:

Problem 4:

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

According to OEIS, this sequences represents: Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.
OEIS Sequence: A000166

Problem 5:

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

For i=1..8, the sequence follows the formula a(n) := 2^{n-1}