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.

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,2

Comments

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

References

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

Links

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

Formula

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

Mathematica

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

Prog

(Sage) [(4^n - 2^n)/2-(3^n - 1)/2 for n in range(1, 24)] # Zerinvary Lajos, Jun 05 2009
(PARI) a(n)=(4^n-3^n-2^n+1)/2 \\ Charles R Greathouse IV, Jul 25 2011

Crossrefs

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

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

Sequence in context: A291972 A056079 A266622 * A268735 A215705 A368783

Adjacent sequences: A036236 A036237 A036238 * A036240 A036241 A036242

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved