TAOCP 1.2.5 Exercise 2
By Eq.
Section 1.2.5: Permutations and Factorials
Exercise 2. [**] [10] In the notation of Eq. (2), show that $p_n^{(n-1)} = p_n^{(n)}$, and explain why this happens.
Verified: yes
Solve time: 1m17s
By Eq. (2),
$$ p_{n,n-1}=n(n-1)\cdots 2, $$
since there are $n-1$ factors, beginning with $n$ and ending with $2$. Multiplying these factors gives
$$ p_{n,n-1}=n!. $$
By definition, the number of permutations of $n$ objects is
$$ p_{n,n}=n(n-1)\cdots 2\cdot 1=n!. $$
Hence
$$ p_{n,n-1}=p_{n,n}. $$
This happens because arranging $n-1$ objects chosen from $n$ automatically determines the remaining object. After the first $n-1$ positions have been specified, there is exactly one choice for the last position, namely the unique object not yet used. Therefore each arrangement of $n-1$ selected objects corresponds to exactly one permutation of all $n$ objects. Thus
$$ \boxed{p_{n,n-1}=p_{n,n}=n!}. $$