login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 228225249142441259147103, 13938493569348563803135339 (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

Labeled incomplete binary trees (every vertex has a left child, a right child, neither, or both) in which every vertex with a right child but no left child has a label greater than the label of its right child. - Ira M. Gessel, Nov 09 2013

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

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seqs., Vol. 6, 2003.

FORMULA

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

O.g.f.: Sum_{n>=1} (2*n)!/(n+1)! * x^n / Product_{k=0..n} (1+k*x). [Paul D. Hanna, Jul 20 2011]

a(n) ~ n! * sqrt(3)*(log(4/3))^(1/2-n)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 13 2013

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 * A242369 A202617 A143633

Adjacent sequences:  A006528 A006529 A006530 * A006532 A006533 A006534

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Typo in g.f. corrected by Joel B. Lewis, Mar 29 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 23 08:17 EDT 2014. Contains 248430 sequences.