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}∩{1,2}|=1 (odd), so S has oip.
LINKS
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.
FORMULA
a(n) = sum(i=0, n-1, ((-1)^(n-i-1))*(2^(2^i)-1)*prod(j=1,i,(2^(n-j+1)-1)/ (2^j-1)) * prod(j=1,n-i,2^j-1)).
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, n-1, ((-1)^(n-i-1))*(2^(2^i)-1)* prod(j=1, i, (2^(n-j+1)-1)/(2^j-1))*prod(j=1, n-i, 2^j-1)); print1(v, ", "); ); }
(Maxima) A218383[n]:=sum(((-1)^(n-i-1))*(2^(2^i)-1)*prod((2^(n-j+1)-1)/(2^j-1), j, 1, i)* prod(2^j-1, j, 1, n-i), i, 0, n-1)$ makelist(A218383[n], n, 1, 9); /* Martin Ettl, Oct 30 2012 */
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Michel Marcus, Oct 27 2012
STATUS
approved