|
Search: id:A134057
|
|
|
| A134057 |
|
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 0) x and y are disjoint and for which x is not a subset of y and y is not 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. |
|
+0
2
|
|
| 0, 0, 3, 21, 105, 465, 1953, 8001, 32385, 130305, 522753, 2094081, 8382465, 33542145, 134193153, 536821761, 2147385345, 8589737985, 34359345153, 137438167041, 549754241025
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
REFERENCES
|
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. [From Ross La Haye (rlahaye(AT)new.rr.com), Feb 22 2009]
|
|
FORMULA
|
a(n) = (1/2)(4^n - 3*2^n + 2) = 3*(StirlingS2(n+1,4) + StirlingS2(n+1,3)).
a(n) = C(2^n - 1,2). - Ross La Haye (rlahaye(AT)new.rr.com), Jan 21 2008
a(n) = StirlingS2(2^n - 1,2^n - 2).
|
|
EXAMPLE
|
a(2) = 3 because for P(A) = {{},{1},{2},{1,2}} we have for case 0
{{1},{2}} and we have for case 2 {{1},{1,2}}, {{2},{1,2}}. There are 0
{x,y} of P(A) in this example that fall under case 1.
|
|
CROSSREFS
|
Cf. A000392, A032263, A028243.
Sequence in context: A144883 A074597 A076207 this_sequence A128281 A034268 A140451
Adjacent sequences: A134054 A134055 A134056 this_sequence A134058 A134059 A134060
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Ross La Haye (rlahaye(AT)new.rr.com), Jan 11 2008, Jun 01 2008
|
|
|
Search completed in 0.006 seconds
|
