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

2, 6, 40, 1376, 1314816, 912818962432, 291201248266450683035648, 14704022144627161780744368338695925293142507520, 12553242487940503914363982718112298267975272720808010757809032705650591023015520462677475328

Offset: 1

Author

Vladeta Jovovic, Goran Kilibarda

Keywords

• hard
• nonn
• nice

Comments

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

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

a(1) = 2^1.

a(2) = 6 = 2^1 * 3

a(3) = 2^3 * 5.

a(4) = 2^5 * 43.

a(5) = 2^12 * 3 * 107.

a(6) = 2^22 * 13 * 16741.

a(7) = 2^49 * 2111 * 245039,

a(8) = 2^93 * 3^2 * 5 * 7211 * 76697 * 59656829,

a(9) = 2^200 * 1823 * 2063 * 576967 * 3600144350906020591.

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

Examples

			a(2) = 6 because we have: {}, {{1}}, {{2}}, {{1, 2}}, {{1}, {1, 2}}, {{2}, {1, 2}}. - _Geoffrey Critzer_, Aug 16 2013
		

References

• 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).
• 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.

Links

• Grant Pogosyan, Miyakawa Masahiro, Akihiro Nozaki, Number of Clique Boolean Functions, 1988.
• Index entries for sequences related to Boolean functions

Crossrefs

Cf. A036239, A051180-A051184.

Programs

Mathematica

Table[Length[
  Select[Subsets[Subsets[Range[1, n]]],
   Apply[And,
     Flatten[Table[
       Table[Intersection[#[[i]], #[[j]]] != {}, {i, 1,
Length[#]}], {j, 1, Length[#]}]]] &]], {n, 1, 4}] (* Geoffrey Critzer, Aug 16 2013 *)

Extensions

a(8)-a(9) by Andries E. Brouwer, Aug 07 2012, Dec 11 2012