A218384 Number of nonempty subsets S of the powerset of a set of size n that have the even intersection property.
1, 7, 71, 3071, 1966207, 270499994623, 2342736474457787596799, 86772003564839307784895323681111305093119, 59169757600268575861444773339439520883460632949720404019392912099891777942585343
Offset: 1
Keywords
Examples
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.
Links
- Tilman Piesk, relationship to Boolean functions (Wikiversity)
- 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), 301-315.
Programs
-
Maple
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
-
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 *) -
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, ", "););}
Formula
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).
a(n) ~ 2^(n + 2^(n-1)). - Vaclav Kotesovec, Apr 03 2021
Comments