

A218383


Number of nonempty subsets S of the powerset of a set of size n, that have the odd intersection property.


2



1, 6, 63, 2880, 1942305, 270460574370, 2342736463012620110115, 86772003564839307585762726826882765841700, 59169757600268575861444773339439520868680468342509442047838072019506515900898085
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

A being a set, S belonging to P(P(A)) \ {{}} has the odd intersection property (oip) if there exists a set B (necessarily nonempty) included in A with B∩S odd for each s in S.
For instance for S={{1}, {1,2}} of A={1,2}, let's take B={1}, then {1}∩{1}=1 (odd) and {1,2}∩{1})=1 (odd), so S has oip.


LINKS

Table of n, a(n) for n=1..9.
V. Scharaschkin, The Odd and Even Intersection Properties, The Electronic Journal of Combinatorics, Volume 18, Issue 1 (2011), #P185.
Steve Wright, Some enumerative combinatorics arising from a problem on quadratic nonresidues, Australas. J. Combin. 44 (2009), 301315.


FORMULA

a(n) = sum(i=0, n1, ((1)^(ni1))*(2^(2^i)1)*prod(j=1,i,(2^(nj+1)1)/ (2^j1)) * prod(j=1,ni,2^j1)).


EXAMPLE

For A=2, A = {1,2} and P(A) = {{}, {1}, {2}, {1,2}}
S can be
{{}, {1}, {2}, {1,2}}
{{}, {1}, {2}}
{{}, {1}, {1,2}}
{{}, {2}, {1,2}}
{{1}, {2}, {1,2}}
{{}, {1}}
{{}, {2}}
{{}, {1,2}}
{{1}, {1,2}} has oip, with B={1}
{{2}, {1,2}} has oip, with B={2}
{{1},{2}} has oip, with B={1, 2}
{{}}
{{1}} has oip, with B={1}
{{2}} has oip, with B={2}
{{1,2}} has oip, with B={1}
So we have 6 S with oip.


PROG

(PARI) d(m) = {for (n=1, m, v = sum(i=0, n1, ((1)^(ni1))*(2^(2^i)1)* prod(j=1, i, (2^(nj+1)1)/(2^j1))*prod(j=1, ni, 2^j1)); print1(v, ", "); ); }
(Maxima) A218383[n]:=sum(((1)^(ni1))*(2^(2^i)1)*prod((2^(nj+1)1)/(2^j1), j, 1, i)* prod(2^j1, j, 1, ni), i, 0, n1)$ makelist(A218383[n], n, 1, 9); /* Martin Ettl, Oct 30 2012 */


CROSSREFS

Cf. A218384.
Sequence in context: A023815 A249590 A034665 * A222596 A067447 A083225
Adjacent sequences: A218380 A218381 A218382 * A218384 A218385 A218386


KEYWORD

nonn


AUTHOR

Michel Marcus, Oct 27 2012


STATUS

approved



