Partition, Sieve Method and Stirling Number

Partition: Distinguishability

We're interested in the question: how many ways to give out candies to kids?
The answers will vary depending on whether the kids and the candies are distinguishable. To get a feel for what we mean by distinguishability, see Art of Problem Solving video.

We've made a nice little table to keep track of different scenarios. (D for distinguishable, and I for indistinguishable)

Kids D I Candies D $S(n,k)k!$ (1) $S(n,k)$ (2) I $\binom{n-1}{k-1}$ (3) $p_k(n)$ (4) n candy bars to k kids such that every kid receives at least one candy bar.

Play with it to make sure you understand the difference between different scenarios. For example, (# of ball in box 1, # of balls in box 2) = $(2,3)$ will be considered the same as $(3,2)$ in scenario (4). Meanwhile, $(2,3)$ is different from $(3,2)$ in scenario (3). 

Scenario (3) is arguably the easiest one, so we will handle it first. We will solve it using a handy trick called "Ball and Urn". 

Instead of giving out candies to kids, we consider the identical question of how many ways to put $n$ identical balls into $k$ different boxes. First, align all the $n$ balls in a straight line. We need to choose $k-1$ spaces to put the walls that separate different boxes. And there are $n-1$ spaces in between the balls to choose from. So we have $\displaystyle \binom{n-1}{k-1}$ ways to arrange in scenario (3). Note that this is also the number of solutions to the equation $\displaystyle x_1+x_2+...+x_k=n$.

Scenario (4) is quite difficult, so forget about it!

In scenarios (1) and (2), we introduce a new notation $S(n,k)$, which is the Stirling number of second kind. The definition of $S(n,k)$ is precisely the scenario (2) described. $S(n,k)$ denotes the number of ways to distribute $n$ distinct balls to $k$ identical boxes. Because the balls are distinct, we can ascribe a number from $1$ through $n$ to each of the balls. $S(n,k)$ then becomes the number of ways to partition the set $\{1,2,3,...,n\}$ into $k$ subsets. 

For example, $S(3,2)$ is the number of ways to partition $\{1,2,3\}$ (three distinct balls) into $2$ parts. $S(3,2)=3$. Namely, $\{1,2\}$ and $\{3\}$ is the first way, $\{1,3\}$ and $\{2\}$ is the second way, and $\{2,3\}$ and $\{1\}$ is the last way. 

Note that scenario (1) is just an extension of (2). If the boxes are now also distinct, we multiply $S(n,k)$ with the number of ways to permute the $k$ boxes, which is $k!$. So, {1,2} & {3}, and {3} & {1,2} are now considered different, because in the former case 1,2 are in the red box while they are in the blue box in latter case. 

In scenario (1), we can ascribe a number from $1$ through $n$ to each of the balls, and from $1$ through $k$ to each of the boxes.  Then we can think of (1) in terms of a surjective function. A function is a mapping from a set $X$ to a set $Y$. In this case, set $X$ is {1,2,..,n} and $Y$ is {1,2,...,k}. A map 1,2 $\to$ 3 says that we put balls numbered 1 and 2 to box numbered 3. A function is surjective if all the elements in set $Y$ are linked to at least one element in set $X$. That is each box contains at least one balls. This provide an alternative way to visualize scenario (1) in terms of function. 

Figure 1 (click at the image to zoom in)

But to obtain a formula for the Stirling number, we need to introduce a powerful method: Exclusion-Inclusion.

Sieve Method: exclusion-inclusion

Motivating question: In a kindergarten school, 24 kids participate in the ballet team, 17 kids in the wrestling team and 8 in both. How many kids participate in either the ballet or the wrestling team?

The venn diagram comes to the rescue

Figure 2

There are some new notations. $B \cap W$ means both B and W, while $B \cup W$ means either B or W. $W^c$ means not in $W$, with c being a shorthand for complement. Lastly, $ \mid B \mid $ means the number of kids in group B. (The notations are quite confusing to me at first, so I make up my own notations. So if you're like me, do the same!)

The number of kids that play either ballet or wrestling equals the sum of the number of kids that play ballet alone, the number of kids that play wrestling alone and the number of them that play both.

Or we can count $ \mid B \cup W \mid  =  \mid B  \mid + \mid W  \mid -\mid B \cap W  \mid$. We subtract $\mid B \cap W  \mid$, because the sum of $\mid B \mid$ and $\mid W \mid$ counts the region 2 twice.

A more complicated example involves three categories (three circles).

We find that$\mid A \cup B \cup C \mid=$

$\mid A \mid +  \mid B \mid +  \mid C \mid - (\mid A \cap B \mid + \mid A \cap C \mid + \mid B \cap C \mid ) + \mid A \cap B \cap C \mid (*)$.

To arrive at (*), we can think of $ A \cup B $ as one big group, and C as one group. So we refer back to figure 2, and replace B by $ A \cup B$ and W by C. We have:

 $ \mid (A \cup B) \cup C \mid = \mid A \cup B \mid + \mid C \mid - \mid (A \cup B) \cap C \mid$.

We already know what $\mid A \cup B \mid$ is. So we only need to concern ourselves with the last term. $\mid (A \cup B) \cap C \mid $ asks for the number of kids in team A or B who are also in team C. It's the number of kid in team C and A or in team C and B. So $\mid (A \cup B) \cap C \mid = \mid (C \cap A) \cup (C \cap B) \mid$. Consider $C \cap A$ as one group, and $C \cap B$ as another, and we know how to compute $\mid (C \cap A) \cup (C \cap B) \mid$ by figure 2.

This suggests a general form $\mid A_1 \cup ... A_n \mid =$

$ (\mid A_1\mid+ \mid A_2 \mid +... + \mid A_n \mid)$  -  $(\mid A_1 \cap A_2 \mid +... + \mid A_{n-1} \cap A_{n}\mid)$ + $(\mid A_1 \cap A_2 \cap A_3\mid + ....)$ - $.... $ + $(-1)^{n+1}\mid A_1 \cap ... \cap A_n \mid$.

Warming: don't just stare at the formula, it can be a mess at first. Try a few small examples, like $n=3$ or $n=4$ to get a feel for what the formula is actually saying. 

The sieve method kinda works in the same way. You tries to correctly count something, but you know combinatorics doesn't work that way. So you over-count and then correct for it by subtracting.

The generalized formula above can be easily proven by induction on $n$. 

We're now ready to compute the Stirling number.

Stirling Number of Second Kind

Instead of directly computing $S(n,k)$, we will compute $S(n,k)k!$, i.e. the number of surjective functions from {1,2, ...,n} to {1,2,..,k} in scenario 1.

Being surjective is key here. We will count the number of surjective functions by subtracting the number of non-surjective functions from the number of all functions. First, the number of all functions is $k^n$, because each element in $X$ can go to any of the $k$ elements in $Y$, and it's okay to have empty boxes. Non-surjective function will be the arrangement that has at least one empty box. Let $A_i$ be the arrangement that leaves box numbered i empty. We have the number of non-surjective functions equal to $\mid A_1 \cup A_2 ... \cup A_k \mid$. That is either box 1 empty or box 2 empty or ... or box k empty.

For connivence, let {1,2,...,n} be $[n]$. Note that $\mid A_i \cap A_j ... \cap A_k \mid $ which involves $m$ A's means that $m$ boxes specified must be empty. The $k-m$ boxes left can take balls in any manner. In other words, $\mid A_i \cap A_j ... \cap A_k \mid $ equals the number of all functions from $[n]$ to $[k-m]$. We have full freedom to do whatever we want with the remaining boxes as long as we keep the $m$ boxes specified empty. The number of such functions is $(k-m)^n$.

Figure 3

Now there are $\displaystyle \binom{k}{m}$ terms in the sum $\mid A_1 \cap A_2 ... \cap A_m \mid + \mid A_2 ... \cap A_{m+1} \mid + ... (**)$ in the sieve formula. Each of the term that involves the intersection (the symbol $\cap$) of $m$ boxes are all equal to $(k-m)^n$. So (**) equals to $\displaystyle \binom{k}{m}(k-m)^n $.

Applying the sieve formula, we have the number of surjective functions is (# of all functions) - (# of non-surjective functions) $\displaystyle = S(n,k)k!= k^n - \mid A_1 \cup A_2 ... \cup A_k \mid = k^n - \sum_{m=1}^k(-1)^{m-1}\binom{k}{m}(k-m)^n$.

So, $S(n,k) = \displaystyle \frac{1}{k!} \sum_{m=0}^k (-1)^m \binom{k}{m} (k-m)^n$.