#HomeWork#5
#OK to post homework
#Abrar Almahmeed, Feb.8

#Question 2: 

Ans: By computing factor(WtE(powerset(n),S->nops(S),x)); for n = 1,2,3,4 we observe that the result is 
                 
                                       (1+x)^n

we conjecture that this expression holds for all natural number n. 


Now, we need to prove that for any natural number n the above identity holds,

let Sn={1,..,n} and A:=powerset(n), which is the set of all subsets of Sn then  

       WtE(A,Sn->nops(Sn),x) defined as sum of all x^|A|, where |A| is the size of set A = (1+x)^n

#Proof by induction:

for n=1, we have S1={1} and A={{},{1}} with 

             WtE(A,S1->nops(S1),x) = sum of all x^|A| = x^0 + x^1 = 1 + x = (1+x)^1.

Assume that for some k>=1 we have 

             WtE(A,Sk->nops(Sk),x) = sum of all x^|A| = (1+x)^k  ---------(1)

For k+1, Sk+1={1,2,...,k,k+1} and the subsets for Sk+1 are either does not contain the element k+1 or contain k+1 

Case I: Does not contain the element k+1, thus we have the subsets of Sk which (1) holds. 

Case II: Contain the element k+1, we can get it by adding the element to the set Sk, this means that the size of the subsets A of Sk will increases by one (|A|+1) hence  

            sum of all x^|A|+1 = x(1+x)^k = x.WtE(A,Sk->nops(Sk),x)

from case I and II we have that 

              WtE(A,Sk+1->nops(Sk+1),x) = (1+x)^k + x(1+x)^k = (1+x)^k (1+x) = (1+x)^k+1 
 
thus the identity holds for k+1.

By mathematical induction, the identity is true for all natural numbers n.


#Question 3:  Write a procedure NumPat3(pi,sig);

NumPat3:=proc(pi,sig):
local n,i,j,k,co,S: 
n:=nops(pi): co:=0:
if nops(sig)<>3 then 
    return Fail:
fi:
for i from 1 to n-2 do
  for j from i+1 to n-1 do
    for k from j+1 to n do
        S:=[pi[i],pi[j],pi[k]]:
         if redu(S)=sig then 
                co:=co+1:
         fi:
     od:
  od:
od:
co:
end:

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

NumPat3([2,3,1,4],[2,1,3,4]);
                              Fail


#Question 4:

for j=0 we have 
                 [seq(coeff(L[i],x,0),i=1..nops(L))] = [1, 2, 5, 14, 42, 132, 429]

this sequence appears in OEIS with A number A000108.

for j=1 we have 
                 [seq(coeff(L[i],x,1),i=1..nops(L))] = [0, 0, 1, 6, 27, 110, 429]

this sequence appears in OEIS with A number A115145.

for j=2 we have 
                 [seq(coeff(L[i],x,2),i=1..nops(L))] = [0, 0, 0, 3, 24, 133, 635]

this sequence appears in OEIS with A number A001089.

for j=3 we have 
                 [seq(coeff(L[i],x,3),i=1..nops(L))] = [0, 0, 0, 0, 7, 70, 461]

this sequence does not appears in OEIS.


#Question 5:
 
##for [1,3,2] L:=[seq(WtE(permute(n),pi->NumPat3(pi,[1,3,2]),x),n=1..7)]:

[seq(coeff(L[n],x,0),n=1..nops(L))];
                   [1, 2, 5, 14, 42, 132, 429] in OEIS with A number A000108.

[seq(coeff(L[i],x,1),i=1..nops(L))];
                   [0, 0, 1, 5, 21, 84, 330] not in OEIS.

[seq(coeff(L[i],x,2),i=1..nops(L))];
                   [0, 0, 0, 4, 23, 107, 464] not in OEIS.

[seq(coeff(L[i],x,3),i=1..nops(L))];
                   [0, 0, 0, 1, 14, 82, 410] not in OEIS. 



##for [2,1,3], [2,3,1], and [3,1,2]  

These patterns yield exactly the same coefficient sequences as the pattern [1,3,2].


##for the pattern [3,2,1] it has the same coefficient sequences as the pattern [1,2,3] in Question 4.