|
%I #23 Nov 07 2020 14:13:06
%S 1,6,63,2880,1942305,270460574370,2342736463012620110115,
%T 86772003564839307585762726826882765841700,
%U 59169757600268575861444773339439520868680468342509442047838072019506515900898085
%N Number of nonempty subsets S of the powerset of a set of size n, that have the odd intersection property.
%C 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.
%C 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.
%H V. Scharaschkin, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p185">The Odd and Even Intersection Properties</a>, The Electronic Journal of Combinatorics, Volume 18, Issue 1 (2011), #P185.
%H 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 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)).
%e For |A|=2, A = {1,2} and P(A) = {{}, {1}, {2}, {1,2}}
%e S can be
%e {{}, {1}, {2}, {1,2}}
%e {{}, {1}, {2}}
%e {{}, {1}, {1,2}}
%e {{}, {2}, {1,2}}
%e {{1}, {2}, {1,2}}
%e {{}, {1}}
%e {{}, {2}}
%e {{}, {1,2}}
%e {{1}, {1,2}} has oip, with B={1}
%e {{2}, {1,2}} has oip, with B={2}
%e {{1},{2}} has oip, with B={1, 2}
%e {{}}
%e {{1}} has oip, with B={1}
%e {{2}} has oip, with B={2}
%e {{1,2}} has oip, with B={1}
%e So we have 6 S with oip.
%o (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, ", "););}
%o (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 */
%Y Cf. A218384.
%K nonn
%O 1,2
%A _Michel Marcus_, Oct 27 2012
|
