Distinct Objects into Identical Bins
Distinct objects into identical bins is a problem in combinatorics in which the goal is to count how many distribution of objects into bins are possible such that it does not matter which bin each object go into, but it does matter which objects are grouped together. This problem is often trickier than the related problem of placing distinct objects into distinct bins.
Suppose there are 4 distinct roses which will be placed into 2 identical vases. How many ways can the roses be arranged?
If a rule of product approach is attempted, the question becomes, "Where does the first, second, third, or fourth flower go?" However, this doesn't account for having identical vases, since it doesn't matter if the flowers all went to the first vase or all went to the second vase. In either case, the end result is the same.
Since there is no clear idea on how to proceed, simply list out all the ways. Note that out of the 8 ways in total, 7 of them involve both vases.
\(\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \)
In this wiki, the goal is to understand how one can deal with the general case in a sensible manner. Listing out cases is extremely tedious, and likely to result in double-counting or missing cases. Unlike the counting of distinct objects into distinct bins, which has a simple bijection argument, this process is slightly more involved and will lead you down the path of recursion.
Consider these two cases:
- Distinct objects into identical bins with no empty bin - Stirling numbers of the second kind
- Distinct objects into any number of identical bins - Bell numbers
Contents
Basic Cases of Stirling Numbers of the Second Kind
A Stirling number of the second kind, denoted as \(S(n,r)\) or \(\left\{n \atop r\right\}\), is the number of ways a set of \(n\) elements can be partitioned into \(r\) non-empty sets.
Equivalently, a Stirling number of the second kind can identify how many ways a number of distinct objects can be distributed among identical non-empty bins. In this section, the basic cases for Stirling numbers of the second kind are explored in order to better understand how to solve "distinct objects into identical bins" problems.
Let \(n\) be the number of distinct objects to be distributed among \(r\) identical bins.
Consider these cases in which the number of bins is close to the number of objects:
\(1.~ \text{(Number of bins)} > \text{(Number of objects)}\):
Clearly, since each bin needs at least 1 object, there are not enough objects to go around. Thus, the number of ways to do this is \(0\).\(2.~ \text{(Number of bins)} = \text{(Number of objects)}\):
Clearly, every bin must have exactly 1 object. Since the bins are the same, each bin contains 1 object each, and the order of bins does not matter. Thus, there is only \(1\) way.\(3.~ \text{(Number of bins)} = (\text{Number of objects} - 1)\):
There is one bin which contains 2 objects, and the rest of the bins each will contain 1 object. Hence, it is sufficient to find the number of ways of picking 2 objects and placing those into a bin while the rest will go into an identical bin. Thus, there are \( \binom{n}{2} \) ways of doing this.\(4.~ \text{(Number of bins)} = (\text{Number of objects} - 2)\):
There are 2 "extra" objects to be placed. There are two possible cases:
- 3 objects in one bin: There are \( \binom{n}{3} \) ways to choose the 3 objects to go into this bin.
- 2 objects in one bin, occurring twice: First, there are \(\binom{n}{4}\) ways to pick 4 objects, and then there are \(\binom{4}{2}\div2=3\) ways to place them into 2 bins of 2 objects. Thus, there are \( \binom{n}{4} \times 3\) ways.
Hence, there are \( \binom{n}{3} + 3 \binom{n}{4} \) ways.
This process can continue, but it quickly gets complicated with the number of cases that need to be studied.
Now consider the cases in which the number of bins is small.
\(\text{(Number of bins)} = 1\):
Clearly, if the number of bins is 1, then all of the objects must be in this bin. Hence, there is only \(1\) way to do this.\(\text{(Number of bins)} = 2\):
Consider a slightly different scenario, where there are \(n\) balls in 2 bins. If the bins are not identical, then there are \( 2^ n \) distributions of the balls since each ball can go into either bin. However, two of these distributions involve all of the balls placed into one bin. Hence, there are \( 2^n -2 \) ways in which these balls can be placed into \(2\) non-identical bins such that no bin remains empty.Now consider how to modify this scenario to reflect the bins being identical. Let there be balls \( \mathfrak{B}_1 \) in the first bin and balls \( \mathfrak{B}_2 \) in the second bin. There is an equivalent distribution of having balls \( \mathfrak{B}_2 \) in the first bin and balls \( \mathfrak{B}_1 \) in the second bin. There are \(2\) distributions of distinct objects into distinct bins for every \(1\) distribution of distinct objects into identical bins. Hence, the distributions into identical bins have been double counted, and so the total number would be:
\[ \frac{ 2^n - 2 } { 2 } = 2^{n-1} - 1 .\]
Now that several basic cases have been considered, the strategy moves to how to use these basic cases to develop a recursive relationship that gives \(S(n,r)\) for any \(n\) number of objects and \(r\) number of bins.
General Case of Stirling Numbers of the Second Kind
A summary of the results in the previous section using Stirling notation.
Let there be \(n\) distinct objects to be distributed among \(r\) identical bins.
- \(\quad r > n\):
\(\quad S(n, r ) = 0 \).- \(\quad r = n\):
\(\quad S(n,n) = 1 \).- \(\quad r = n- 1\):
\(\quad S(n, n-1) = { n \choose 2 } \).- \(\quad r = n- 2\):
\(\quad S( n, n-2) = { n \choose 3} + 3 { n \choose 4 } \).- \(\quad r = 1\):
\(\quad S(n,1) = 1 \).- \(\quad r = 2\):
\(\quad S(n,2) = 2^{n-1} - 1 .\)
From these basic cases, any value of \( S(n,r) \) can be calculated through the recurrence relation:
\[ S (n,r) = r S(n-1, r) + S(n-1, r-1). \]
To develop this relation, consider a single object to be fixed, and then consider where the remaining objects go. There are two cases:
- Case 1: The fixed object is in its own bin.
There are \(n-1 \) remaining objects to be distributed into \( r - 1 \) bins, which gives \( S(n-1, r - 1 ) \) distributions for this case.- Case 2: The fixed object is in a bin with other objects.
The remaining \(n-1\) objects are distributed into \( r \) bins, which gives \(S(n-1,r)\) distributions. For each of these distributions, there are \(r\) ways to group the fixed object with the other objects. Thus, there are \( rS ( n-1, r )\) distributions for this case.Summing both cases together yields:
\[ S (n,r) = r S(n-1, r) + S(n-1, r-1).\ _\square\]
The recurrence relation allows one to calculate Stirling numbers of the second kind from basic cases.
How many ways are there to place 5 flowers into 3 bins?
The goal is to find \( S(5, 3 ) \). From the recurrence relation:
\(S(5,3)= 3S(4, 3)+ S(4, 2 ) \)
The values of \(S(4, 3)\) and \(S(4, 2 ) \)can be drawn from the basic cases: \( S(4,3) = { 4 \choose 2 } = 6 \) and \( S(4,2) = 2^{4-1} - 1 = 7 \). Thus,
\[ S(5,3 ) = 3 \times 6 + 7 = 25.\ _\square \]
Now consider an example in which the recurrence relation is used several times.
How many ways are there to place 7 flowers into 4 bins?
The goal is to find \( S(7, 4) \). From the recurrence relation,
\[S(7,4)=4S(6,4)+S(6,3)\]
These values can't be drawn from the basic cases, but the recurrence relation can be used again to calculate them separately.
From the recurrence relation, basic cases, and previous example,
\[ S(6, 4) = 4S(5,4) + S(5, 3) = 4 \times 10 + 25 = 65. \]
Also from the recurrence relation, basic cases, and previous example,
\[ S(6, 3) = 3S(5, 3) + S(5, 2) =3 \times 25 + 15 = 90.\]
Putting this together,
\[ S(7,4) = 4 \times S(6,4) + S(6,3) = 4 \times 65 + 90 = 350. \ _\square \]
These examples show the power of the recurrence relation, which allows one to calculate any value of \(S(n,r)\) from other values of \(S(n,r)\). For reference, here is a list of \( S(n, r) \) for \( n \leq 7 \).
\[ \begin{array} { c | c c c c c c } _n \backslash ^r & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 0 & 1 \\ 1 & 0&1\\ 2& 0&1&1\\ 3& 0&1&3&1\\ 4& 0&1&7&6&1\\ 5& 0 &1&15&25&10&1 \\ 6 & 0 & 1 & 31 & 90 & 65 & 15 & 1 \\ 7 & 0 & 1 & 63 & 301 & 350 & 140 & 21 & 1 \\ \end{array} \]
\(7\) people of distinct heights want to take a photo. They form exactly \(3\) vertical rows, such that each row is arranged in order of height. How many ways are there to do this?
This starts to look like arranging \(7\) people into \(3\) rows. Verify that the problem can be solved with Stirling numbers of the second kind:
- \(7\) distinct objects: Yes, these people are of distinct heights.
- \(3\) identical boxes: Yes, the order of the rows do not matter.
- Into boxes: Yes, the order of the items does not matter, because there is only \(1\) way to arrange them in increasing order of height.
Thus, it is equal to \( S(7,3) = 301 \) (which is obtained from the above table). \( _ \square\)
Prove by induction that \( S(n,3) = \dfrac{ 3^{n-1} + 1 } {2} - 2 ^ {n-1} \).
Base case: For \( n = 3\), \( S(3,3) = 1 \). \(\dfrac{ 3^{n-1} + 1 } {2} - 2 ^ {n-1}= \frac{ 3^2 + 1 } { 2} - 2 ^ 2 = 5 - 4 = 1 \). Hence the base case is verified.
Induction Hypothesis: Assume it is true for some \( n = k \). By the recurrence relation:
\[ \begin{align}
S(k+1, 3) & = 3 S ( k, 3 ) + S(k, 2 ) \\
& = 3 \left( \frac{ 3^{k-1} + 1 } {2} - 2 ^ {k-1} \right) + \left(\vphantom{\frac{ 3^{k} } {2}} 2^{k-1} - 1 \right) \\
& = \frac{ 3^k + 1 } { 2} - 2 ^{k}. \end{align}\]Hence, by mathematical induction, the statement is true. \(\ _\square \)
Bell Numbers
Previous examples required the objects to be placed in a specific number of non-empty bins. There is a related problem in which objects can be placed in any number of non-empty bins. Consider this example:
There are \(4\) distinct flowers. How many ways can they be planted into identical vases?
These flowers can be placed into \(1\), \(2\), \(3\), or \(4\) vases. The number of distributions of flowers into vases will thus be the sum of Stirling numbers of the second kind:
\[ S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4) = 1 + 7 + 6 + 1 = 15 . \]
The Bell numbers count the number of ways \(n\) distinct objects can be distributed into up to \(n\) identical non-empty bins. In the language of sets, Bell numbers count the partitions of a set of \(n\) objects into non-empty disjoint subsets whose union is the entire set. \(_\square\)
The Stirling numbers denote the number of ways to arrange \(n\) distinct objects into \(k \) identical boxes, and Bell numbers denote the number of ways to arrange \(n\) distinct objects into up to \(n\) identical objects. Hence, Bell numbers are computed as a sum of Stirling numbers:
\[ B_n = \sum_{k=1}^n S(n,k) . \]
From the table of Stirling numbers, the following Bell numbers are computed as the sum of each \(n^\text{th}\) row:
\[\begin{array} &B_0 = 1, &B_1 = 1, &B_2 = 2, &B_3 = 5, &B_4 = 15, &B_5 = 52, &B_6 = 203, &B_7 = 877, &\ldots.\end{array} \]
The Bell numbers have their own recurrence relation:
\[ B_{n+1} = \sum_{k=0}^n { n \choose k } B_k . \]
This will be proven with combinatorics. Consider how the \( (n+1)^\text{th}\) element is partitioned. Suppose that there are \(k\) elements which are not in its box, then there are \( { n \choose k } \) ways to pick these \( k \) elements, and thereafter there are \( B _ k \) ways to arrange these \(k\) elements into identical boxes. Hence, there are \( {n \choose k } B_k \) such arrangements. The resulting Bell number is the sum of all these arrangements across all possible values of \(k\).
It is interesting to note that the exponential generating function of the Bell numbers is
\[ B(x) = \sum_{n=0} ^ \infty \frac{B_n} { n!} x^n = e^{ e^x -1 } . \]
The simplest way to prove this is to show that the previous recurrence relation explains why \( B'(x) = e^x B(x) \), from which the result follows by solving the differential equation and evaluating at \( x = 0 \).
Suppose that \(N\) is the product of \(n\) distinct primes. How many ways are there to write \(N\) as the product of positive integers \( (> 1) \), where the order of terms do not matter ?
Consider how placing \( n \) distinct primes into identical boxes gives us a way of writing \(N\) as the product of positive integers. First, find the prime factorization of each term of the product, and place the factors of each term into a box. Then, since \(N\) is the product of distinct prime factors, each prime factor appears in a unique box. Since the product of all of these terms is \(N\), each prime factor must be in a box.
Conversely, given any arrangement of these \(n\) distinct primes into \(r\) identical boxes, multiply the primes in a box to create a term, and the product of these terms gives the value of \(N\). This establishes the bijection. Thus, the number of ways is \( B_n. \ _\square \)