# HomeWork#2
#OK to post homework
#Abrar Almahmeed, Feb.1, Assignment 2


# Question 1: Read and do all the examples, plus make up similar ones, in pages 30-60 of Frank Garvan's awesome Maple booklet;

>L:={seq(i^2, i=1..5)};
                     L := {1, 4, 9, 16, 25}

>nops(L);
                               5
>L[3];
                               9
>type(L,list);
                             false

>convert(L,list);
                       [1, 4, 9, 16, 25]

>sum(i^5, i=1..5);
                              4425

>sum(i^2, i=1..n);
               1        3   1        2   1     1
               - (n + 1)  - - (n + 1)  + - n + -
               3            2            6     6

>factor(%);
                     1                    
                     - n (n + 1) (2 n + 1)
                     6                    
>y:=1/sqrt(1-x);
                                 1      
                       y := ------------
                                   (1/2)
                            (1 - x)     

>taylor(y,x=0,5);
                1     3  2   5   3   35   4    / 5\
            1 + - x + - x  + -- x  + --- x  + O\x /
                2     8      16      128           


# Question 3: 
## Part I: Write a procedure Bij(pi);

>Bij:=proc(pi):
>local i,n,pi1:
>n:=nops(pi):
>for i from 1 to n do
>if pi[i]=n then
>pi1:=[op(1..i-1,pi),op(i+1..n,pi)]:
>RETURN([i,pi1]):
>fi:
>od:
>end proc;

>Bij([3,1,4,6,2,5]);
                      [4, [3, 1, 4, 2, 5]]



## Part II: Write a procedure InvBij(Pair);

>InvBij:=proc(i,pi1):
>local n,pi:
>n:=nops(pi1)+1:
>pi:=[op(1..i-1,pi1),n,op(i..n-1,pi1)]:
>pi:
>end proc;

>InvBij(4,[3,1,4,2,5]);
                       [3, 1, 4, 6, 2, 5]

# Question 4: Convince yourself that Bij and InvBij are inverses of each other and hence the sets permute(n) and {1, ...,n} x permute(n-1) are in bijection and hence we have a rigorous proof that if a(n) is the number of permutations of {1, ...,n} we have the recurrence
a(n)=n*a(n-1);

#Ans: 

From the previous question we have the following procedures 

>Bij: permute(n) -----> {1, ...,n} x permute(n-1), where 

                            Bij(pi)=[i,pi1]      

and   >InvBij: {1, ...,n} x permute(n-1) -----> permute(n) , where
    
                           InvBij([i,pi1])=pi

>pi is from permute(n) and [i,pi1] from {1, ...,n} x permute(n-1).

Let  [i,pi1] from {1, ...,n} x permute(n-1), then 

                      Bij(InvBij([i,pi1])=Bij(pi)=[i,pi1]

Similarly, let pi from permute(n), then 

                     InvBij(Bij(pi)=InvBij([i,pi1])=pi

Hence, Bij and InvBij are inverses of each other.

Therefore, Bij and InvBij define bijection between the sets permute(n) and {1, ...,n} x permute(n-1), by properties of bijection and Cartesian product  

                  |permute(n)|=|{1, ...,n}|.|permute(n-1)| ----------(1)

where |{1, ...,n}| = n, and a(n) is the number of permutations of {1, ...,n} = |permute(n)|
 
and a(n-1) is the number of permutations of {1, ...,n-1} = |permute(n-1)|

therefore, (1) implies that a(n) = n a(n-1)
This completes the proof of the recurrence.