login
Number of 2-multiantichains of an n-set.
16

%I #47 Oct 07 2017 10:13:57

%S 1,2,5,17,71,317,1415,6197,26591,112157,466775,1923077,7863311,

%T 31972397,129459335,522571157,2104535231,8460991037,33972711095,

%U 136277478437,546270602351,2188566048077,8764718254055,35090241492917

%N Number of 2-multiantichains of an n-set.

%C 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

%H G. C. Greubel, <a href="/A084869/b084869.txt">Table of n, a(n) for n = 0..1000</a>

%H Goran Kilibarda and Vladeta Jovovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL7/Kilibarda/kili2.html">Antichains of Multisets</a>, J. Integer Seqs., Vol. 7, 2004.

%H Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (9,-26,24).

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

%F a(n) = 3*StirlingS2(n+1,4) + StirlingS2(n+1,3) + StirlingS2(n+1,2) + 1. - _Ross La Haye_, Jan 11 2008

%F G.f.: -(13*x^2-7*x+1) / ((2*x-1)*(3*x-1)*(4*x-1)). - _Colin Barker_, Nov 27 2012

%F a(n) = 9*a(n-1) - 26*a(n-2) + 24*a(n-3). - _Vaclav Kotesovec_, Oct 30 2015

%F 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

%t Table[2^(2*n-1) - 3^n + 3*2^(n-1), {n, 0, 20}] (* _Vaclav Kotesovec_, Oct 30 2015 *)

%o (PARI) a(n) = 2^(2*n-1)-3^n+3*2^(n-1); \\ _Altug Alkan_, Sep 12 2017

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

%K nonn,easy

%O 0,2

%A Goran Kilibarda, _Vladeta Jovovic_, Jun 10 2003