Number of Permutations/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set of $n$ elements.

Let $r \in \N: r \le n$.


The number of $r$-permutations of $S$ is:

${}^n P_r = \dfrac {n!} {\paren {n - r}!}$


Using the falling factorial symbol, this can also be expressed:

${}^n P_r = n^{\underline r}$


Proof

We pick the elements of $S$ in any arbitrary order.

There are $n$ elements of $S$, so there are $n$ options for the first element.

Then there are $n - 1$ elements left in $S$ that we haven't picked, so there are $n-1$ options for the second element.

Then there are $n - 2$ elements left, so there are $n - 2$ options for the third element.

And so on, to the $r$th element of our selection: we now have $n - \paren {r - 1}$ possible choices.

Each mapping is independent of the choices made for all the other mappings, so by the Product Rule for Counting, the total number of ordered selections from $S$:

\(\ds {}^n P_r\) \(=\) \(\ds n \paren {n - 1} \paren {n - 2} \cdots \paren {n - r + 1}\)
\(\ds \) \(=\) \(\ds n \paren {n - 1} \paren {n - 2} \ldots \paren {n - r + 1} \dfrac {\paren {n - r}!} {\paren {n - r}!}\) multiplying top and bottom by $\paren {n - r}!$
\(\ds \) \(=\) \(\ds \dfrac {n!} {\paren {n - r}!}\) simplifying the numerator

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Number_of_Permutations/Proof_1&oldid=596139"