# Applications of Permutation and Combination

### Applications of Permutation and Combination

Functional Applications

(i) The number of all permutations (arrangements) of n different objects taken r at a time,

1. When a particular object is to be always included in each arrangement is n-1Cr-1 x r!
2. When a particular object is never taken in each arrangement is n-1Cr x r!

(ii) If the sets A has m elements and B has n elements, then

1. The number of functions from A to B is nm.
2. The number of one-one functions from A to B is nPm, m ≤ n.
3. The number of onto functions from A to B is $${{n}^{m}}\,-\,\left( \begin{matrix} n \\ 1 \\\end{matrix} \right){{\left( n-1 \right)}^{m}}+\left( \begin{matrix} n \\ 2 \\\end{matrix} \right){{\left( n-2 \right)}^{m}}-\,…$$, m≤ n.
4. The number of increasing (decreasing) functions from A to B is \left( \begin{align}& n \\ & m \\ \end{align} \right), m ≤ n.
5. The number of non-decreasing (non-increasing) functions from A to B is \left( \begin{align}& m+n-1 \\ & \,\,\,\,\,\,m \\ \end{align} \right), m ≤ n.
6. The number of bijections from A to B is n! if m = n.
7. The number of bijections from A to A such that f(x) ≠ x, ” x ϵ A, is $$m!\left[ \frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-….+\frac{{{(-1)}^{m}}}{m!} \right]$$.

Example: Let A = {x₁, x₂, x₃, x₄, x₅}, B = {y₁, y₂, y₃, y₄, y₅}. Then, the number of one-one mappings, from A to B such that f (xi) ≠ yi, i = 1, 2, …, 5 is

Interpret: Here, we use the formula, the number of bijections from A to A such that f (x) ≠ x, ” x ϵ A is $$m!\left[ \frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}-…..+\frac{{{(-1)}^{m}}}{m!} \right]$$

Here required number of ways $$=5!\left( \frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!} \right)$$

$$=120\left( \frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120} \right)$$

$$=120\left( \frac{60-20+5-1}{120} \right)=44$$.

Geometrical Applications:

• Out of n non-concurrent and non-parallel straight lines the number of point of intersection are nC₂.
• The number of straight lines passing through n points = nC₂.
• The number of straight lines passing through n points out of which m are collinear nC₂ – mC₂ + 1.
• In a polygon, the total number of diagonals out of n points (no three points are collinear) = nC₂ – n = n(n-3)/ 2.
• Number of triangles formed by joining n points is nC₃.
• Number of triangles formed by joining n points out of which m are collinear are nC₃ – mC₃.
• The number of parallelogram in two systems of parallel lines (when 1st set contains m parallel lines and 2nd set contains n parallel lines) = nC₂ x mC₂.
• The number of rectangles of any size in a square of n x n is $$\sum\limits_{r\,\,=\,\,1}^{n}{{{r}^{3}}}$$ and number of squares of any size is $$\sum\limits_{r\,\,=\,\,1}^{n}{{{n}^{2}}}$$.