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!)
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. 28
0, 2, 15, 80, 375, 1652, 7035, 29360, 120975, 494252, 2007555, 8120840, 32753175, 131818052, 529680075, 2125927520, 8525298975, 34165897052, 136857560595, 548011897400, 2193792030375, 8780400395252, 35137296305115, 140596265198480 (list; graph; refs; listen; history; text; internal format)
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

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, 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*StirlingS2(n+1,4) + 2*StirlingS2(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(0)=0, a(1)=2, a(2)=15, a(3)=80, a(n)=10*a(n-1)-35*a(n-2)+50*a(n-3)- 24*a(n-4).

G.f.: x^2*(2-5*x)/(1-10*x+35*x^2-50*x^3+24*x^4). (End)

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 A301566

Adjacent sequences:  A036236 A036237 A036238 * A036240 A036241 A036242

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

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 July 10 14:17 EDT 2020. Contains 335576 sequences. (Running on oeis4.)