walkccc / CLRS

📚 Solutions to Introduction to Algorithms Third Edition
https://walkccc.me/CLRS
MIT License
4.63k stars 1.26k forks source link

Update 5.4.md #463

Closed runebone closed 1 year ago

runebone commented 1 year ago

$$ Pr(k-perm\ in\ n) = \frac{n}{n} \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \dots \frac{n-k+1}{n} $$

$$ Pr(k-perm\ in\ n) = \frac{\frac{n!}{(n-k)!}}{n^k} = \frac{n!}{n^k (n-k)!} $$

Which is indeed the complementary event to the birthday problem. You can check https://en.wikipedia.org/wiki/Birthday_problem

walkccc commented 1 year ago

Thanks!