Applications of Permutation and Combination

Functional Applications

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

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

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

The number of functions from A to B is n^m.
The number of one-one functions from A to B is ⁿP_m, m ≤ n.
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.
The number of increasing (decreasing) functions from A to B is \(\left( \begin{align}& n \\ & m \\ \end{align} \right)\), m ≤ n.
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.
The number of bijections from A to B is n! if m = n.
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 (x_i) ≠ y_i, 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 ⁿC₂.
The number of straight lines passing through n points = ⁿC₂.
The number of straight lines passing through n points out of which m are collinear ⁿC₂ – ^mC₂ + 1.
In a polygon, the total number of diagonals out of n points (no three points are collinear) = ⁿC₂ – n = n(n-3)/ 2.
Number of triangles formed by joining n points is ⁿC₃.
Number of triangles formed by joining n points out of which m are collinear are ⁿC₃ – ^mC₃.
The number of parallelogram in two systems of parallel lines (when 1^st set contains m parallel lines and 2^nd set contains n parallel lines) = ⁿC₂ 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}}}\).