Counting Principles - Examples and Constructions

Advanced counting problems often require combining multiple principles and handling special conditions such as repetition, restrictions, or multi-stage selection processes. These examples illustrate systematic approaches to complex counting scenarios.

ExamplePermutations with Repetition

How many distinct arrangements are there of the letters in the word MISSISSIPPI?

The word has 11 letters: 1 M, 4 I's, 4 S's, and 2 P's. If all letters were distinct, there would be $11!$ arrangements. However, we must account for indistinguishable letters. The number of distinct arrangements is: $\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39,916,800}{1 \cdot 24 \cdot 24 \cdot 2} = 34,650$

This formula generalizes: if we have $n$ objects where $n_1$ are of type 1, $n_2$ are of type 2, ..., and $n_k$ are of type $k$ , then the number of distinct arrangements is $\frac{n!}{n_1! \cdot n_2! \cdots n_k!}$ . These are called multinomial coefficients.

ExampleDistributing Indistinguishable Objects

How many ways can we distribute 10 identical balls into 4 distinct boxes?

This is a classic "stars and bars" problem. We need to find the number of non-negative integer solutions to $x_1 + x_2 + x_3 + x_4 = 10$ . Using the stars and bars method, we arrange 10 stars (balls) and 3 bars (dividers) to create 4 groups: $\binom{10 + 4 - 1}{4 - 1} = \binom{13}{3} = 286$

Generally, distributing $n$ identical objects into $k$ distinct boxes has $\binom{n+k-1}{k-1}$ solutions.

ExampleCounting with Restrictions

A committee of 5 people is to be chosen from 6 men and 8 women. How many committees can be formed if there must be at least 2 women?

We use complementary counting. The total number of committees without restrictions is $\binom{14}{5}$ . We subtract committees with 0 or 1 women: $\binom{14}{5} - \binom{6}{5}\binom{8}{0} - \binom{6}{4}\binom{8}{1}$ $= 2002 - 6 \cdot 1 - 15 \cdot 8 = 2002 - 6 - 120 = 1876$

Alternatively, we can count directly by cases (2, 3, or 4 women): $\binom{8}{2}\binom{6}{3} + \binom{8}{3}\binom{6}{2} + \binom{8}{4}\binom{6}{1} + \binom{8}{5}\binom{6}{0} = 560 + 840 + 420 + 56 = 1876$ .

DefinitionDerangements

A derangement is a permutation where no element appears in its original position. The number of derangements of $n$ objects, denoted $D_n$ or $!n$ , is given by: $D_n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!} = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$

Remarkably, $D_n$ is the nearest integer to $\frac{n!}{e}$ , and the probability that a random permutation is a derangement approaches $\frac{1}{e} \approx 0.368$ as $n \to \infty$ .

Remark

Many counting problems involve circular arrangements, where rotations are considered identical. For $n$ distinct objects, there are $\frac{n!}{n} = (n-1)!$ distinct circular arrangements. If reflections are also considered identical (as with a necklace that can be flipped), the count becomes $\frac{(n-1)!}{2}$ for $n \geq 3$ . These considerations lead to Burnside's lemma and Pólya enumeration theorem in more advanced combinatorics.

These examples demonstrate how fundamental counting principles extend to handle complex scenarios encountered in practical applications.