Help:=proc(): print(`choose1(S,k), Fnk(n,k) , powerset1(S) `): 
print(`powerset2(S) , Lara(n), aS(n), SeqaS(N), SeqaC(n) `):
print(`Rat(L) , Fn(n)`):

end:


Lara:=proc(n) local i: {seq(i,i=1..n)}: end:

#choose1(S,k): inputs a set S and a non-negative
#integer k, and outputs the set of k-element 
#subsets of S. For example, try:
#choose1({1,2,3},2);
choose1:=proc(S,k) local fa,S1,T1,T2,t2:

option remember:

if not type(S,set) then
ERROR(`Bad input`):
fi:

if k=0 then
  RETURN({{}}):
fi:

if ( k>nops(S) or k<0 or not type(k,integer) ) then
   RETURN({}):
fi:

fa:=S[1]:

S1:=S minus {fa}:

T1:=choose1(S1,k):

T2:=choose1(S1,k-1):

T1 union { seq(t2 union {fa}, t2 in T2) }:

end:

##Fnk(n,k): the set of lists of 1'2 and 2's
#of length k, that sum to n
#For example:
#Fnk(5,3)={[1,2,2],[2,1,2],[2,2,1]}  .

Fnk:=proc(n,k) local a, F1,F2 :
option remember:

if n<0 or k<0 then
  RETURN({}):
fi:

if n=0 then
  if k=0 then
     RETURN({[]}):
  else
    RETURN({}):
   fi:
fi:

###The case where the last element is 1
F1:=Fnk(n-1,k-1):
###The case where the last element is 2
F2:=Fnk(n-2,k-1):

{seq([op(f1),1],f1 in F1),
seq([op(f2),2],f2 in F2)}:
end:


#powerset1(S): the set of ALL subsets of a set S
powerset1:=proc(S) local k:

{ seq( op( choose1(S,k) ) , k=0..nops(S) ) }:  
end:

#powerset2(S):directly
powerset2:=proc(S) local baxter,S1,T1,t1:
option remember:

if S={} then
 RETURN({{}}):
else

baxter:=S[1]:

S1:=S minus {baxter}:

T1:=powerset2(S1):

T1 union { seq( { op(t1), baxter}   , t1 in T1) }:



fi:

end:


#aS(n): the number of subsets of {1, ..., n} the
#very stupid way
aS:=proc(n) : nops(powerset2(Lara(n))): end:




aC:=proc(n) option remember:

if n=0 then
 1:
else
 2*aC(n-1):
fi:

end:
SeqaC:=proc(N) local n: [seq(aC(n),n=1..N)]:end:

SeqaS:=proc(N) local n: [seq(aS(n),n=1..N)]:end:


Rat:=proc(L) local i: [seq(L[i+1]/L[i],i=1..nops(L)-1)]: end:


#Fn(n): all lists of {1,2}'s that add up to n
Fn:=proc(n) local F1,F2,f1,f2: option remember:

if n<0 then
 RETURN({}):
elif n=0 then
 RETURN({[]}):
else
  F1:=Fn(n-1):
  F2:=Fn(n-2):

 { seq([1, op(f1)],f1 in F1)} union  { seq([2, op(f2)],f2 in F2)}:

fi:

end:


#fn(n): the number of lists of {1,2}'s that add up to n
fn:=proc(n) local F1,F2,f1,f2: option remember:

if n<0 then
 RETURN(0):
elif n=0 then
 RETURN(1):
else
  

fn(n-1)+fn(n-2):

fi:

end: