A051180 -id:A051180 - cp's OEIS frontend

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

Vladeta Jovovic, Goran Kilibarda

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

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

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.

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

Cf. A036239, A051180-A051184.

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

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

A036239 Number of 2-element intersecting families of an n-element set; number of 2-way interactions when 2 subsets of power set on {1..n} are chosen at random.

Original entry on oeis.org

0, 2, 15, 80, 375, 1652, 7035, 29360, 120975, 494252, 2007555, 8120840, 32753175, 131818052, 529680075, 2125927520, 8525298975, 34165897052, 136857560595, 548011897400, 2193792030375, 8780400395252, 35137296305115, 140596265198480

Offset: 1

N. J. A. Sloane

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are intersecting but for which x is not a subset of y and y is not a subset of x, or 1) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x. - Ross La Haye, Jan 10 2008

Graph theory formulation. Let P(A) be the power set of an n-element set A. Then a(n) = the number of edges in the intersection graph G of P(A). The vertices of G are the elements of P(A) and the edges of G are the pairs of elements {x,y} of P(A) such that x and y are intersecting (and x <> y). - Ross La Haye, Dec 23 2017

W. W. Kokko, "Interactions", manuscript, 1983.

T. D. Noe, Table of n, a(n) for n = 1..200
Taylor Brysiewicz, Holger Eble, and Lukas Kühne, Enumerating chambers of hyperplane arrangements with symmetry, arXiv:2105.14542 [math.CO], 2021.
V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, in Russian, Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, English translation, in Discrete Mathematics and Applications, 9, (1999), no. 6.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Cf. A036240, A051180-A051185, A028243, A032263.

Cf. A003462, A006516, A016127, A016129, A016130, A016311, A016316, A016321, A016325. - Zerinvary Lajos, Jun 05 2009

LinearRecurrence[{10,-35,50,-24},{0,2,15,80},40] (* or *) With[{c=1/2!}, Table[ c(4^n-3^n-2^n+1),{n,40}]] (* Harvey P. Dale, May 11 2011 *)

a(n)=(4^n-3^n-2^n+1)/2 \\ Charles R Greathouse IV, Jul 25 2011

[(4^n - 2^n)/2-(3^n - 1)/2 for n in range(1,24)] # Zerinvary Lajos, Jun 05 2009

a(n) = (1/2) * (4^n - 3^n - 2^n + 1).
a(n) = 3*Stirling2(n+1,4) + 2*Stirling2(n+1,3). - Ross La Haye, Jan 10 2008
a(n) = A006516(n) - A003462(n). - Zerinvary Lajos, Jun 05 2009
From Harvey P. Dale, May 11 2011: (Start)
a(n) = 10*a(n-1) - 35*a(n-2) + 50*a(n-3) - 24*a(n-4); a(0)=0, a(1)=2, a(2)=15, a(3)=80.
G.f.: x^2*(2-5*x)/(1 - 10*x + 35*x^2 - 50*x^3 + 24*x^4). (End)
E.g.f.: exp(x)*(exp(x) - 1)^2*(exp(x) + 1)/2. - Stefano Spezia, Jun 26 2022

A051181 Number of 4-element intersecting families of an n-element set.

Original entry on oeis.org

0, 0, 0, 4, 365, 11770, 278455, 5715094, 108498285, 1963243930, 34404675635, 589459538734, 9933916068505, 165358097339890, 2726894329246815, 44648990949187174, 727080119853611525, 11790570902483264650, 190587735542474633995, 3073193346666282232414

Offset: 0

Vladeta Jovovic, Goran Kilibarda

G. C. Greubel, Table of n, a(n) for n = 0..825
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.
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (English translation), Discrete Mathematics and Applications, 9, (1999), no. 6.
Index entries for linear recurrences with constant coefficients, signature (83, -3052, 65670, -919413, 8804499, -58966886, 277278100, -904270136, 1982352768, -2749917312, 2142305280, -696729600).

Cf. A036239, A051180-A051185.

Table[1/4! (16^n - 6*12^n + 12*10^n - 9^n - 22*8^n + 15*7^n + 12*6^n - 17*5^n + 17*4^n - 11*3^n - 6*2^n + 6), {n, 0, 50}] (* G. C. Greubel, Oct 06 2017 *)
LinearRecurrence[{83,-3052,65670,-919413,8804499,-58966886,277278100,-904270136,1982352768,-2749917312,2142305280,-696729600},{0,0,0,4,365,11770,278455,5715094,108498285,1963243930,34404675635,589459538734},20] (* Harvey P. Dale, Jul 04 2019 *)

for(n=0,25, print1((1/4!)*(16^n-6*12^n+12*10^n-9^n-22*8^n+15*7^n +12*6^n-17*5^n+17*4^n-11*3^n-6*2^n+6), ", ")) \\ G. C. Greubel, Oct 06 2017

a(n) = (1/4!)*(16^n - 6*12^n + 12*10^n - 9^n - 22*8^n + 15*7^n + 12*6^n - 17*5^n + 17*4^n - 11*3^n - 6*2^n + 6).

G.f.: -x^3*(64667520*x^8 - 81966960*x^7 + 42070268*x^6 - 11421992*x^5 + 1766529*x^4 - 152845*x^3 + 6317*x^2 - 33*x - 4)/((x-1)*(2*x-1)*(3*x-1)*(4*x-1)*(5*x-1)*(6*x-1)*(7*x-1)*(8*x-1)*(9*x-1)*(10*x-1)*(12*x-1)*(16*x-1)). - Colin Barker, Jul 30 2012

More terms from Harvey P. Dale, Jul 04 2019

A051184 Number of 7-element intersecting families of an n-element set.

Original entry on oeis.org

0, 0, 0, 0, 80, 169125, 71102400, 18047221707, 3623784887164, 638772147728325, 103751227132038920, 15931275037246743999, 2348130220089143792148, 335520750110815538499945, 46803828588394634589433120

Offset: 0

Vladeta Jovovic, Goran Kilibarda

nonn

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

Cf. A036239, A051180-A051185.

1/7! (128^n - 21*96^n + 105*80^n - 35*72^n + 105*68^n - 42*66^n + 7*65^n - 476*64^n - 630*60^n + 1785*56^n + 315*54^n - 210*52^n - 105*51^n + 1260*50^n - 105*49^n - 1575*48^n - 2520*46^n - 105*45^n + 1638*44^n + 840*43^n - 6615*42^n + 1050*41^n + 4130*40^n - 1890*39^n + 14595*38^n + 2835*37^n - 7945*36^n - 1554*35^n - 18711*34^n - 12572*33^n + 24710*32^n + 4620*31^n + 560*30^n + 25995*29^n - 16905*28^n - 13545*27^n - 6510*26^n - 42945*25^n + 12005*24^n + 102011*23^n - 4648*22^n - 87780*21^n - 15785*20^n + 43120*19^n + 21364*18^n + 4200*17^n - 37205*16^n - 17105*15^n + 36386*14^n + 28644*13^n - 57603*12^n + 24150*11^n + 4585*10^n - 16289*9^n + 20943*8^n - 12754*7^n - 287*6^n + 4137*5^n - 3388*4^n + 1764*3^n + 720*2^n - 720)

A051182 Number of 5-element intersecting families of an n-element set.

Original entry on oeis.org

0, 0, 0, 0, 371, 38163, 2236504, 103998636, 4289058501, 164693276181, 6034793020298, 213993130915542, 7407880110115111, 251837583669470799, 8443568934653875932, 280082506996725346368

Offset: 0

Vladeta Jovovic, Goran Kilibarda

nonn

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

Cf. A036239, A051180-A051185.

1/5!(32^n-10*24^n+30*20^n-5*18^n+5*17^n-80*16^n-30*15^n+135*14^n+30*13^n-80*12^n-2*11^n+10*10^n-100*9^n+240*8^n-160*7^n-44*6^n+95*5^n-85*4^n+50*3^n+24*2^n-24).

A051183 Number of 6-element intersecting families of an n-element set.

Original entry on oeis.org

0, 0, 0, 0, 230, 91993, 14037879, 1509286261, 136653987232, 11209147489701, 862949794999193, 63573922606869037, 4535012297248660194, 315713834759742768349, 21570075957885603579067

Offset: 0

Vladeta Jovovic, Goran Kilibarda

nonn

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

Cf. A036239, A051180-A051185.

1/6! (64^n - 15*48^n + 60*40^n - 15*36^n + 30*34^n - 6*33^n - 215*32^n - 180*30^n + 585*28^n + 45*27^n + 60*26^n + 150*25^n - 510*24^n - 360*23^n + 168*22^n - 585*21^n + 795*20^n + 1665*19^n - 1890*18^n - 2175*17^n + 3305*16^n + 1775*15^n - 3795*14^n - 870*13^n + 3123*12^n - 1075*11^n - 495*10^n + 1460*9^n - 2245*8^n + 1424*7^n + 150*6^n - 590*5^n + 499*4^n - 274*3^n - 120*2^n + 120)

