A056005 - OEIS

%I #32 Oct 21 2022 22:04:13

%S 0,0,0,2,19,90,302,820,1926,4068,7920,14454,25025,41470,66222,102440,

%T 154156,226440,325584,459306,636975,869858,1171390,1557468,2046770,

%U 2661100,3425760,4369950,5527197,6935814,8639390,10687312,13135320,16046096,19489888

%N Number of 3-element ordered antichains on an unlabeled n-element set; T_1-hypergraphs with 3 labeled nodes and n hyperedges.

%C T_1-hypergraph is a hypergraph (not necessarily without empty hyperedges or multiple hyperedges) which for every ordered pair of distinct nodes have a hyperedge containing one but not the other node.

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

%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath515.htm">Dedekind's problem</a>

%H V. Jovovic and G. Kilibarda, <a href="http://dx.doi.org/10.4213/dm398">On the number of Boolean functions in the Post classes F^{mu}_8</a>, (in Russian), Diskretnaya Matematika, 11 (1999), no. 4, 127-138.

%H V. Jovovic and G. Kilibarda, <a href="http://dx.doi.org/10.1515/dma.1999.9.6.593">On the number of Boolean functions in the Post classes F^{mu}_8</a>, (English translation), Discrete Mathematics and Applications, 9, (1999), no. 6.

%H G. Kilibarda and V. Jovovic, <a href="https://arxiv.org/abs/1411.4187">Enumeration of some classes of T_0-hypergraphs</a>, arXiv:1411.4187 [math.CO], 2014.

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (8,-28,56,-70,56,-28,8,-1).

%F a(n) = C(n+7, 7) - 6*C(n+5, 5) + 6*C(n+4, 4) + 3*C(n+3, 3) - 6*C(n+2, 2) + 2*C(n+1, 1).

%F a(n) = n*(n-2)*(n-1)*(n+1)*(n^3 + 30*n^2 + 131*n - 270)/5040.

%F G.f.: 1/(1-x)^8 - 6/(1-x)^6 + 6/(1-x)^5 + 3/(1-x)^4 - 6/(1-x)^3 + 2/(1-x)^2.

%F G.f.: x^3*(2 + 3*x - 6*x^2 + 2*x^3)/(1-x)^8.

%F Recurrence: a(n) = 8*a(n-1) - 28*a(n-2) + 56*a(n-3) - 70*a(n-4) + 56*a(n-5) - 28*a(n-6) + 8*a(n-7) - a(n-8).

%F Generally, recurrence for the number of m-element ordered antichains on an unlabeled n-element set is a(m, n) = C(2^m, 1)*a(m, n - 1) - C(2^m, 2)*a(m, n - 2) + C(2^m, 3)*a(m, n - 3) + ... + ( - 1)^(k - 1)*C(2^m, k)*a(m, n - k) + ... - a(m, n - 2^m).

%F a(n) = A000580(n+7) - 6*A000389(n+5) + 6*A000332(n+4) + 3*A000292(n+1) - 6*A000217(n+1) + 2*A000027(n+1). - _R. J. Mathar_, Nov 16 2007

%e There are 19 3-element ordered antichains on an unlabeled 4-element set: ({4},{3},{2}), ({4},{3},{1,2}), ({4},{2,3},{1}), ({4},{2,3},{1,3}), ({3,4},{2},{1}), ({3,4},{2},{1,4}), ({3,4},{2,4},{2,3}), ({3,4},{2,4},{1}), ({3,4},{2,4},{1,4}), ({3,4},{2,4},{1,3}), ({3,4},{2,4},{1,2}), ({3,4},{2,4},{1,2,3}), ({3,4},{1,2},{2,4}), ({3,4},{1,2,4},{2,3}), ({3,4},{1,2,4},{1,2,3}), ({2,3,4},{1,4},{1,3}), ({2,3,4},{1,4},{1,2,3}), ({2,3,4},{1,3,4},{1,2}), ({2,3,4},{1,3,4},{1,2,4}).

%t Table[Binomial[n+7,7]-6Binomial[n+5,5]+6Binomial[n+4,4]+3Binomial[n+3,3]- 6Binomial[n+2,2]+ 2Binomial[n+1,1],{n,0,40}] (* or *) LinearRecurrence[ {8,-28,56,-70,56,-28,8,-1},{0,0,0,2,19,90,302,820},40] (* _Harvey P. Dale_, Jul 27 2011 *)

%o (PARI) x='x+O('x^50); concat([0,0,0], Vec(x^3*(2+3*x-6*x^2+2*x^3)/(1-x)^8)) \\ _G. C. Greubel_, Oct 06 2017

%o (Magma) [n*(n-2)*(n-1)*(n+1)*(n^3 + 30*n^2 + 131*n - 270)/5040: n in [0..30]]; // _G. C. Greubel_, Nov 22 2017

%Y Cf. A047707 for 3-element (unordered) antichains on a labeled n-element set.

%Y Cf. A056069, A056070, A056071, A056073, A056163.

%K nonn,easy

%O 0,4

%A _Vladeta Jovovic_, Goran Kilibarda, Jul 24 2000

%E More terms from _Harvey P. Dale_, Jul 27 2011