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

0, 0, 0, 2, 19, 90, 302, 820, 1926, 4068, 7920, 14454, 25025, 41470, 66222, 102440, 154156, 226440, 325584, 459306, 636975, 869858, 1171390, 1557468, 2046770, 2661100, 3425760, 4369950, 5527197, 6935814, 8639390, 10687312, 13135320, 16046096, 19489888

Offset

0,4

Comments

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.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

K. S. Brown, Dedekind's problem

V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (in Russian), Diskretnaya Matematika, 11 (1999), no. 4, 127-138.

V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (English translation), Discrete Mathematics and Applications, 9, (1999), no. 6.

G. Kilibarda and V. Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.

Index entries for linear recurrences with constant coefficients, signature (8,-28,56,-70,56,-28,8,-1).

Formula

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).

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

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.

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

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).

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).

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

Example

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}).

Mathematica

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 *)

Prog

(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
(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

Crossrefs

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

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

Sequence in context: A331898 A054570 A135436 * A034572 A041393 A107123

Adjacent sequences: A056002 A056003 A056004 * A056006 A056007 A056008

Keyword

nonn,easy

Author

Vladeta Jovovic, Goran Kilibarda, Jul 24 2000

Extensions

More terms from Harvey P. Dale, Jul 27 2011

Status

approved