Permutations and Combinations

Permutations

Definition: An ordered arrangement of $r$ objects from a set $A$ containing $n$ objects $(0 < r \leq n)$ is called an \textbf{r-element permutation} of $A$ , or a permutation of the elements of $A$ taken $r$ at a time. The number of $r$ -element permutations of a set containing $n$ objects is denoted by $_nP_r$ which is given by

$_nP_r = \frac{n!}{(n - r)!}.$

Example:
Suppose that two anthropology, four computer science, three statistics and three biology books are randomly put on a shelf, what is the probability that the books of the same subject are put together?
Solution: If the books are grouped together there are $2!$ ways to order the anthropology books, $4!$ ways to order the computer science books, $3!$ ways for the statistics books and $3!$ for the biology books. So there are $2! \times 4! \times 3! \times 3!$ arrangements with the books ordered by anthropology, comp sci, statistics and then biology. There are then $4!$ ways to order the subjects. So there are $4! \times 2! \times 4! \times 3! \times 3!$ total ways to arrange the books with the desired properties. There are $12!$ ways to randomly order 12 books. So the probability of an arrangement we are looking for is

$\frac{4! \times 2! \times 4! \times 3! \times 3!}{12!} = 0.00008 .$

Theorem: The number of distinguishable permutations of $n$ objects of $k$ different types, where $n_1$ are alike, $n_2$ are alike, …, $n_k$ are alike and $n = n_1 + n_2 +...+n_k$ , is

$\frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}$

Example:
How many different 10-letter codes can be made using three a’s, four b’s and three c’s?
Solution: Using the above theorem the number of different codes is

$\frac{10!}{3!4!3!} = 4200.$

Combinations:

Definition: An unordered arrangement of $r$ objects from a set $A$ containing $n$ objects $(r \leq n)$ is called an \textbf{ $r$ -element combination} of $A$ , or a combination of the elements of $A$ taken $r$ at a time. The number of $r$ -element combinations of $n$ objects is given by

$_nC_r = \binom{n}{r} = \frac{n!}{r!(n - r)!}$

Example:
From a deck of 52 cards, seven cards are drawn at random and without replacement, what is the probability that at least one of the cards is a king?

Solution: If we let $A$ be the event that there is at least one king in the set of cards. If we were to try to count all the possible ways that this could occur it would be rather complicated, so instead we look at $A^c$ , which is the event that no kings occur. This event is significantly easier to quantify. Since no kings occur there are $\binom{48}{7}$ or 48 choose 7 ways of choosing seven cards that aren’t a king. Since there are $\binom{52}{7}$ ways of choosing seven cards. So

$\begin{align*} p(A) = 1 - p(A^c) &= 1 - \frac{\binom{48}{7}}{\binom{52}{7}} \\ &= 1 - \left( \frac{48!}{7!41!} \right)\left( \frac{7!45!}{52!} \right) \\ &= 1 - \left( \frac{48!45!}{41!52!} \right) \\ &= 1 - \left( \frac{45*44*43*42}{52*51*50*49} \right) \\ &\approx 1 - 0.55 = .45 \end{align*}$

Theorem: [Binomial Expansion] For any integer $n\geq 0$ ,

$(x + y)^n = \sum_{i = 0}^{n}\binom{n}{i}x^{n-i}y^{i}$

Example:
Calculate $(x + y)^ 4$ .

Solution: We first see that the different ways that the powers of the variables can be arranged is $x^4, x^3y,x^2y^xy^3,y^4$ , so from the above theorem,

$\begin{align*} (x + y)^4 &= \binom{4}{0}x^4 + \binom{4}{1} x^3y + \binom{4}{2}x^2y^2 + \binom{4}{3}xy^3 + \binom{4}{4}y^4 \\ &= x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4 \end{align*}$

Theorem:[Multinomial Expansion]In the expansion of

$(x_1 + x_2 + ... + x_k)^n$

the coefficient of the term $x_1^{n_1}x_2^{n_2}...x_{k}^{n_k}$ , $n_1 + n_2 +...+n_k = n,$ is

$\frac{n!}{n_1!n_2!...n_k!}$

So we have,

$(x_1 + x_2 + ... +x_k)^n = \sum_{n_1+n_2+...+n_k = n} \frac{n!}{n_1!n_2!...n_k!}x_1^{n_1}x_2^{n_2}...x_{k}^{n_k}$

Example:
Calculate $(x + y + z)^3$ .\\

Solution:
We as the previous example we find all the ways that we can have variable powers of three,

$x^3,x^2y,x^2z,xyz,xy^2,xz^2,y^3,y^2z,yz^2,z^3$

so from here we apply the above theorem

$\begin{align*} (x + y + z)^3 &= \frac{3!}{3!0!0!}x^3 + \frac{3!}{2!1!0!}x^2y + \frac{3!}{2!0!1!}x^2z + \frac{3!}{1!1!1!}xyz + \frac{3!}{1!2!0!}xy^2 \\ &+ \frac{3!}{1!0!2!}xz^2 + \frac{3!}{0!3!0!}y^3 + \frac{3!}{0!2!1!}y^2z + \frac{3!}{0!1!2!}yz^2 + \frac{3!}{0!0!3!}z^3 \\ &= x^3 + 3x^2y + 3x^2z + 6xyz + 3xy^2 + 3xz^2 + y^3 + 3 y^2z + 3yz^2 + z^3 \end{align*}$

and with a little rearranging, for neatness sake alone

$\begin{align*} &= x^3 + y^3 + z^3 + 3x^2y + 3x^2z + 3xy^2 + 3xz^2 + 3y^2z +3yz^2 + 6xyz \end{align*}$