

A134168


Let P(A) be the power set of an nelement 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, 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.


1



1, 3, 9, 30, 111, 438, 1779, 7290, 29871, 121998, 496299, 2011650, 8129031, 32769558, 131850819, 529745610, 2126058591, 8525561118, 34166421339, 136858609170, 548013994551, 2193796224678, 8780408783859, 35137313082330, 140596298752911, 562526359448238, 2250528981434379, 9003386657325090
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000
Ross La Haye, Binary Relations on the Power Set of an nElement Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Index entries for linear recurrences with constant coefficients, signature (10,35,50,24).


FORMULA

a(n) = (1/2)*(4^n  3^n + 3*2^n  1).
a(n) = 3*StirlingS2(n+1,4) +2*StirlingS2(n+1,3) +2*StirlingS2(n+1,2) +1.
G.f.: (5*x^3  14*x^2 + 7*x  1)/((x1)*(2*x1)*(3*x1)*(4*x1)).  Colin Barker, Jul 30 2012


EXAMPLE

a(2) = 9 because for P(A) = {{},{1},{2},{1,2}} we have for case 0 {{},{1}}, {{},{2}}, {{},{1,2}} and 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.


MATHEMATICA

LinearRecurrence[{10, 35, 50, 24}, {1, 3, 9, 30}, 50] (* or *) Table[(1/2)*(4^n  3^n + 3*2^n  1), {n, 0, 50}] (* G. C. Greubel, May 30 2016 *)


CROSSREFS

Cf. A000225, A032263, A028243, A000079.
Sequence in context: A151472 A107379 A117428 * A124427 A308554 A055730
Adjacent sequences: A134165 A134166 A134167 * A134169 A134170 A134171


KEYWORD

nonn,easy


AUTHOR

Ross La Haye, Jan 12 2008


STATUS

approved



