Permutation and Combination

 

Motivation :

                         If we have 6 different objects,  we would like to put 3 of them in 3

                         different containers labeled as 1, 2, 3.  How many possible results will be

                         shown ?

 

                                       

                         This problem can be considered in this way.  For the first container,  we

                         can choose 1 between 6 objects and put that chosen one into the first

                         container.  There are 6 possible results when we decide to choose the first

                         one.   Once that is determined, we have 5 left.

 

                          For the second one, we have 5 choices.  Similarly for the third one, we

                          have 4 choices.

 

                          Of course, it will not be necessary to place the object from the container

                          labeled as 1; no matter which one we start to put the object, the result

                          should be the same because we only care about the final result.

 

                          Thus,  there are 6  5  4= 120 possible outcomes.

 

                          We would like to consider the problems in more general way.

 

                          Let’s say we have n objects and we would like to put some of them into r

                          different places; each place only contains 1 object.   The number of

                          possible results is

 

                                         n  (n-1)  (n-r+1)

 

                          This notation is lengthy.   The following representation make the

                          statement concise:

                                           n! = 1  2  3  4  n

                           Then

                                             =  n  (n-1)  (n-r+1)

 

                           And we denote      as  P(n,r), namely,  “r-permutation of n symbols”

 

Definition ( Permutation )

                   The symbol  P(n,r) is defined as

                                        P(n,r) = 

                     Where   k! is defined as   1  2  3  4  k  for  k>0;  and  “0!” is defined as 1.

                  

                   P(n,r) can be considered as the number of possible outcomes for arranging r

                   objects in an order from n objects.

 

 

 

Question ( Combination ) :  

                        Given 6 distinct objects,  we only want to choose 3 of them. How many possible outcomes we can get ?

 

                         The question can be solved easily if we follow the previous result we have.  If  the answer to the problem for placing the objects into 3 containers from 6 objects is

                                                   P(6,3) =  

 

            For choosing 3 from 6, it means we do not care which objects is arranged into which container.    Let’s say we want to choose 3 letters from A, B, C, D, E, F.  If A, B, and C are selected,  we do not care if  they are arranged as ABC or ACB or BCA; we only care the letters we choose.  Thus, all the possible orders should be considered as 1 outcome.   For 3 containers, it will generate  “3!” possible outcomes.

 

            Hence, the number of possible outcomes for choosing 3 from 6 is

 

                                                       =

 

            In general, to choose r objects from n objects, the number of possible outcomes is

 

                                                       =

 

 

 

 Definition ( Combination )

                           The symbol  C(n,r ) is defined as

 

                                      C(n,r) =   =  .  

 

                          And we read it as “n-choose-r”.  Sometimes, it is denoted as

                                                        or        .

 

                          C(n,r) can be considered as the number of possible outcomes to choose

                          r objects from n objects.

 

 

Theorem ( Binomial )

                (x+y)ⁿ = xⁿ + C(n,1)x^n-1y + C(n,2)x^n-2y² + … + C(n,n-1)xy^n-1 + yⁿ

 

   Proof:

                    (x+y)ⁿ =   

 

                For the coefficient of xⁿ ,  there is only one choice to multiply the x from each (x+y)  in order to generate xⁿ  .  Thus,  the coefficient of xⁿ is 1 .

 

 

                For the coefficient of x^n-1y,   if one term contributes y, then the rest (n-1) terms will contribute x in order to generate x^n-1y .   There are  C(n,1)  choices for such arrangement.  Thus, the coefficient of  x^n-1y  is  C(n,1) .

 

 

 

                Similarly, the coefficient of  x^n-iyⁱ  is  C(n,i) .