A036240 -id:A036240 - cp's OEIS frontend

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

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

A005530 Number of Boolean functions of n variables from Post class F(8,inf); number of degenerate Boolean functions of n variables.

Original entry on oeis.org

2, 6, 38, 942, 325262, 25768825638, 129127208425774833206, 2722258935367507707190488025630791841374

Offset: 1

N. J. A. Sloane, R. K. Guy

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
I. Tomescu, Introducere in Combinatorica. Editura Tehnica, Bucharest, 1972, p. 129.

Alois P. Heinz, Table of n, a(n) for n = 1..12
T. E. Allen, J. Goldsmith, N. Mattei, Counting, Ranking, and Randomly Generating CP-nets, 2014.
R. K. Guy, Letter to N. J. A. Sloane, Mar 1974
Y. Raekow and K. Ziegler, A taxonomy of non-cooperatively computable functions, Presented at WEWoRC 2011 (link to conference record).
I. Tomescu, Excerpts from "Introducese in Combinatorica" (1972), pp. 230-1, 44-5, 128-9. (Annotated scanned copy)
Index entries for sequences related to Boolean functions

a(n) = 2^(2^n) - A000371(n). Cf. A036239, A036240.

Sum[(-1)^(j + 1) Binomial[n, j] 2^2^(n - j), {j, 1, n}]

for(n=1,10, print1(sum(j=1,n, (-1)^(j+1)*binomial(n,j)*2^(2^(n-j))), ", ")) \\ G. C. Greubel, Oct 06 2017

a(n) = Sum_{j=1..n} (-1)^(j+1)*binomial(n,j)*2^(2^(n-j)).

More terms from Vladeta Jovovic, Goran Kilibarda

A051375 Number of Boolean functions of n variables and rank 3 from Post class F(5,inf).

Original entry on oeis.org

0, 0, 9, 66, 345, 1590, 6909, 29106, 120465, 493230, 2005509, 8116746, 32744985, 131801670, 529647309, 2125861986, 8525167905, 34165634910, 136857036309, 548010848826, 2193789933225, 8780396200950, 35137287916509

Offset: 1

Vladeta Jovovic, Goran Kilibarda

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
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
Index entries for sequences related to Boolean functions
Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Cf. A036240.

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

Table[(4^n - 3^n - 3*2^n + 5)/2, {n, 0, 50}] (* G. C. Greubel, Oct 08 2017 *)

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

a(n) = A036239(n) - A000918(n).
a(n) = (4^n - 3^n - 3*2^n + 5)/2.
a(n) = Sum_{j=1..n} (-1)^(j+1)*C(n, j)*C(2^(n-j)-1, k-1) (with k=3).
Also: 1/(k-1)!*Sum(s(k, j)*(2^((j-1)*n)-(2^(j-1)-1)^n), j=1..k), where s(k, j) are Stirling numbers of the first kind (with k=3).
From Colin Barker, Jun 25 2012: (Start)
a(n) = 10*a(n-1) - 35*a(n-2) + 50*a(n-3) - 24*a(n-4).
G.f.: 3*x^3*(3-8*x)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)). (End)

More terms from James Sellers

A051376 Number of Boolean functions of n variables and rank 4 from Post class F(5,inf).

Original entry on oeis.org

0, 0, 3, 134, 1935, 20830, 198303, 1776894, 15402495, 130890110, 1098087903, 9130126654, 75412301055, 619706950590, 5071742430303, 41369422556414, 336511166127615, 2730929153686270, 22119108433729503, 178853777028618174

Offset: 1

Vladeta Jovovic, Goran Kilibarda

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, 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 sequences related to Boolean functions
Index entries for linear recurrences with constant coefficients, signature (25,-241,1135,-2734,3160,-1344).

Cf. A000918, A036239, A036240.

[(8^n - 7^n - 6*4^n + 6*3^n + 11*2^n - 17)/6: n in [1..50]]; // G. C. Greubel, Oct 08 2017

Table[(8^n - 7^n - 6*4^n + 6*3^n + 11*2^n - 17)/6, {n, 1, 50}] (* G. C. Greubel, Oct 08 2017 *)

for(n=1,50, print1((8^n - 7^n - 6*4^n + 6*3^n + 11*2^n - 17)/6, ", ")) \\ G. C. Greubel, Oct 08 2017

a(n) = A036240(n) - A036239(n) + A000918(n).
a(n) = (8^n - 7^n - 6*4^n + 6*3^n + 11*2^n - 17)/6.
a(n) = Sum_{j=1..n} (-1)^(j+1)*C(n, j)*C(2^(n-j)-1, k-1), where k=4.
Also: 1/(k-1)!*Sum_{j=1..k} s(k, j)*(2^((j-1)*n)-(2^(j-1)-1)^n), where s(k, j) are Stirling numbers of the first kind (and k=4).
G.f.: x^3*(3 + 59*x - 692*x^2 + 1344*x^3) / ( (x-1)*(4*x-1)*(3*x-1)*(2*x-1)*(8*x-1)*(7*x-1) ). - R. J. Mathar, Jun 13 2013

More terms from James Sellers

A051381 Number of Boolean functions of n variables from Post class F(5,inf).

Original entry on oeis.org

1, 3, 19, 471, 162631, 12884412819, 64563604212887416603, 1361129467683753853595244012815395920687, 521064401567922879406069432539095585333589848390805645835993148352662477920015

Offset: 1

Vladeta Jovovic, Goran Kilibarda

G. C. Greubel, Table of n, a(n) for n = 1..12
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.
S. Spasovski and A. M. Bogdanova, Optimization of the Polynomial Greedy Solution for the Set Covering Problem, 2013, 10th Conference for Informatics and Information Technology (CIIT 2013).
Index entries for sequences related to Boolean functions

Cf. A036239, A036240. Equals A005530(n)/2.

Table[Sum[(-1)^(j + 1)*Binomial[n, j]*2^(2^(n - j) - 1) , {j, 1, n}], {n, 1, 5}] (* G. C. Greubel, Oct 08 2017 *)

a(n) = Sum_{j=1..n} (-1)^(j+1)*C(n, j)*2^(2^(n-j)-1).

More terms from James Sellers

cp's OEIS Frontend

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

A005530 Number of Boolean functions of n variables from Post class F(8,inf); number of degenerate Boolean functions of n variables.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A051375 Number of Boolean functions of n variables and rank 3 from Post class F(5,inf).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A051376 Number of Boolean functions of n variables and rank 4 from Post class F(5,inf).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A051381 Number of Boolean functions of n variables from Post class F(5,inf).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions