A134018 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 disjoint and for which either x is a subset of y or y is a subset of x, or 1) x and y are intersecting but for which x is not a subset of y and y is not a subset of x.

0, 1, 3, 10, 45, 226, 1113, 5230, 23565, 102826, 438273, 1836550, 7601685, 31183426, 127084233, 515429470, 2083077405, 8396552026, 33779262993, 135696871990, 544528258725, 2183337968626, 8749031918553, 35043178292110, 140313885993645, 561679104393226

Offset

0,3

Links

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

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 - 3) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,2).

G.f.: x*(1-7*x+15*x^2)/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)). [Colin Barker, Jul 29 2012]

Example

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

Mathematica

LinearRecurrence[{10, -35, 50, -24}, {0, 1, 3, 10}, 30] (* Harvey P. Dale, Dec 01 2017 *)

Crossrefs

Cf. A000225, A032263.

Sequence in context: A293554 A346066 A211193 * A355719 A028417 A060311

Adjacent sequences: A134015 A134016 A134017 * A134019 A134020 A134021

Keyword

nonn,easy

Author

Ross La Haye, Jan 10 2008

Extensions

More terms from Harvey P. Dale, Dec 01 2017

Status

approved