How many unordered partitions of $[n]$ are there, and how to enumerate?

Question

In this context, a partition of $[n]$ is an assignment of each $1\le i\le n$ to a class, but in which the class names don't matter (can be given in any order). For example:

• $[1]$ has one partition, $\{\{1\}\}$.
• $[2]$ has two partitions: $\{\{1,2\}\}, \{\{1\},\{2\}\}$.
• $[3]$ has five partitions: $$\{\{1,2,3\}\}, \{\{1\},\{2,3\}\}, \{\{2\},\{1,3\}\}, \{\{3\},\{1,2\}\}, \{\{1\},\{2\},\{3\}\}.$$
• $[4]$ has 15 partitions: $$\{\{1,2,3,4\}\},$$ $$\{\{1\},\{2,3,4\}\}, \{\{2\},\{1,3,4\}\}, \{\{3\},\{1,2,4\}\}, \{\{4\},\{2,3,4\}\},\\ \{\{1,2\},\{3,4\}\},\{\{1,3\},\{2,4\}\},\{\{1,4\},\{2,3\}\},$$ $$\{\{1\},\{2\},\{3,4\}\},\{\{1\},\{3\},\{2,4\}\},\{\{1\},\{4\},\{2,3\}\},\\ \{\{2\},\{3\},\{1,4\}\},\{\{2\},\{4\},\{1,3\}\},\{\{3\},\{4\},\{1,2\}\},$$ $$\{\{1\},\{2\},\{3\},\{4\}\}.$$

