A133224 Let P(A) be the power set of an n-element set A and let B be the Cartesian product of P(A) with itself. Remove (y,x) from B when (x,y) is in B and x <> y and let R35 denote the reduced set B. Then a(n) = the sum of the sizes of the union of x and y for every (x,y) in R35.

0, 2, 14, 78, 400, 1960, 9312, 43232, 197120, 885888, 3934720, 17307136, 75509760, 327182336, 1409343488, 6039920640, 25770065920, 109522223104, 463857647616, 1958507577344, 8246342451200

Offset: 0

Author

Ross La Haye, Dec 30 2007, Jan 03 2008

Keywords

• nonn
• easy

Comments

A082134 is the analogous sequence if "union" is replaced by "intersection" and A002697 is the analogous sequence if "union" is replaced by "symmetric difference". Here, X union Y = Y union X are considered as the same Cartesian product [Relation (37): U_Q(n) in document of Ross La Haye in reference], if we want to consider that X Union Y and Y Union X are two distinct Cartesian products, see A212698. [Bernard Schott, Jan 11 2013]

Examples

			a(2) = 14 because for P(A) = {{},{1},{2},{1,2}} |{} union {1}| = 1, |{} union {2}| = 1, |{} union {1,2}| = 2, |{1} union {2}| = 2, |{1} union {1,2}| = 2 and |{2} union {1,2}| = 2, |{} union {}| = 0, |{1} union {1}| = 1, |{2} union {2}| = 1, |{1,2} union {1,2}| = 2, which sums to 14.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..300
• 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 (12,-52,96,-64).

Crossrefs

Cf. A027471, A002697, A082134, A212698.

Programs

Magma

[n*(2^(n-2) + 3*2^(2*n-3)): n in [0..30]]; // Vincenzo Librandi, Jun 10 2011

Mathematica

LinearRecurrence[{12,-52,96,-64},{0,2,14,78},30] (* Harvey P. Dale, Jan 24 2019 *)

Formula

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

G.f.: 2*x*(7*x^2-5*x+1) / ((2*x-1)^2*(4*x-1)^2). [Colin Barker, Dec 10 2012]

E.g.f.: exp(2*x)*(1 + 3*exp(2*x))*x. - Stefano Spezia, Aug 04 2022