A134169 a(n) = 2^(n-1)*(2^n - 1) + 1.

1, 2, 7, 29, 121, 497, 2017, 8129, 32641, 130817, 523777, 2096129, 8386561, 33550337, 134209537, 536854529, 2147450881, 8589869057, 34359607297, 137438691329, 549755289601, 2199022206977, 8796090925057, 35184367894529

Offset: 0

Author

Ross La Haye, Jan 12 2008

Keywords

• nonn
• easy

Comments

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 (Case 0) x and y are disjoint, x is not a subset of y, and y is not a subset of x; or (Case 1) x and y are intersecting, but x is not a subset of y, and y is not a subset of x; or (Case 2) x and y are intersecting, and either x is a proper subset of y, or y is a proper subset of x; or (Case 3) x = y.

Examples

			a(2) = 7 because for P(A) = {{},{1},{2},{1,2}} we have for Case 0 {{1},{2}}; we have for Case 2 {{1},{1,2}}, {{2},{1,2}}; and we have for Case 3 {{},{}}, {{1},{1}}, {{2},{2}}, {{1,2},{1,2}}. There are 0 {x,y} of P(A) in this example that fall under Case 1.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• 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 (7,-14,8).

Crossrefs

Cf. A000392, A032263, A028243, A000079, A006516.

Programs

Mathematica

Table[EulerE[2,2^n],{n,0,60}]/2+1 (* Vladimir Joseph Stephan Orlovsky, Nov 03 2009 *)
LinearRecurrence[{7,-14,8},{1,2,7},30] (* Harvey P. Dale, Mar 12 2013 *)

Formula

a(n) = 2^(n-1)*(2^n - 1) + 1.

a(n) = StirlingS2(2^n,2^n - 1) + 1 = C(2^n,2) + 1 = A006516(n) + 1.

From R. J. Mathar, Feb 15 2010: (Start)

a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3).

G.f.: (1 - 5*x + 7*x^2)/((1-x) * (2*x-1) * (4*x-1)). (End)

Extensions

More terms from Vladimir Joseph Stephan Orlovsky, Nov 03 2009

Edited by N. J. A. Sloane, Jan 25 2015 at the suggestion of Michel Marcus