login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051185 Number of intersecting families of an n-element set. Also number of n-variable clique Boolean functions. 52
2, 6, 40, 1376, 1314816, 912818962432, 291201248266450683035648, 14704022144627161780744368338695925293142507520, 12553242487940503914363982718112298267975272720808010757809032705650591023015520462677475328 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

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

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

Table of n, a(n) for n=1..9.

Grant Pogosyan, Miyakawa Masahiro, Akihiro Nozaki, Number of Clique Boolean Functions, 1988.

Index entries for sequences related to Boolean functions

EXAMPLE

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

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 *)

CROSSREFS

Cf. A036239, A051180-A051184.

Sequence in context: A199574 A320489 A135755 * A118623 A000612 A319633

Adjacent sequences:  A051182 A051183 A051184 * A051186 A051187 A051188

KEYWORD

hard,nonn,nice

AUTHOR

Vladeta Jovovic, Goran Kilibarda

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 21:20 EST 2020. Contains 332195 sequences. (Running on oeis4.)