Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.

This is a Jupyter notebook. See How to use these notes.

UP TO THE TABLE OF CONTENTS

Partitions

The problem

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.

A generalization

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

  • 1 way into a partition of size 4: $\{\{0\}, \{1\}, \{2\}, \{3\}\}$.
  • 6 ways into a partition of size 3: $\{\{0, 1\}, \{2\}, \{3\}$, $\{\{1\}, \{0,2\}, \{3\}\}$, $\{\{1\}, \{2\}, \{0,3\}\}$, $\{\{0\}, \{1,2\}, \{3\}\}$, $\{\{0\}, \{2\}, \{1, 3\}\}$, and $\{\{0\}, \{1\}, \{2,3\}\}$.
  • 7 ways into a partition of size 2: $\{\{0,1,2 \}, \{3\}\}$, $\{\{0, 1, 3\}, \{2\} \}$, $\{\{0, 2, 3\}, \{1\}\}$, $\{\{1,2,3\}, \{0\}\}$, $\{\{0,1\}, \{2,3\}\}$, $\{\{0,2\}, \{1,3\}\}$, and $\{\{0,3\}, \{1,2\}\}$.
  • 1 way into a partition of size 1: $\{\{0, 1, 2, 3\}\}$.
  • 0 ways into a parition of size 0.

A contract

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.
        """

Problem analysis

Alice's observation

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.]

We need a base case

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

  1. $countPartitions(n, n) = 1$ for all $n$, $n \ge 0$.
  2. $countPartitions(n, 0) = 0$ for all $n$, $n > 0$.
  3. $countPartitions(n, k) = ...$ for all $n$, and $r$, $0 < r < n$.

Is this a definition

These three properties uniquely define the function, we can see this by induction on $n$.

Some tests

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.

Your solution

Design

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]

Analyze design

Before coding, you should check that your design will work. Here is a checklist

  • Is every case allowed by the precondition covered?
  • Does the code do the right thing (i.e. return a result allowed by the postcondition) in each case?
  • Is every recursive call smaller in some sense than its parent call?

Code

Complete the following function

In [9]:
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.
    """

Analyze your code

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.

Test your code

Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.

In [10]:
countPartitions(0, 0)
In [11]:
countPartitions(1, 0)
In [12]:
countPartitions(1, 1)
In [13]:
countPartitions(2, 0)
In [14]:
countPartitions(2, 1)
In [15]:
countPartitions(2, 2)
In [16]:
countPartitions(2, 0)

Now let's compare your answers with the first 7 rows of our table

In [17]:
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 )
S( 0 , 0 ) = None 
S( 1 , 0 ) = None S( 1 , 1 ) = None 
S( 2 , 0 ) = None S( 2 , 1 ) = None S( 2 , 2 ) = None 
S( 3 , 0 ) = None S( 3 , 1 ) = None S( 3 , 2 ) = None S( 3 , 3 ) = None 
S( 4 , 0 ) = None S( 4 , 1 ) = None S( 4 , 2 ) = None S( 4 , 3 ) = None S( 4 , 4 ) = None 
S( 5 , 0 ) = None S( 5 , 1 ) = None S( 5 , 2 ) = None S( 5 , 3 ) = None S( 5 , 4 ) = None S( 5 , 5 ) = None 
S( 6 , 0 ) = None S( 6 , 1 ) = None S( 6 , 2 ) = None S( 6 , 3 ) = None S( 6 , 4 ) = None S( 6 , 5 ) = None S( 6 , 6 ) = None 
FAILED on these inputs:  {(6, 6), (3, 0), (2, 1), (6, 2), (5, 1), (4, 0), (3, 3), (5, 5), (4, 4), (6, 3), (5, 0), (2, 2), (4, 1), (1, 1), (6, 4), (3, 2), (0, 0), (5, 4), (6, 0), (4, 2), (1, 0), (6, 5), (5, 3), (6, 1), (3, 1), (2, 0), (4, 3), (5, 2)}

My Solution

Design

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 subsets

if $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

Code

And here is the Python 3 code

In [18]:
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)

Test

In [19]:
countPartitionsMine(0, 0)
Out[19]:
1
In [20]:
countPartitionsMine(4, 0)
Out[20]:
0
In [21]:
countPartitionsMine(4, 1)
Out[21]:
1
In [22]:
countPartitionsMine(4, 2)
Out[22]:
7
In [23]:
countPartitionsMine(4, 3)
Out[23]:
6
In [24]:
countPartitionsMine(4, 4)
Out[24]:
1

Next we'll compare with the whole table

In [25]:
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 )
S( 0 , 0 ) = 1 
S( 1 , 0 ) = 0 S( 1 , 1 ) = 1 
S( 2 , 0 ) = 0 S( 2 , 1 ) = 1 S( 2 , 2 ) = 1 
S( 3 , 0 ) = 0 S( 3 , 1 ) = 1 S( 3 , 2 ) = 3 S( 3 , 3 ) = 1 
S( 4 , 0 ) = 0 S( 4 , 1 ) = 1 S( 4 , 2 ) = 7 S( 4 , 3 ) = 6 S( 4 , 4 ) = 1 
S( 5 , 0 ) = 0 S( 5 , 1 ) = 1 S( 5 , 2 ) = 15 S( 5 , 3 ) = 25 S( 5 , 4 ) = 10 S( 5 , 5 ) = 1 
S( 6 , 0 ) = 0 S( 6 , 1 ) = 1 S( 6 , 2 ) = 31 S( 6 , 3 ) = 90 S( 6 , 4 ) = 65 S( 6 , 5 ) = 15 S( 6 , 6 ) = 1 
PASSED

Going further

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".