A084869 Number of 2-multiantichains of an n-set.

1, 2, 5, 17, 71, 317, 1415, 6197, 26591, 112157, 466775, 1923077, 7863311, 31972397, 129459335, 522571157, 2104535231, 8460991037, 33972711095, 136277478437, 546270602351, 2188566048077, 8764718254055, 35090241492917

Offset: 0

Author

Goran Kilibarda, Vladeta Jovovic, Jun 10 2003

Keywords

• nonn
• easy

Comments

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 = y. - Ross La Haye, Jan 11 2008

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Goran Kilibarda and Vladeta Jovovic, Antichains of Multisets, J. Integer Seqs., Vol. 7, 2004.
• 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 (9,-26,24).

Crossrefs

Cf. A000079, A000217, A000392, A016269, A032263, A034472, A047707, A051112-A051118, A084870-A084883.

Programs

Mathematica

Table[2^(2*n-1) - 3^n + 3*2^(n-1), {n, 0, 20}] (* Vaclav Kotesovec, Oct 30 2015 *)

PARI

a(n) = 2^(2*n-1)-3^n+3*2^(n-1); \\ Altug Alkan, Sep 12 2017

Formula

a(n) = (1/2!)*(4^n - 2*3^n + 3*2^n).

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

G.f.: -(13*x^2-7*x+1) / ((2*x-1)*(3*x-1)*(4*x-1)). - Colin Barker, Nov 27 2012

a(n) = 9*a(n-1) - 26*a(n-2) + 24*a(n-3). - Vaclav Kotesovec, Oct 30 2015

a(n) = 2^(2n-1) + 2^n + 2^(n-1) - 3^n = A000217(2^n+1) - A034472(n), for n >= 1. - Bob Selcoe, Sep 12 2017