Permutation and Combination

 Permutation and Combination

Permutation and combination are both concepts in mathematics that deal with counting and arranging elements in a set.

Permutation refers to the arrangement of objects in a specific order, where the order of the objects matters. For example, the number of ways that 3 different books can be arranged on a shelf is a permutation problem. The first book can be any of the three books, the second can be either of the remaining two, and the third can be the last book. Therefore, there are 3 x 2 x 1 = 6 different ways the books can be arranged.

The formula for calculating the number of permutations of n objects taken r at a time is given by:

nPr = n! / (n-r)!

where n! represents n factorial, which is the product of all positive integers up to and including n.

Combination, on the other hand, refers to the selection of objects from a set without regard to the order in which they are selected. For example, the number of ways to choose 2 out of 5 different colored balls from a bag is a combination problem. The order in which the balls are selected doesn't matter, so we can use the formula for combinations to calculate the number of ways to do this.

The formula for calculating the number of combinations of n objects taken r at a time is given by:

nCr = n! / (r! (n-r)!)

where r! represents r factorial.

In general, permutation problems involve arrangements where order matters, while combination problems involve selections where order doesn't matter.

Theorem 1: (Without repetition in partial permutation)

The total number of permutation of a set of n objects taken r at a time is given by 

P(n,r)= n(n-1)(n-2).......(n-r+1).     (n ≥ r)

Proof: The number of permutations of a set of n objects taken r at a time is equivalent to the number of ways in which r positions can be filled by n objects. When first object is filled, we have (n-1) choices to fill up the second position. Similarly, there are (n-2) choices to fill up the third position and so on. Ultimately to fill up the r^th position, there are n-(r-1) = (n-r+1) choices. Then, by basic principle of counting, total number of ways= n(n-1)(n-2)....(n-r+1).

=n(n-1)(n-2).....(n-r+1)(n-r).....3.2.1 / (n-r)...3.2.1

= n!/ (n-r)!

Types of Permutations 

The permutation of a object taken all at a time when P of the objects are of first kind, q of them are of second kind , of them are of third kind and the rest all are different.

The total no. of Permutations=n!/p!q!r!

1. Circular Permutation: Circular permutation refers to a type of permutation where the order of objects arranged in a circular shape is important. In a circular permutation, the objects are arranged in a circular shape, and each arrangement is considered unique if the order of the objects is different, even if the objects themselves are the same.

For example, imagine there are four people sitting at a round table. If they change seats while remaining seated, this would be considered a circular permutation. There are different ways that the four people can be arranged, and each arrangement is considered unique.

The formula for the number of possible arrangements in a circular permutation is (n-1)!, where n is the number of objects being arranged. This is because, in a circular permutation, the first object can be fixed in place, and the remaining objects can be arranged in (n-1)! ways.

For example, if there are 5 people sitting at a round table, the number of possible arrangements is (5-1)! = 4! = 24. This means that there are 24 unique ways that the 5 people can be arranged around the table.

2. Linear Permutation: A linear permutation is a permutation of a set of elements where each element is mapped to a unique image under the permutation. In other words, a linear permutation is a one-to-one and onto function that reorders the elements of the set.

For example, suppose we have the set {1, 2, 3, 4}. A linear permutation of this set might be:

{2, 4, 1, 3}

This is a linear permutation because each element of the original set is mapped to a unique image in the new set, and every element in the new set has a preimage in the original set.

Permutation of repeated things 

The permutation of the n objects taken r at a time when each occur number of times and its is given by P= n^r

Combinations

Combinations means collection of an object without regarding the order of arrangement. The total number of combinations of n objects taken r at a time C(n,r) is given by C(n,r)= n!/ (n-r)!r!

Note:

1. n

       Cr= n

                Cn-r

2. n

       Cn-r= n+1

                         Cr