A134019 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 = y.

1, 2, 4, 11, 46, 227, 1114, 5231, 23566, 102827, 438274, 1836551, 7601686, 31183427, 127084234, 515429471, 2083077406, 8396552027, 33779262994, 135696871991, 544528258726, 2183337968627, 8749031918554, 35043178292111, 140313885993646, 561679104393227, 2247987182714914, 8995761194057831

Offset

0,2

Links

Table of n, a(n) for n=0..27.

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. [Ross La Haye, Feb 22 2009]

Index entries for linear recurrences with constant coefficients, signature (10,-35,50,-24).

Formula

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

G.f.: -(9*x^3-19*x^2+8*x-1) / ((x-1)*(2*x-1)*(3*x-1)*(4*x- 1)). [Colin Barker, Dec 10 2012]

Example

a(3) = 11 because for P(A) = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} we have for case 0 {{1,2},{1,3}}, {{1,2},{2,3}}, {{1,3},{2,3}} and we have for case 1 {{},{}}, {{1},{1}}, {{2},{2}}, {{3},{3}}, {{1,2},{1,2}}, {{1,3},{1,3}}, {{2,3},{2,3}}, {{1,2,3},{1,2,3}}.

Mathematica

Table[3 StirlingS2[n + 1, 4] + StirlingS2[n + 1, 2] + 1, {n, 0, 27}] (* Michael De Vlieger, Nov 30 2015 *)

Prog

(PARI) a(n) = (4^n - 3^(n+1) + 5*2^n - 1)/2; \\ Michel Marcus, Nov 30 2015

Crossrefs

Cf. A032263, A000079.

Sequence in context: A107703 A140838 A114954 * A120259 A174632 A307592

Adjacent sequences: A134016 A134017 A134018 * A134020 A134021 A134022

Keyword

nonn,easy

Author

Ross La Haye, Jan 10 2008

Extensions

More terms from Michael De Vlieger, Nov 30 2015

Status

approved