|
| |
|
|
A056005
|
|
Number of 3-element ordered antichains on an unlabeled n-element set; T_1-hypergraphs with 3 labeled nodes and n hyperedges.
|
|
9
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
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.
|
|
|
REFERENCES
| V. Jovovic and G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, Diskretnaya Matematika, 11 (1999), no. 4, 127-138 (translated in Discrete Mathematics and Applications, 9, (1999), no. 6)
V. Jovovic, G. Kilibarda, On enumeration of the class of all monotone Boolean functions, in preparation.
|
|
|
LINKS
| K. S. Brown, Dedekind's problem
|
|
|
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)=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 = 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 (mathar(AT)strw.leidenuniv.nl), 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] (* From Harvey P. Dale, Jul 27 2011 *)
|
|
|
CROSSREFS
| Cf. A047707 for 3-element (unordered) antichains on a labeled n-element set.
Cf. A056069, A056070, A056071, A056073, A056163.
Sequence in context: A129446 A054570 A135436 * A034572 A041393 A107123
Adjacent sequences: A056002 A056003 A056004 * A056006 A056007 A056008
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Vladeta Jovovic, Goran Kilibarda (vladeta(AT)eunet.rs), Jul 24 2000
|
|
|
EXTENSIONS
| More terms from Harvey P. Dale, Jul 27 2011
|
| |
|
|