What is an efficient way to enumerate these partitions, and how many are there for general $n$? (I searched OEIS but the four terms here is not enough and I don't have a good algorithm to calculate more terms.)

Edit: To make this question not entirely trivial, is there a way to generate the $k$-th partition of $n$ using the recurrence relation for Bell numbers?

Answer 1

These are the Bell numbers, OEIS A000110. The Bell triangle is a fairly efficient way to generate them, and there’s a great deal more information at the Wikipedia and OEIS links. I’ve not really thought about efficient schemes for enumerating the partitions.

Answer 2

This is an attempt at translating the Bell triangle method for computing Bell numbers into an enumeration of the set partitions.

The Bell triangle looks like this: \begin{matrix}1&&&&\\ 1&2&&&\\ 2&3&5&&\\ 5&7&10&15&\\ 15&20&27&37&52\\ \end{matrix}

If $A_{n,k}$ for $1\le k\le n$ denotes the element of the triangle, then these satisfy the recurrence $A_{n,k}=A_{n,k-1}+A_{n-1,k-1}$ and $A_{n,1}=A_{n-1,n-1}$, and the Bell numbers can be read off the diagonal as $B_n=A_{n,n}$.

The combinatorial interpretation of the off-diagonal elements of the table are that $A_{n-1,k-1}$ counts the number of partitions of $[n]$ such that $\{k\}$ is the largest singleton in the partition.

To tie this in with the Bell numbers, if we take $B_n=A_{n,n}=A_{n+1,1}$ then we have three combinatorial interpretations:

• $B_n$ is the partitions of $[n]$
• $A_{n,n}$ is the partitions of $[n+1]$ containing $\{n+1\}$ as a partition element
• $A_{n+1,1}$ is the partitions of $[n+2]$ containing $\{2\}$ as a partition element, and with no other singletons except possibly $\{1\}$

For the first two, there is the obvious map from a partition $P$ of $[n]$ to $P\cup\{\{n+1\}\}$, which is a partition of $[n+1]$ containing $\{n+1\}$; conversely we can remove $\{n+1\}$ from any partition of $[n+1]$ containing $\{n+1\}$ to get a partition of $[n]$.

For the third property, first remove $\{2\}$ from the partition and move $1$ to the end to get a partition of $[n+1]$ with no singletons except possibly $\{n+1\}$. To get a partition of $[n]$ from this, with any arrangement of singletons, we use all of the sets except the one containing $n+1$ as-is, and add singletons for all the elements of $[n]$ in the same group as $n+1$.

The reverse map takes merges all the singletons and $n+1$ to a single set, and keeps the rest as is. This ensures that no element of $[n]$ is in a singleton in the result. Thus this describes a bijection.

Now, we need a conbinatorial interpretation of the equation $A_{n,k}=A_{n,k-1}+A_{n-1,k-1}$. This involves a bijection of two collections:

• The partitions of $[n+1]$ such that $\{k+1\}$ is the largest singleton
• The disjoint union of:
  • The partitions of $[n+1]$ such that $\{k\}$ is the largest singleton
  • The partitions of $[n]$ such that $\{k\}$ is the largest singleton

Given a partition of $[n+1]$ with $\{k+1\}$ as the largest singleton, we split this into two pieces according to whether $\{1\}$ is a singleton or not. If it is a singleton, then by removing $1$ and decreasing all the other numbers by one, we get a partition of $[n]$ with $\{k\}$ as the largest singleton. Otherwise, only $2\dots k+1$ can be singletons, so we can map $1\mapsto k+1$, and $i+1\mapsto i$ for each $1\le i\le k$, and the result is a partition of $[n+1]$ such that all the singletons are in $1\dots k$.

These bijections directly map to a method for efficiently calculating the $i$-th partition of $[n]$, by applying the bijections recursively in parallel with the Bell triangle method.

---

An alternative formula with a natural combinatorial description is the formula $$B_{n+1}=\sum_{k=0}^n{n\choose k}B_k.$$ Any partition of $[n+1]$ has a unique set containing $n+1$, which can be written in the form $[n+1]\setminus S$ for some $S\subseteq [n]$. We can first choose $|S|=k$, and there are ${n\choose k}$ possibilities for $S$ of this size; then we choose recursively one of the $B_k$ partitions of $S$, and append $[n+1]\setminus S$ to each partition.

Turning this into an efficient mechanism for finding the $i$-th partition of $[n]$ then relies on a method for getting the $i$-th subset of $[n]$ of size $k$; this problem is most commonly dealt with using a combinatorial number system.

Answer 3

The following algorithm is not an optimal contender as this is a difficult problem. We use backtracking to examine potential admissible assignments from among all permutations in alignment with the partitions. No details right now due to time constraints. Written in Perl to be self-contained with a free interpreter. The algorithm is practical to about $n=11$ (tested up to $n=12$ on a fast machine).

Remark, somewhat later. The algorithm here is perfectly straightforward and works by expressing the problem as a kind of constraint satisfaction task. We define a canonical representation of the set partitions in question by ordering the sets according to increasing size, same for their elements and sets of the same size are ordered according to their first element, which is the smallest. Writing this as a table clearly yields a permutation of the $n$ elements. The algorithm places elements in the permutation one by one, starting with the first element on the left. An element is placed at a position only if it does not violate the ordering constraints on sets of the same size (elements in increasing order, first elements in increasing order). This is backtracking. We have found a partition when all $n$ elements have been placed. As for the asymptotics, the values from the generating function $\exp(\exp(z)-1)$ indicate that the value for $n=16$ is a $34$ bit number. Wikipedia has more on the growth rate of these numbers.

#! /usr/bin/perl -w
#

my %pcache = ();

sub part {
    my ($n, $k) = @_;
    my $key = "$n-$k";

    return $pcache{$key}
    if exists $pcache{$key};

    if($k == 1){
        $pcache{$key} = [[$n]];
        return $pcache{$key};
    }

    my @res = ();

    if($n > 1 and $k > 1){
        foreach $term (@{ part($n-1, $k-1) }){
            my @contrib = (1);
            push @contrib, @$term;

            push @res, \@contrib;
        }
    }

    if($n - $k >= $k){
        foreach $term (@{ part($n-$k, $k) }){
            my @contrib =
                map {$_ + 1} @$term;

            push @res, \@contrib;
        }
    }

    $pcache{$key} = \@res;
    return \@res;
}

sub allparts {
    my ($n) = @_;

    my @res;

    for(my $k=$n; $k>0; $k--){
        push @res, @{ part($n, $k) };
    }

    return \@res;
}


sub recurse {
    my ($n, $sofar, $src, $part, $tref, $cref) = @_;
    my $done = scalar(@$sofar);

    if($done == $n){
        my @sets;
        my @sol = @$sofar[0 .. ($n-1)];

        for(my $pos=0; $pos < scalar(@$part); $pos++){
            my @data = splice @sol, 0, $part->[$pos];

            push @sets, '{' . join(', ', @data) . '}';
        }

        print '{', join(', ', @sets), '}';
        print "\n\n";

        $$tref++;
        return;
    }

    for(my $nxt = 0; $nxt < scalar(@$src); $nxt++){
        my $elem = splice @$src, $nxt, 1;
        my $admit = 1;

        push @$sofar, $elem;

        foreach my $condx (@$cref){
            if($condx->[0] <= $done && $condx->[1] <= $done){
                if($sofar->[$condx->[0]] >=
                   $sofar->[$condx->[1]]){
                    $admit = 0;
                    last;
                }
            }
        }

        recurse($n, $sofar, $src, $part, $tref, $cref)
            if $admit;

        pop @$sofar;
        splice @$src, $nxt, 0, $elem;        
    }

    1;
}

 MAIN: {
     my $n = int(shift || 5);

     my $total = 0;

     foreach my $part (@{ allparts($n) }){
         my @groups = ([$part->[0]]);

         for(my $pos = 1; $pos < scalar(@$part); $pos++){
             if($part->[$pos] == $groups[-1]->[0]){
                 push @{ $groups[-1] }, $part->[$pos];
             }
             else{
                 push @groups, [$part->[$pos]];
             };
         };

         my ($baseidx, @conds) = (0);

         foreach my $group (@groups){
             my $grplen = scalar(@$group);
             my $grptype = $group->[0];
             my $grptotal = $grplen * $grptype;

             for(my $pos = 0; $pos < $grptotal; 
                 $pos += $grptype){
                 for($inpos = 1; $inpos < $grptype;
                     $inpos++){
                     push @conds,
                     [$baseidx+$pos+$inpos-1,
                      $baseidx+$pos+$inpos];
                 }
             }

             for(my $pos = $grptype; $pos < $grptotal; 
                 $pos += $grptype){
                 push @conds,
                 [$baseidx+$pos-$grptype,
                  $baseidx+$pos];
             }

             $baseidx += $grptotal;
         };

         my @source = (1 .. $n);
         recurse($n, [], \@source, $part, \$total, \@conds);
     }

     print STDERR "$total\n";

     1;
}

The output from this script looks like this.

{{1}, {2}, {3}, {4}}

{{1}, {2}, {3, 4}}

{{1}, {3}, {2, 4}}

{{1}, {4}, {2, 3}}

{{2}, {3}, {1, 4}}

{{2}, {4}, {1, 3}}

{{3}, {4}, {1, 2}}

{{1}, {2, 3, 4}}

{{2}, {1, 3, 4}}

{{3}, {1, 2, 4}}

{{4}, {1, 2, 3}}

{{1, 2}, {3, 4}}

{{1, 3}, {2, 4}}

{{1, 4}, {2, 3}}

{{1, 2, 3, 4}}

15

Addendum, Aug 22 2016. A tremendous improvement by a factor of almost ten can be obtained by ensuring during backtracking that the remaining values that have not been placed in the permutation do indeed contain an increasing subsequence of length at least the number of values required to complete the particular set currently being assembled. This makes it possible to process all $27644437$ set partitions of $n=13$ elements in fifteen minutes on the machine I used. Of course these data may be archived in a file for instant re-use later. This is the Perl code.

#! /usr/bin/perl -w
#

my %pcache = ();

sub part {
    my ($n, $k) = @_;
    my $key = "$n-$k";

    return $pcache{$key}
    if exists $pcache{$key};

    if($k == 1){
        $pcache{$key} = [[$n]];
        return $pcache{$key};
    }

    my @res = ();

    if($n > 1 and $k > 1){
        foreach $term (@{ part($n-1, $k-1) }){
            my @contrib = (1);
            push @contrib, @$term;

            push @res, \@contrib;
        }
    }

    if($n-$k >= $k){
        foreach $term (@{ part($n-$k, $k) }){
            my @contrib =
                map {$_ + 1} @$term;

            push @res, \@contrib;
        }
    }

    $pcache{$key} = \@res;
    return \@res;
}

sub allparts {
    my ($n) = @_;

    my @res;

    for(my $k=$n; $k>0; $k--){
        push @res, @{ part($n, $k) };
    }

    return \@res;
}


sub recurse {
    my ($n, $sofar, $src, $part, $tref, 
        $cref, $rlref) = @_;
    my $done = scalar(@$sofar);

    if($done == $n){
        my @sets;
        my @sol = @$sofar[0 .. ($n-1)];

        for(my $pos=0; $pos < scalar(@$part); $pos++){
            my @data = splice @sol, 0, $part->[$pos];

            push @sets, '{' . join(', ', @data) . '}';
        }

        print '{', join(', ', @sets), '}';
        print "\n\n";

        $$tref++;
        return;
    }

    for(my $nxt = 0; 
        $nxt <= scalar(@$src) - $rlref->[$done];
        $nxt++){
        my $elem = splice @$src, $nxt, 1;
        my $admit = 1;

        push @$sofar, $elem;

        foreach my $condx (@{ $cref->[$done] }){
            if($sofar->[$condx] >= $elem){
                $admit = 0;
                last;
            }
        }

        recurse($n, $sofar, $src, $part, $tref, 
                $cref, $rlref)
            if $admit;

        pop @$sofar;
        splice @$src, $nxt, 0, $elem;        
    }

    1;
}

 MAIN: {
     my $n = int(shift || 5);

     my $total = 0;

     foreach my $part (@{ allparts($n) }){
         my @groups = ([$part->[0]]);

         for(my $pos = 1; $pos < scalar(@$part); $pos++){
             if($part->[$pos] == $groups[-1]->[0]){
                 push @{ $groups[-1] }, $part->[$pos];
             }
             else{
                 push @groups, [$part->[$pos]];
             };
         };

         my ($baseidx, @conds) = (0);
         @conds = map { [] } (1..$n);

         foreach my $group (@groups){
             my $grplen = scalar(@$group);
             my $grptype = $group->[0];
             my $grptotal = $grplen * $grptype;

             for(my $pos = 0; $pos < $grptotal; 
                 $pos += $grptype){
                 for($inpos = 1; $inpos < $grptype;
                     $inpos++){
                     push @{ $conds[$baseidx+$pos+$inpos] },
                     $baseidx+$pos+$inpos-1;
                 }
             }

             for(my $pos = $grptype; $pos < $grptotal; 
                 $pos += $grptype){
                 push @{ $conds[$baseidx+$pos] },
                 $baseidx+$pos-$grptype;
             }

             $baseidx += $grptotal;
         };

         my @runlens;

         foreach my $comp (@$part){
             for(my $pos = 0; $pos < $comp; $pos++){
                 push @runlens, $comp-$pos;
             }
         }

         my @source = (1 .. $n);
         recurse($n, [], \@source, $part, \$total, 
                 \@conds, \@runlens);
     }

     print STDERR "$total\n";

     1;
}

Addendum II, Aug 22 2016. Actually there is no need for the complicated machinery from above. The enumeration problem can be solved easily using a basic recursion. We build the set partiton one element at a time, adding the new element to each set in the partition that has been formed already or making it into a new singleton set. (This leaves the indexing problem open -- map index to set partition). The new code makes it possible to go up to $n=14$ in half an hour.

#! /usr/bin/perl -w
#

sub found {
    my ($n, $sofar, $mx, $tref) = @_;

    if($n == $mx){
        my (@sets, @sorted);

        @sorted =
            sort {scalar(@$a) <=> scalar(@$b)}
            @$sofar;

        foreach my $part (@sorted){
            push @sets, '{' . join(', ', @$part) . '}';
        }

        print '{', join(', ', @sets), '}';
        print "\n\n";

        $$tref++;
        return;
    }

    for(my $pos = 0; $pos < scalar(@$sofar); $pos++){
        push @{ $sofar->[$pos] }, $n + 1;
        found($n+1, $sofar, $mx, $tref);
        pop @{ $sofar->[$pos] };
    }

    push @$sofar, [$n + 1];
    found($n+1, $sofar, $mx, $tref);
    pop @$sofar;

    1;
}

MAIN : {
    my $n = int(shift || 5);

    my $total = 0;
    found(1, [[1]], $n, \$total);

    print STDERR "$total\n\n";
}

Answer 4

To generate the partitions recursively, suppose you have all partitions of $[n-1]$. Given such a partition, you can add $n $ either as a singleton or to any part of the partition.

Note every partition of $[n] $, when removing $n $, gives a partition of $[n-1] $. This means that every partition of $[n] $ is generated exactly once, so it is efficient in that sense.

I don't know if there is a good encoding that will let you produce the $k$th partition of $[n] $ directly.