login
Number of empty sets in the n-th power set of the empty set.
0

%I #18 Mar 31 2015 00:44:22

%S 1,1,2,5,41,1343489

%N Number of empty sets in the n-th power set of the empty set.

%C Starting with the empty set {}, we can repeatedly take the power set, say, n times, to obtain the n-th power set. If we write out the n-th power set, a(n) is the number of occurrences of {} in this written form. For n>0, this corresponds with the total number of empty sets contained in the n-th power set in any level of the set hierarchy.

%C a(6) = a(5)*2^65535 + 1 is too large to display in full. - _N. J. A. Sloane_, Mar 31 2015

%F Let t(n) = 2^2^2^...^2 be an exponentiation tower, n-1 2s high. The n-th element of the sequence a(n) is then given by the recurrence a(n) = 1 if n=0 or n=1, a(n) = (a(n-1)*t(n))/2 + 1 if n>1.

%e For n=0, we take the power set of {} 0 times, which yields {}. In the written form, there is one occurrence of {}, so a(0) = 1.

%e For n=2, the 2nd power set of {} is { {}, {{}} }. In the written form there are 2 occurrences of {}, so a(2) = 2. Also in all levels of the set hierarchy together, this set contains 2 empty sets. Indeed the recurrent formula yields a(2) = (a(1)*t(2))/2 + 1 = (1*2)/2 + 1 = 2.

%o (Python)

%o def empty_sets(n):

%o . if n==0:

%o .. return 1

%o . if n==1:

%o .. return 1

%o . else:

%o .. t = 2

%o .. for i in range(n-2):

%o ... t = 2**t

%o .. return ((empty_sets(n-1)*t)/2 + 1)

%o # _Kesava van Gelder_, Mar 12 2015

%K nonn,easy

%O 0,3

%A _Kesava van Gelder_, Mar 12 2015