How many unordered partitions of $[n]$ are there, and how to enumerate? 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?
 A: 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.
A: 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.
A: 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";
}


A: 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. 