A053155 Number of 3-element intersecting families (with not necessarily distinct sets) of an n-element set.

Original entry on oeis.org

0, 1, 7, 50, 397, 3366, 29197, 253030, 2170357, 18385046, 153927037, 1275981510, 10492253317, 85727548726, 696964520077, 5644579061990, 45579645264277, 367223771048406, 2953549834748317, 23724145930814470, 190373553357763237

Offset: 0

Vladeta Jovovic, Goran Kilibarda, Feb 28 2000

G. C. Greubel, Table of n, a(n) for n = 0..1000
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (in Russian), Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (English translation), Discrete Mathematics and Applications, 9, (1999), no. 6.
Index entries for linear recurrences with constant coefficients, signature (29,-343,2135,-7504,14756,-14832,5760).

Cf. A051180.

[(8^n - 3*6^n + 3*5^n + 2*4^n - 3*3^n + 2*2^n - 2)/6: n in [0..50]]; // G. C. Greubel, Oct 06 2017

A053155:=n->(8^n - 3*6^n + 3*5^n + 2*4^n - 3*3^n + 2*2^n - 2)/6: seq(A053155(n), n=0..30); # Wesley Ivan Hurt, Oct 06 2017

Table[(8^n - 3*6^n + 3*5^n + 2*4^n - 3*3^n + 2*2^n - 2)/6, {n, 0, 50}] (* G. C. Greubel, Oct 06 2017 *)
LinearRecurrence[{29, -343, 2135, -7504, 14756, -14832, 5760}, {0, 1, 7, 50, 397, 3366, 29197}, 30] (* Vincenzo Librandi, Oct 07 2017 *)

for(n=0,50, print1((8^n - 3*6^n + 3*5^n + 2*4^n - 3*3^n + 2*2^n - 2)/6, ", ")) \\ G. C. Greubel, Oct 06 2017

a(n) = (8^n - 3*6^n + 3*5^n + 2*4^n - 3*3^n + 2*2^n - 2)/6.
G.f.: x*(1224*x^5-1562*x^4+787*x^3-190*x^2+22*x-1)/((x-1)*(2*x-1)*(3*x-1)*(4*x-1)*(5*x-1)*(6*x-1)*(8*x-1)). - Colin Barker, Jul 29 2012
a(n) = 29*a(n-1) - 343*a(n-2) + 2135*a(n-3) - 7504*a(n-4) + 14756*a(n-5) - 14832*a(n-6) + 5760*a(n-7) for n > 6. - Wesley Ivan Hurt, Oct 06 2017

A055484 Number of unlabeled 3-element intersecting families (with not necessarily distinct sets) of an n-element set.

Original entry on oeis.org

1, 4, 14, 39, 96, 213, 437, 837, 1520, 2632, 4380, 7040, 10979, 16668, 24716, 35879, 51104, 71549, 98625, 134025, 179782, 238292, 312386, 405368, 521083, 663968, 839140, 1052439, 1310534, 1620985, 1992343, 2434229, 2957458, 3574108

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Jul 03 2000

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (in Russian), Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (English translation), Discrete Mathematics and Applications, 9, (1999), no. 6.
Index entries for linear recurrences with constant coefficients, signature (4, -4, -2, 2, 4, 3, -12, 3, 4, 2, -2, -4, 4, -1).

Cf. A053155 (labeled case), A005783, A002727, A051180.

Rest[CoefficientList[Series[-x*(x^3 - x^2 - 1)*(x^6 + x^4 + 2*x^3 + x^2 + 1)/((x^3 - 1)^2*(x^2 - 1)^2*(x - 1)^4), {x, 0, 50}], x]] (* G. C. Greubel, Oct 06 2017 *)
LinearRecurrence[{4,-4,-2,2,4,3,-12,3,4,2,-2,-4,4,-1},{1,4,14,39,96,213,437,837,1520,2632,4380,7040,10979,16668},40] (* Harvey P. Dale, Jun 10 2024 *)

x='x+O('x^50); Vec(-x*(x^3-x^2-1)*(x^6+x^4+2*x^3+x^2+1)/( (x^3-1)^2*(x^2-1)^2*(x-1)^4)) \\ G. C. Greubel, Oct 06 2017

G.f.: -x*(x^3-x^2-1)*(x^6+x^4+2*x^3+x^2+1)/((x^3-1)^2*(x^2-1)^2*(x-1)^4).

