

A218384


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


2



1, 7, 71, 3071, 1966207, 270499994623, 2342736474457787596799, 86772003564839307784895323681111305093119, 59169757600268575861444773339439520883460632949720404019392912099891777942585343
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

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


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) = 1 + 2*Sum_{i=0..n1} (1)^(ni1)*(2^(2^i1)1)*(Product_{j=1..i} (2^(nj+1)1)/(2^j1)) * 2^binomial(ni,2).
a(n) ~ 2^(n + 2^(n1)).  Vaclav Kotesovec, Apr 03 2021


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}} has eip, with B={2}
{{}, {2}} has eip, with B={1}
{{}, {1,2}} has eip, with B={1,2}
{{1}, {1,2}}
{{2}, {1,2}}
{{1}, {2}}
{{}} has eip, with B={1,2}
{{1}} has eip, with B={2}
{{2}} has eip, with B={1}
{{1,2}} has eip, with B={1,2}
So we have 7 S with eip.


MAPLE

A218384:=n>1+2*add((1)^(ni1)*(2^(2^i1)1)* product((2^(nj+1)1)/(2^j1), j=1..i)*2^binomial(ni, 2), i=0..n1): seq(A218384(n), n=1..10); # Wesley Ivan Hurt, Dec 11 2015


MATHEMATICA

Table[1 + 2 Sum[((1)^(n  i  1)) (2^(2^i  1)  1) Product[(2^(n  j + 1)  1)/(2^j  1), {j, 1, i}] 2^Binomial[n  i, 2], {i, 0, n  1}], {n, 9}] (* Michael De Vlieger, Dec 11 2015 *)


PROG

(PARI) e(m) = {for (n=1, m, v = 1+2*sum(i=0, n1, ((1)^(ni1))*(2^(2^i1)1)* prod(j=1, i, (2^(nj+1)1)/(2^j1))*2^binomial(ni, 2)); print1(v, ", "); ); }


CROSSREFS

Cf. A218383.
Sequence in context: A146752 A022518 A113053 * A022503 A063861 A093632
Adjacent sequences: A218381 A218382 A218383 * A218385 A218386 A218387


KEYWORD

nonn


AUTHOR

Michel Marcus, Oct 27 2012


STATUS

approved



