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, 4, 16, 70, 316, 1414, 6196, 26590, 112156, 466774, 1923076, 7863310, 31972396, 129459334, 522571156, 2104535230, 8460991036, 33972711094, 136277478436, 546270602350, 2188566048076, 8764718254054, 35090241492916, 140455083984670, 562102715143516

Offset

0,3

Comments

Also, number of even binomial coefficient in rows 0 to 2^n of Pascal's triangle. [Aaron Meyerowitz, Oct 29 2013]

Links

Table of n, a(n) for n=0..25.

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. [Ross La Haye, Feb 22 2009]

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+2*x)*(-1+3*x)*(-1+4*x)]. - R. J. Mathar, Jan 11 2008

a(n) = A084869(n)-1 = A016269(n-2)+2^n-1. - Vladeta Jovovic, Jan 04 2008, corrected by Eric Rowland, May 15 2017

a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3) + StirlingS2(n+1,2). - Ross La Haye, Jan 11 2008

a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3) + StirlingS2(n+1,2). - Ross La Haye, Jan 11 2008

a(n) = 10*a(n-1)-35*a(n-2)+50*a(n-3)-24*a(n-4). [Aaron Meyerowitz, Oct 29 2013]

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.
Also, through row 8 of Pascal's triangle the a(3)=16 even entries are 2 (so a(0)=0 and a(1)=1) then 4,6,4 (so a(2)=4) then 10,10 then  6,20,6 then 8,28,56,70,56,28,8. [Aaron Meyerowitz, Oct 29 2013]

Crossrefs

Cf. A082134, A002697, A020522, A006516, A007582, A000302.

Cf. A000225, A000392, A032263.

Sequence in context: A344267 A144316 A180145 * A151244 A280767 A091354

Adjacent sequences: A133786 A133787 A133788 * A133790 A133791 A133792

Keyword

nonn

Author

Ross La Haye, Jan 03 2008, Jan 08 2008

Extensions

Edited by N. J. A. Sloane, Jan 20 2008 to incorporate suggestions from several contributors.

Status

approved