Partitions and Multinomial Coefficients

Definition

Suppose we have an $n$ -element set which can be partitioned into $r$ disjoint subsets, with the $i$ -th subset containing $n$ elements

This is similar to having $n$ objects, of which $n_{1}$ are alike $n_{2}$ are alike $\dots n_{r}$ are alike.

The number of permutations of the $n$ -element set to form this configuration is given by:

\frac{n !}{n _{1} ! n _{2} ! \dots n _{r} !}

These are also called multinomial coefficients

Ex: Signals

How many different signals, each consisting of 9 flags hung in a line, can be made from a set of 4 white flags, 3 red flags, and 2 blue flags, if all flags of the same color are identical?

Answer:

\frac{9 !}{4 ! 3 ! 2 !} = 1260

Occupancy Problems (Boxes and Objects)

Distinguishable Objects and Distinguishable Boxes

The number of ways of distributing $n$ distinguishable objects into $r$ distinguishable boxes so that $n_{i}$ objects are placed into box $i$ , for $i = 1, 2, \dots, r$ is:

(n _{1} , n _{2} , \dots , n _{r} n) = \frac{n !}{n _{1} ! n _{2} ! \dots n _{r} !}

Indistinguishable Objects and Distinguishable Boxes

Every box gets an object

Suppose we want to distribute $n$ indistinguishable objects into $k$ boxes so that every box gets at least one object

If $x_{i}$ is the number of objects going into box $i$ , we are looking for the number of solutions to:

x_{1} + x_{2} + \dots + x_{k} = n, where x_{i} > 0

If we express this as bars and stars, you want to place $k - 1$ bars in $n - 1$ spaces, so this can be expressed as:

(k - 1 n - 1)

This is just regular combinations.

Not every box gets an object

Suppose we want to distribute $n$ indistinguishable objects into $k$ boxes so that every box may or may not get an object

If $x_{i}$ is the number of objects going into box $i$ , we are looking for the number of solutions as the sum of $k$ non-negative integers:

x_{1} + x_{2} + \dots + x_{k} = n, where x_{i} \geq 0

The number of ways we can do this can be expressed as:

(k - 1 n + k - 1)

Notes

Explorer