|
Search: id:A133789
|
|
|
| A133789 |
|
Let P(A) denote 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 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, 1) x and y are disjoint and for which either x is a subset of y or y is a subset of x, or 2) x and y intersect but for which x is not a subset of y and y is not a subset of x. |
|
+0
1
|
|
| 0, 1, 4, 16, 70, 316, 1414, 6196, 26590, 112156, 466774, 1923076, 7863310, 31972396, 129459334, 522571156, 2104535230, 8460991036, 33972711094, 136277478436, 546270602350
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
FORMULA
|
a(n) = (1/2)(4^n - 2*3^n + 3*2^n - 2).
O.g.f.: x*(1-6*x+11*x^2)/[(-1+x)*(-1+4*x)*(-1+3*x)*(-1+2*x)]. - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jan 11 2008
a(n) = A084869(n)-1 = A0162699(n)+2^n-1. - Vladeta Jovovic (vladeta(AT)Eunet.yu), Jan 04 2008
a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3) + StirlingS2(n+1,2). - Ross La Haye (rlahaye(AT)new.rr.com), Jan 11 2008
a(n) = A084869(n)-1. - Vladeta Jovovic (vladeta(AT)Eunet.yu), Jan 04 2008
a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3) + StirlingS2(n+1,2). - Ross La Haye (rlahaye(AT)new.rr.com), Jan 11 2008
|
|
EXAMPLE
|
a(3) = 16 because for P(A) = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} we see that
{1} and {2},
{1} and {3},
{2} and {3},
{1} and {2,3},
{2} and {1,3},
{3} and {1,2}
are disjoint, while
{} and {1},
{} and {2},
{} and {3},
{} and {1,2},
{} and {1,3},
{} and {2,3},
{} and {1,2,3}
are disjoint and one is a subset of the other, and
{1,2} and {1,3},
{1,2} and {2,3},
{1,3} and {2,3}
are intersecting, but neither is a subset of the other.
|
|
CROSSREFS
|
Cf. A082134, A002697, A020522, A006516, A007582, A000302.
Cf. A000225, A000392, A032263.
Sequence in context: A059606 A000303 A144316 this_sequence A151244 A091354 A124533
Adjacent sequences: A133786 A133787 A133788 this_sequence A133790 A133791 A133792
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Ross La Haye (rlahaye(AT)new.rr.com), Jan 03 2008, Jan 08 2008
|
|
EXTENSIONS
|
Edited by njas, Jan 20 2008 to incorporate suggestions from several contributors.
|
|
|
Search completed in 0.003 seconds
|
