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

Author

Vladeta Jovovic and Goran Kilibarda, Feb 28 2000

Keywords

• easy
• nonn

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

Crossrefs

Cf. A000225, A000392, A028243, A000079.

Cf. A036239.

Column k=2 of A288638.

Third column of A294201.

Programs

Magma

[(3^n-2^n+1)/2: n in [1..30]]; // G. C. Greubel, Oct 06 2017

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 *)

PARI

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

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)