scratch

§ Counting with Repetitions via Pure Binomial Coefficients

created 2022-01-28 · last edited 2022-05-30
  • If we want to place nnn things where aaa of them are of kind a, bbb are of kind b, cccof them are kind ccc. the usual formula is n!/(a!b!c!)n!/(a!b!c!)n!/(a!b!c!).
  • An alternative way to count this is to think of it as first picking aaa slots from nnn, and then picking bbb slots from the leftover (n−a)(n - a)(n−a) elements, and finally picking ccc slots from (n−a−b)(n - a - b)(n−a−b). This becomes (na)(n−ab)(n−a−bc)\binom{n}{a}\binom{n-a}{b}\binom{n - a - b}{c}(an​)(bn−a​)(cn−a−b​).
  • This is equal to n!/a!(n−a)!⋅(n−a)!/n!(n−a−b)!⋅(n−a−b)!/c!0!n!/a!(n -a)! \cdot (n-a)!/n!(n - a - b)! \cdot (n - a - b)! / c!0!n!/a!(n−a)!⋅(n−a)!/n!(n−a−b)!⋅(n−a−b)!/c!0!, which is equal to the usual n!/a!b!c!n!/a!b!c!n!/a!b!c! by cancelling and setting c=n−a−bc = n - a - bc=n−a−b.
  • Generalization is immediate.
❦
Newer ৪ Blog ৪ Older