Number of Permutations of One Less
Jump to navigation
Jump to search
Theorem
- ${}^{n - 1} P_n = {}^n P_n$
where ${}^k P_n$ denotes the number of ordered selections of $k$ objects from $n$.
Proof 1
\(\ds {}^{n - 1} P_n\) | \(=\) | \(\ds \dfrac {n!} {\paren {n - \paren {n - 1} }!}\) | Number of Permutations | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {n!} {1!}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds n!\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds {}^n P_n\) | Number of Permutations |
$\blacksquare$
Proof 2
\(\ds {}^{n - 1} P_n\) | \(=\) | \(\ds n^{\underline {n - 1} }\) | Number of Permutations: $n^{\underline {n - 1} }$ denotes Falling Factorial | |||||||||||
\(\ds \) | \(=\) | \(\ds n!\) | Integer to Power of Itself Less One Falling is Factorial | |||||||||||
\(\ds \) | \(=\) | \(\ds {}^n P_n\) | Number of Permutations |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.5$: Permutations and Factorials: Exercise $2$