|
| |
|
|
A006531
|
|
Semiorders on n elements.
(Formerly M3061)
|
|
5
|
|
|
|
1, 1, 3, 19, 183, 2371, 38703, 763099, 17648823, 468603091, 14050842303, 469643495179, 17315795469063, 698171064855811, 30561156525545103, 1443380517590979259, 73161586346500098903, 3961555049961803092531
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Labeled semiorders on n elements: (1+3) and (2+2)-free posets. - Detlef Pauly (dettodet(AT)yahoo.de), Dec 27 2002
|
|
|
REFERENCES
|
J. L. Chandon, J. LeMaire and J. Pouget, Dénombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 61-80.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.30.
|
|
|
LINKS
|
Table of n, a(n) for n=0..17.
Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seqs., Vol. 6, 2003.
|
|
|
FORMULA
|
O.g.f.: Sum_{n>=1} (2*n)!/(n+1)! * x^n / Product_{k=0..n} (1+k*x). [From Paul D. Hanna, Jul 20 2011]
E.g.f.: C(1-exp(-x)), where C(x) = (1 - sqrt(1 - 4*x)) / (2*x) is the ordinary g.f. for the Catalan numbers A000108.
a(n) = sum( S(n, k) * k! * M(k-1), k=1..n), S(n, k): Stirling number of the second kind, M(n): Motzkin number, A001006. - Detlef Pauly, Jun 06 2002
|
|
|
MAPLE
|
A006531 := n->add(stirling2(n, k)*k!*A001006(k-1), k=1..n);
|
|
|
MATHEMATICA
|
m[n_] := m[n] = m[n-1] + Sum[ m[k]*m[n-k-2], {k, 0, n-2}]; m[0] = a[0] = 1; a[n_] := Sum[ StirlingS2[n, k]*k!*m[k-1], {k, 1, n}]; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Jul 24 2012, after Maple *)
|
|
|
PROG
|
(PARI) {a(n)=polcoeff(sum(m=0, n, (2*m)!/(m+1)!*x^m/prod(k=1, m, 1+k*x+x*O(x^n))), n)} /* Paul D. Hanna, Jul 20 2011 */
|
|
|
CROSSREFS
|
Cf. A000108 (unlabeled semiorders: Catalan numbers).
Sequence in context: A121083 A213533 A203133 * A202617 A143633 A052888
Adjacent sequences: A006528 A006529 A006530 * A006532 A006533 A006534
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Typo in GF corrected by Joel B. Lewis, Mar 29 2011
|
|
|
STATUS
|
approved
|
| |
|
|
