
COMMENTS

a(2), a(3), a(5) and a(7) are prime; a(11) is not.
Let S be a set of n elements. First we perform a set partition on S. Let SU be the set of all nonempty subsets of S. As is well known, 2^n  1 is the number of nonempty subsets of a set with n elements (see A000225). That is, 2^n  1 is the number of elements SU of SU. In the second step, we select k elements from SU. We want to know how many different selections are possible. Let W be the resulting set of selections formed from SU. Then the number of elements W of W is W = sum((binomial(2^n1,k)), k=1..2^n1) = 2^(2^n1)1 = A077585. Example: W(n) = a(n=2) = 7, because W={[[1, 2]], [[1]], [[1, 2], [1]], [[1, 2], [2], [1]], [[1, 2], [2]], [[2], [1]], [[2]]}.  Thomas Wieder, Nov 08 2007
These are socalled double Mersenne numbers, sometimes denoted MM(n) where M = A000225. MM(n) is prime iff M(n) = 2^n1 is a Mersenne prime exponent (A000043), which isn't possible unless n itself is also in A000043. Primes of this form are called double Mersenne primes MM(p). For all Mersenne exponents between 7 and 61, factors of MM(p) are known. MM(61) is far too large for any currently known primality test, but a distributed search for factors of this and other MM(p) is ongoing, see the doublemersenne.org web site.  M. F. Hasler, Mar 05 2020


FORMULA

a(n) = A000225(A000225(n)).
a(n) = A058891(n+1)1.  corrected by Maurizio De Leo, Feb 25 2015
a(n) = (A001146(n)2)/2.
a(n) = A056220(1+a(n1)).
a(n) = Sum_{k=1..2^n1} binomial(2^n1,k).  Thomas Wieder, Nov 08 2007
a(n) = 2 * a(n1)^2 + 4 * a(n1) + 1.  Roderick MacPhee, Oct 05 2012


PROG

(PARI) a(n)=if(n<1, 0, 1+2*(1+a(n1))^2)
(PARI) apply( {A077585(n)=1<<(1<<n1)1}, [0..9]) \\ M. F. Hasler, Mar 05 2020
(Sage) [stirling_number2(2^(n1), 2) for n in range(1, 10)] # Zerinvary Lajos, Nov 27 2009