More terms from James Sellers, Jul 04 2000

A055485 Number of unlabeled 3-element intersecting families (with distinct sets) of an n-element set.

Original entry on oeis.org

4, 19, 61, 157, 353, 717, 1355, 2412, 4094, 6676, 10524, 16108, 24036, 35063, 50135, 70409, 97295, 132485, 178011, 236268, 310086, 402768, 518158, 660692, 835486, 1048379, 1306039, 1616025, 1986887, 2428245, 2950913, 3566968, 4289896

Offset: 3

Vladeta Jovovic, Goran Kilibarda, Jul 03 2000

nonn

G. C. Greubel, Table of n, a(n) for n = 3..1000
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (in Russian), Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (English translation), Discrete Mathematics and Applications, 9, (1999), no. 6.
Index entries for linear recurrences with constant coefficients, signature (3,1,-9,0,12,7,-15,-16,16,15,-7,-12,0,9,-1,-3,1).

Cf. A051180 (labeled case), A005783.

Rest[Rest[Rest[CoefficientList[Series[-x^3*(x^8 + x^7 - 3*x^6 - x^5 + x^4 + 3*x^3 - x^2 - 3*x - 4)/((x^3 - 1)^2*(x^2 - 1)^2*(x - 1)^4), {x,0,50}], x]]]] (* G. C. Greubel, Oct 06 2017 *)
LinearRecurrence[{3, 1, -9, 0, 12, 7, -15, -16, 16, 15, -7, -12, 0, 9, -1, -3, 1}, {4, 19, 61, 157, 353, 717, 1355, 2412, 4094, 6676, 10524, 16108, 24036, 35063, 50135, 70409, 97295}, 33] (* Vincenzo Librandi, Oct 07 2017 *)

x='x+O('x^50); Vec(-x^3*(x^8+x^7-3*x^6-x^5+x^4+3*x^3-x^2-3*x-4)/((x^3-1)^2*(x^2-1)^2*(x-1)^4)) \\ G. C. Greubel, Oct 06 2017

G.f.: -x^3*(x^8+x^7-3*x^6-x^5+x^4+3*x^3-x^2-3*x-4)/((x^3-1)^2*(x^2-1)^2*(x-1)^4).

More terms from James Sellers, Jul 04 2000

A053153 Number of 3-element intersecting families whose union is an n-element set.

Original entry on oeis.org

0, 0, 13, 170, 1605, 13390, 104993, 794010, 5867245, 42681830, 307120473, 2192847250, 15570312485, 110116458270, 776528783953, 5464646634890, 38398786511325, 269529019274710, 1890415785439433, 13251574765596930

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Feb 28 2000

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

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (22,-190,820,-1849,2038,-840).

Cf. A051180.

[(7^n -3*5^n +3*4^n -4*3^n +3*2^n +2)/6: n in [1..25]]; // G. C. Greubel, Oct 07 2017

LinearRecurrence[{22,-190,820,-1849,2038,-840},{0,0,13,170,1605,13390}, 20] (* Harvey P. Dale, Aug 16 2015 *)

for(n=1,25, print1((7^n -3*5^n +3*4^n -4*3^n +3*2^n +2)/6, ", ")) \\ G. C. Greubel, Oct 07 2017

a(n) = 1/3!*(7^n -3*5^n +3*4^n -4*3^n +3*2^n +2).

G.f. -x^3*(280*x^3 -335*x^2 +116*x -13)/((x-1)*(2*x-1)*(3*x-1)*(4*x-1)*(5*x-1)*(7*x-1)). - Colin Barker, Jul 29 2012

More terms from James Sellers, Mar 01 2000

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A036239 Number of 2-element intersecting families of an n-element set; number of 2-way interactions when 2 subsets of power set on {1..n} are chosen at random.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A051181 Number of 4-element intersecting families of an n-element set.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A051184 Number of 7-element intersecting families of an n-element set.

Views

Author

Keywords

References

Crossrefs

Formula

A051182 Number of 5-element intersecting families of an n-element set.

Views

Author

Keywords

References

Crossrefs

Formula

A051183 Number of 6-element intersecting families of an n-element set.

Views

Author

Keywords

References

Crossrefs

Formula

A053155 Number of 3-element intersecting families (with not necessarily distinct sets) of an n-element set.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A055484 Number of unlabeled 3-element intersecting families (with not necessarily distinct sets) of an n-element set.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula