Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.
This is a Jupyter notebook. See How to use these notes.
Alice decides to invite 14 friends to an unbirthday party later this month. Unfortunately she discovers that because of their busy schedules she can't have them all over on the same day. In fact she will need to have at least 3 separate unbirthday parties in order that everyone can attend. (Since she has at least 364 unbirthdays a year, this isn't a big problem, but on the other hand she doesn't want to throw more unbirthday parties than necessary, at least not until next month.) So she decides to have 3 unbirthday parties. She'll have to divide her set $S$ of 14 friends into 3 subsets $S_0$, $S_1$, and $S_2$ with the following properties: (a) No one can be missed, so $S_0 \cup S_1 \cup S_2 = S$. And (b) no one should be invited twice, so $S_0 \cap S_1 = \emptyset$, $S_1 \cap S_2 = \emptyset$, and $S_1 \cap S_2 = \emptyset$. Any set of three sets $\{S_0, S_1, S_2\}$ with these two properties is called a partition of $S$ of size 3. We have one more requirement, none of the 3 subsets should be empty -- since a party with no guests is hardly a party at all. Alice wonders how many ways she can partition her 14 friends into 3 nonempty subsets.
In general we'd like a way to compute the number of ways to partition a set of size $n$ into $k$ nonempty subsets. For example the set $\{0,1,2,3\}$ can be partioned
We write a contract for the countPartitions function.
The contract is
def countPartitions( n, k ):
"""
Pre: k and n are integers such that 0 <= k and k <= n
Post: result == the number of ways to partition a set of size n into k nonempty subsets.
"""
Alice thinks about her 14 friends. In each partition, Bill is either alone or not alone.
The partitions in which Bill is alone can be obtained by adding the set $\{B\}$ --I'll use "B" for Bill-- to a partition of the 13 remaining friends into 2 nonempty subsets. For example, from the partition: $$ \{ \{C, D, E, F, G\}, \{H, I, J, K, L, M, N, P\} \} $$ we get a partition $$ \{ \{B\}, \{C, D, E, F, G\}, \{H, I, J, K, L, M, N, P\} \} $$
The partitions in which Bill is not alone can be obtained by adding Bill to one of the 3 sets in a partition of the remaining 13 friends. So each solution to partitioning 13 friends into 3 sets yields three partions of the set of 14 friends into 3 partitions. For example the partition: $$ \{ \{C, D, E, F, G\}, \{H, I, J, K, L\}, \{M, N, P\} \} $$ yields three different ways of partitioning the set of 14 friends $$ \{ \{B, C, D, E, F, G\}, \{H, I, J, K, L\}, \{M, N, P\} \}\;\text{,} \\ \{ \{C, D, E, F, G\}, \{B, H, I, J, K, L\}, \{M, N, P\} \}\;\text{, and} \\ \{ \{C, D, E, F, G\}, \{H, I, J, K, L\}, \{B, M, N, P\} \} $$ The three partitions generated are different from each other and also from any partitions generated in a similar way from a different partition of the remaining 13. And they are different from any partitions generated using the method in the previous paragraph. [You should stop and think about why this is true.]
Your turn: Use Alice's observation to complete this equation. $$ countPartitions(n, k) = ... $$ when $0 < k < n$. [Hint: $countPartitions(n-1, k-1)$ and $countPartitions(n, k-1)$ should appear on the right hand side.]
The cases ($k=0$ and $k=n$) that aren't dealt with by this rule can be dealt with easily enough.
Consider a set $S$ of size $0$. There is one partition of size 0, the empty set. $$ countPartitions(0, 0) = 1 $$ For a set of size $n$, with $n>0$, there are no partitions of size 0 $$ countPartitions(n, 0) = 0\text{ for all } n > 0 $$ there is one partition namely of size $n$, namely the partition that puts each member of $S$ on its own. $$ countPartitions(n, n) = 1\text{ for all } n > 0 $$ The first rule and the third can above be combined, so altogether we have three properties
These three properties uniquely define the function, we can see this by induction on $n$.
Here are some values we can compute by hand
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 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 | 13 | 1 |
These numbers, by the way, are known as the Stirling numbers of the second kind. You can read more about them at this Wikipedia entry.
Based on the problem analysis, we can write a design in pseudocode. In this case the pseudocode will look a lot like Python, so you can take this step if you want or skip it if you don't.
[Put your pseudocode here]
Before coding, you should check that your design will work. Here is a checklist
Complete the following function
def countPartitions( n, k ):
"""
Pre: k and n are integers such that 0 <= k and k <= n
Post: result == the number of ways to partition a set of size n into k nonempty subsets.
"""
If you wrote pseudocode, check that your design is consistant with the pseudocode. If you didn't write pseudocode, use the checklist above to check your code.
Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.
countPartitions(0, 0)
countPartitions(1, 0)
countPartitions(1, 1)
countPartitions(2, 0)
countPartitions(2, 1)
countPartitions(2, 2)
countPartitions(2, 0)
Now let's compare your answers with the first 7 rows of our table
s2 = [ [1],
[0, 1],
[0, 1, 1],
[0, 1, 3, 1],
[0, 1, 7, 6, 1],
[0, 1, 15, 25, 10, 1],
[0, 1, 31, 90, 65, 15, 1]]
failures = set()
for n in range(0, 7) :
for r in range(0, n+1):
result = countPartitions(n,r)
print("S(", n, ",", r, ") =", result, end=" " )
if result != s2[n][r]: failures.add( (n, r) )
print()
if len(failures) == 0 : print( "PASSED")
else: print( "FAILED on these inputs: ", failures )
Here is my pseudo code
function $countPartitions( n : nat, k: nat ) $
pre $0 \le k \le n$
post result = the number of ways to partition a set of size $n$ into $k$ nonempty subsetsif $n > 0$ and $k=0$ then 0
| $k = n$ then 1
| $0 < r < n$ then $countPartitions( n-1, k-1) + k \times countPartitions( n-1, k)$
end if
And here is the Python 3 code
def countPartitionsMine( n, k ):
"""
Pre: k and n are integers such that 0 <= k and k <= n
Post: result == the number of ways to partition a set of size n into k nonempty subsets.
"""
assert isinstance(n, int) and n >= 0
assert isinstance(k, int) and 0 <= k and k <= n
if k == n : return 1
elif k == 0: return 0
else: return countPartitionsMine(n-1, k-1) + k*countPartitionsMine(n-1, k)
countPartitionsMine(0, 0)
countPartitionsMine(4, 0)
countPartitionsMine(4, 1)
countPartitionsMine(4, 2)
countPartitionsMine(4, 3)
countPartitionsMine(4, 4)
Next we'll compare with the whole table
s2 = [ [1], [0, 1], [0, 1, 1], [0, 1, 3, 1], [0, 1, 7, 6, 1], [0, 1, 15, 25, 10, 1], [0, 1, 31, 90, 65, 15, 1]]
failures = set()
for n in range(0, 7) :
for r in range(0, n+1):
result = countPartitionsMine(n,r)
print("S(", n, ",", r, ") =", result, end=" " )
if result != s2[n][r]: failures.add( (n, r) )
print()
if len(failures) == 0 : print( "PASSED")
else: print( "FAILED on these inputs: ", failures )
As with combinations, the straightforward recursive solution that I've used is very inefficient. I'm going to ignore this problem for now. The point of these exercises is to get comfortable with creating correct recursive solutions without worrying about efficiency. Later we'll come back to the problem of making this solution efficient by using a technique called "memoization".