Back to course

Advanced Counting Techniques

Permutations and combinations handle "choose kk from nn". Four further patterns cover most of what they cannot, and each has a recognisable signature.

Multinomial coefficients: splitting into several groups

When nn items are divided into groups of sizes k1,…,krk_1, \ldots, k_r with ∑ki=n\sum k_i = n:

The multinomial coefficient
(nk1,k2,…,kr)=n!k1! k2!⋯kr!\binom{n}{k_1, k_2, \ldots, k_r} = \frac{n!}{k_1!\,k_2! \cdots k_r!}

Arrangements of n items into labelled groups, dividing out the orderings you cannot tell apart.

The binomial coefficient is the two-group case. The classic use is counting arrangements of a word with repeated letters: the number of distinct orderings of BANANA is

6!1! 3! 2!=72012=60\frac{6!}{1!\,3!\,2!} = \frac{720}{12} = 60

with the denominator removing the orderings that merely permute identical letters.

Signature: items are dealt into named groups, or a sequence has repeated indistinguishable elements.

The rest of this lesson is for subscribers

Unlock every lesson in Fundamentals of Probability and Statistics, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Continue
NextConditional Probability

Keep reading Fundamentals of Probability and Statistics

41 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them