A053156 Number of 2-element intersecting families (with not necessarily distinct sets) whose union is an n-element set.

1, 3, 10, 33, 106, 333, 1030, 3153, 9586, 29013, 87550, 263673, 793066, 2383293, 7158070, 21490593, 64504546, 193579173, 580868590, 1742867913, 5229128026, 15688432653, 47067395110, 141206379633, 423627527506, 1270899359733

Offset

1,2

Comments

Let P(A) be the power set of an n-element set A. Then a(n+1) = 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 disjoint and for which x is not a subset of y and y is not a subset of x, or 2) x and y are intersecting and for which either x is a proper subset of y or y is a proper subset of x, or 3) x = y. - Ross La Haye, Jan 12 2008

From Paul Barry, Apr 27 2003: (Start)

With offset 0, this is a(n) = (3*3^n - 2*2^n + 1)/2.

G.f. (1-3*x+3*x^2)/((1-x)*(1-2*x)*(1-3*x)).

E.g.f. (3*exp(3*x) - 2*exp(2*x) + exp(x))/2.

Binomial transform of A083329.

Second binomial transform of A040001. (End)

Links

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

Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

Formula

a(n) = (3^n - 2^n + 1)/2.

a(n) = StirlingS2(n+2,3) + StirlingS2(n+1,2) + 1. - Ross La Haye, Jan 12 2008

From Colin Barker, Jul 29 2012: (Start)

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) for n > 3.

G.f.: x*(1-3*x+3*x^2)/((1-x)*(1-2*x)*(1-3*x)). (End)

Maple

A053156:=n->(3^n - 2^n + 1)/2: seq(A053156(n), n=1..40); # Wesley Ivan Hurt, Oct 06 2017

Mathematica

LinearRecurrence[{6, -11, 6}, {1, 3, 10}, 50] (* or *) Table[(3^n - 2^n + 1)/2, {n, 1, 50}] (* G. C. Greubel, Oct 06 2017 *)

Prog

(PARI) a(n) = (3^n-2^n+1)/2; \\ Michel Marcus, Nov 30 2015
(Magma) [(3^n-2^n+1)/2: n in [1..30]]; // G. C. Greubel, Oct 06 2017

Crossrefs

Cf. A000225, A000392, A028243, A000079.

Cf. A036239.

Column k=2 of A288638.

Third column of A294201.

Sequence in context: A093043 A061566 A082398 * A120897 A077825 A049219

Adjacent sequences: A053153 A053154 A053155 * A053157 A053158 A053159

Keyword

easy,nonn

Author

Vladeta Jovovic and Goran Kilibarda, Feb 28 2000

Status

approved