> #ok to post
;
> #Yifan Zhang, 09/14/2020, hw3
;
> #------------------------------------------------------
;
> #Q1. 
;
> 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 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:
> 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 from 1 to n do
>  if w[i]=1 then
>   S:=S union {i}:
>  fi:
> od:
> 
> S:
> 
> end:
> WtoS([1,0,0,0,1]);
{1, 5}

;
> 
;
> #------------------------------------------------------
;
> #Q2.
;
> #NuFP(pi)
;
> NuFP := proc(P) local n,i,counter:
> n := nops(P):
> counter :=0:
> 
> for i from 1 to n do
>  if P[i] = i then
>  counter := counter +1;
>  fi:
> od:
> counter:
> end:
> NuFP([1,2,3,4]);
4

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

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

;
> 
;
> MyPerms:=proc(n) local i:
>  MyPermsL([seq(i,i=1..n)]):
> end:
> #------------------------------------------------------
;
> #Q3.
;
> Der :=proc(n) local  m, c, L, i, j, boo:
> option remember:
> L := {}:
> 
> for i from 1 to nops(MyPerms(n)) do     
>     boo:=1:
>   
>     for j from 1 to nops(MyPerms(n)[i]) do    #locate each element
>         if evalb(j = ((MyPerms(n)[i])[j])) then 
>             boo:= 0;
>         fi:
>     od:
>     if evalb(boo = 1) then
>         L := {op(L), MyPerms(n)[i]};    # output 
>     fi:
> od:
> L;     # resut
> end:
> 
;
> Der(3);
{[2, 3, 1], [3, 1, 2]}

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

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

;
> #Yes! I can find it in the OEIS. It's a part of the number of permutations of n elements with no fixed points.
;
> 
;
> 
;
> #------------------------------------------------------------------------
;
> #Q5.
;
> 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 from 1 to n do
>  S1:=Comps(n-i):
>  S:=S union {seq( [op(s),i], s in S1)}:
> od:
> 
> S:
> end:
> [seq(nops(Comps(i)), i=1..8)];
[1, 2, 4, 8, 16, 32, 64, 128]

;
> # Since 1,2,4,8,16,32 are the power of 2 with an increasingly order, I conject the formula is
;
> #nops(Comps(i))  =  2^(i-1)
;
> 
;
> Comps(1); Comps(2); Comps(3);
{[1]}
{[2], [1, 1]}
{[3], [1, 2], [2, 1], [1, 1, 1]}

;
> #------------------------------------------------------------------------
;
> #Q6. 
;
> #Proof: 
> #Let P(n) be the statement that the number of the set of composition of n is 2^(n-1). 
;
> #Base Case: For n = 1, the composition of 1 is {[1]}, so the number of the set of composition of 1 is 1. RHS = 2^(1-1) = 2^0 = 1. LHS = RHS.
;
> #Induction Hypothesis:
> #The number of the set of composition of n-1 is 2^(n-1-1), which is 2^(n-2).
;
> #Induction Steps: By the induction hypothesis, nops(Comps(n-1)) = 2^(n-2). Every time from the recursion, Comps(n) = S union {seq([ops(s),i], s in S1)}. And since S1 is Comps(n-1), nops(S1) = nops(Comps(n-1)) = 2^(n-2). From the recursion function, Comps(n) = S union {seq([ops(s),i], s in S1)}, S is the result of Comp(n-1), hence S has 2^(n-2) elements, and{seq([ops(s),i], s in S1)} has nops(S1) elements that is 2^(n-2) elements. Hence, Comps(n) has 2*2^(n-2) elements=>2^(n-2+1)=2^(n-1) elements. Therefore proved the statement by the induction. QED.
;
> 
;
> 
;