Exercise 5.4.5

$\star$ What is the probability that a $k$-string over a set of size $n$ forms a $k$-permutation? How does this question relate to the birthday paradox?

$$ \Pr\{k\text{-perm in }n\} = 1 \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdots \frac{n-k+1}{n} = \frac{(n-1)!}{(n-k)!n^k} $$

This is the complementary event to the birthday problem, that is, the chance of $k$ people have distinct birthdays.