# Daniel Yang, Due Sept. 20, 9:00pm
# OK to post Homwork
# 1)After looking at the code, we get that:  
# 	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 & 3) 

#M3.txt: for hw3
with(combinat):
Help3:=proc():print(`NuFP(w), Der(n), MyPermsL(L), MyPerms(n)`): end:
	
	# 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:

	# NuFP(w): inputs set {n[1],...,n[k]} and counts the number of cases where pi[i] = i
	# For example
	# NuFP([2,1,3,4]); should output 1
	  NuFP:=proc(w) local n,i,S:
	
	  n:=nops(w):
	
	  S:= 0:
	
	  for i from 1 to n do
  	   if w[i]=i then
	    S:=S + 1:
	   fi:
	  od:

	  S:

	  end:

	# Der(n): inputs n such that it outputs all derangements of the sequence from 1..n
	# For example
	# Der(3); should output {[2,3,1],[3,1,2]}
	  Der:=proc(w) local i,S,L:
	
	  P:=MyPerms(n):
	  L:=nops(X):
	  S:={}:
	
	
	  for i from 1 to nops(P) do
  	   if NuFP(P[i]) = 0 then
	    S:=S union {P[i]}:
	   fi:
	  od:

	  S:

	  end:


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

#	1,1,1,1,1,1,1,1,1
# 	We can find this on OEIS as A000012

# 5) Study the code for Comps(n) and understand it. What is
#    [seq(nops(Comps(i)),i=1..8)]?
#    Can you conjecture a formula for the number of compositions of n?
#    [Optional Challenge] PROVE IT! 

#	1, 2, 4, 8, 16, 32, 64, 128
#	Formula:NuComps(k) = 2^K