cp's OEIS Frontend

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

%I A218384 #54 Jul 09 2025 04:35:09
%S A218384 1,7,71,3071,1966207,270499994623,2342736474457787596799,
%T A218384 86772003564839307784895323681111305093119,
%U A218384 59169757600268575861444773339439520883460632949720404019392912099891777942585343
%N A218384 Number of nonempty subsets S of the powerset of a set of size n that have the even intersection property.
%C A218384 If A is a set, an element S of 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.
%C A218384 For instance for S={{},{1}} of A={1,2}, we can take B={2}, and then |{}∩{2}|=0 (even) and |{1}∩{2}|=0 (even), so S has eip.
%H A218384 Tilman Piesk, <a href="https://en.wikiversity.org/wiki/Sequence_A218384">relationship to Boolean functions</a> (Wikiversity)
%H A218384 V. Scharaschkin, <a href="https://doi.org/10.37236/672">The Odd and Even Intersection Properties</a>, The Electronic Journal of Combinatorics, Volume 18, Issue 1 (2011), #P185.
%H A218384 Steve Wright, <a href="https://ajc.maths.uq.edu.au/pdf/44/ajc_v44_p301.pdf">Some enumerative combinatorics arising from a problem on quadratic nonresidues</a>, Australas. J. Combin. 44 (2009), 301-315.
%F A218384 a(n) = 1 + 2*Sum_{i=0..n-1} (-1)^(n-i-1)*(2^(2^i-1)-1)*(Product_{j=1..i} (2^(n-j+1)-1)/(2^j-1)) * 2^binomial(n-i,2).
%F A218384 a(n) ~ 2^(n + 2^(n-1)). - _Vaclav Kotesovec_, Apr 03 2021
%F A218384 Apparently, a(n) = A051179(n) - A305737(n). - _Tilman Piesk_, Jan 26 2025
%e A218384 For |A|=2, A = {1,2} and P(A) = {{}, {1}, {2}, {1,2}}
%e A218384 S can be
%e A218384   {{}, {1}, {2}, {1,2}}
%e A218384   {{}, {1}, {2}}
%e A218384   {{}, {1}, {1,2}}
%e A218384   {{}, {2}, {1,2}}
%e A218384   {{1}, {2}, {1,2}}
%e A218384   {{}, {1}} has eip, with B={2}
%e A218384   {{}, {2}} has eip, with B={1}
%e A218384   {{}, {1,2}} has eip, with B={1,2}
%e A218384   {{1}, {1,2}}
%e A218384   {{2}, {1,2}}
%e A218384   {{1}, {2}}
%e A218384   {{}} has eip, with B={1,2}
%e A218384   {{1}} has eip, with B={2}
%e A218384   {{2}} has eip, with B={1}
%e A218384   {{1,2}} has eip, with B={1,2}
%e A218384 So we have 7 S with eip.
%p A218384 A218384:=n->1+2*add((-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): seq(A218384(n), n=1..10); # _Wesley Ivan Hurt_, Dec 11 2015
%t A218384 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 *)
%o A218384 (PARI) e(m) = {for (n=1, m, v = 1+2*sum(i=0, n-1, ((-1)^(n-i-1))*(2^(2^i-1)-1)* prod(j=1,i,(2^(n-j+1)-1)/(2^j-1))*2^binomial(n-i,2));print1(v, ", "););}
%Y A218384 Cf. A218383, A051179, A305737.
%K A218384 nonn
%O A218384 1,2
%A A218384 _Michel Marcus_, Oct 27 2012