All Relations Are Created Equal

This is exactly the definition of Bell numbers $B_n$ . We're seeking $B_6 = \boxed{203}$ .

A simple recurrence relation is $B_0 = 1$ and

$\displaystyle B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k$

This can be proven as follows. Given a set of $n+1$ elements, fix an element $e$ . Consider the partition (the equivalence class) that includes $e$ . Suppose it contains $n-k$ elements besides $e$ itself. There are $\binom{n}{n-k} = \binom{n}{k}$ ways to select these $n-k$ elements, and the remaining $k$ elements can be partitioned in $B_k$ ways by definition. Summing over all $k$ gives the above identity.

We can thus use the identity above to generate the Bell numbers $1, 1, 2, 5, 15, 52, \boxed{203}, \ldots$ .

Let the number of equivalence relations on n elements that divide them into k equivalence classes be P(n, k).

Of course, P(n, 1) = 1 and P(n, n) = 1.

Otherwise, look at how this would be obtained from an equivalence relation on n-1 elements. From a relation that divides into k-1 classes, there is only one way to get one that divides into k classes (the new element must be a new class by itself). From a relation that divides into k classes, there are k ways to do this (choose the existing class the new element must become part of). It is easy to see that these are the only two cases.

So P(n, k) = P(n-1, k-1) + k * P(n-1, k).

Now we can just solve this manually by dynamic programming.

Here are the values of P for different values of n till 6 (and k going from 1, 2,... in a row) (values not given are 0):

n     P
1     1
2     1          1
3     1    2*1+1=3           1
4     1    2*3+1=7     3*1+3=6           1
5     1   2*7+1=15    3*6+7=25    4*1+6=10             1
6     1  2*15+1=31  3*25+15=90  4*10+25=65  5*1+10=15  1

Now, to get the required answer, just sum up 1+31+90+65+15+1=203

I came about my solution in the same way as Ivan Koswara (although I was not familiar with the concept of Bell Numbers before reading his solution). Although not the best in regards to time complexity, the python code below produces the desired solution of $\boxed{203}$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# Count Number of Equivalent Relations
def fact(n):
    if n==1 or n==0:
        return 1
    else:
        return n*fact(n-1)

def C(n,k):
    return fact(n)/(fact(k)*fact(n-k))

def f(n):
    if n==0 or n==1:
        return 1
    else:
        return sum([C(n-1,i)*f(i) for i in range(0,n)])

print f(6)