cp's OEIS Frontend

A051185 Number of intersecting families of an n-element set. Also number of n-variable clique Boolean functions.

%I A051185 #45 Jan 04 2021 20:00:52
%S A051185 2,6,40,1376,1314816,912818962432,291201248266450683035648,
%T A051185 14704022144627161780744368338695925293142507520,
%U A051185 12553242487940503914363982718112298267975272720808010757809032705650591023015520462677475328
%N A051185 Number of intersecting families of an n-element set. Also number of n-variable clique Boolean functions.
%C A051185 Also the number of n-ary Boolean polymorphisms of the binary Boolean relation OR, namely the Boolean functions f(x1,...,xn) with the property that (x1 or y1) and ... and (xn or yn) implies f(x1,...,xn) or f(y1,...,yn). - _Don Knuth_, Dec 04 2019
%C A051185 These values are necessarily divisible by powers of 2. The sequence of exponents begins 1, 1, 3, 5, 12, 22, 49, 93, ... , 2^(n-1)-C(n-1,floor(n/2)-1), ... (cf. A191391). - _Andries E. Brouwer_, Aug 07 2012
%C A051185 a(1) = 2^1.
%C A051185 a(2) = 6 = 2^1 * 3
%C A051185 a(3) = 2^3 * 5.
%C A051185 a(4) = 2^5 * 43.
%C A051185 a(5) = 2^12 * 3 * 107.
%C A051185 a(6) = 2^22 * 13 * 16741.
%C A051185 a(7) = 2^49 * 2111 * 245039,
%C A051185 a(8) = 2^93 * 3^2 * 5 * 7211 * 76697 * 59656829,
%C A051185 a(9) = 2^200 * 1823 * 2063 * 576967 * 3600144350906020591.
%C A051185 An intersecting family is a collection of subsets of {1,2,...,n} such that the intersection of every subset with itself or with any other subset in the family is nonempty. The maximum number of subsets in an intersecting family is 2^(n-1). - _Geoffrey Critzer_, Aug 16 2013
%D A051185 V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6).
%D A051185 Pogosyan G., Miyakawa M., A. Nozaki, Rosenberg I., The Number of Clique Boolean Functions, IEICE Trans. Fundamentals, Vol. E80-A, No. 8, pp. 1502-1507, 1997/8.
%H A051185 Grant Pogosyan, Miyakawa Masahiro, Akihiro Nozaki, <a href="http://hdl.handle.net/2433/100660">Number of Clique Boolean Functions</a>, 1988.
%H A051185 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%e A051185 a(2) = 6 because we have: {}, {{1}}, {{2}}, {{1, 2}}, {{1}, {1, 2}}, {{2}, {1, 2}}. - _Geoffrey Critzer_, Aug 16 2013
%t A051185 Table[Length[
%t A051185   Select[Subsets[Subsets[Range[1, n]]],
%t A051185    Apply[And,
%t A051185      Flatten[Table[
%t A051185        Table[Intersection[#[[i]], #[[j]]] != {}, {i, 1,
%t A051185 Length[#]}], {j, 1, Length[#]}]]] &]], {n, 1, 4}] (* _Geoffrey Critzer_, Aug 16 2013 *)
%Y A051185 Cf. A036239, A051180-A051184.
%K A051185 hard,nonn,nice
%O A051185 1,1
%A A051185 _Vladeta Jovovic_, Goran Kilibarda
%E A051185 a(8)-a(9) by _Andries E. Brouwer_, Aug 07 2012, Dec 11 2012