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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

Crossrefs

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

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

Programs

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

PARI

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

Sage

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

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