cp's OEIS Frontend

A006531 Semiorders on n elements.

%I A006531 M3061 #77 May 15 2025 22:37:12
%S A006531 1,1,3,19,183,2371,38703,763099,17648823,468603091,14050842303,
%T A006531 469643495179,17315795469063,698171064855811,30561156525545103,
%U A006531 1443380517590979259,73161586346500098903,3961555049961803092531,228225249142441259147103,13938493569348563803135339
%N A006531 Semiorders on n elements.
%C A006531 Labeled semiorders on n elements: (1+3) and (2+2)-free posets. - Detlef Pauly (dettodet(AT)yahoo.de), Dec 27 2002
%C A006531 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
%D A006531 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A006531 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.30.
%H A006531 Vincenzo Librandi, <a href="/A006531/b006531.txt">Table of n, a(n) for n = 0..200</a>
%H A006531 J. L. Chandon, J. LeMaire and J. Pouget, <a href="http://www.numdam.org/item?id=MSH_1978__62__61_0">Dénombrement des quasi-ordres sur un ensemble fini</a>, Math. Sci. Humaines, No. 62 (1978), 61-80.
%H A006531 J. L. Chandon, J. LeMaire and J. Pouget, <a href="/A006531/a006531_1.pdf">Enumeration of semiorders on a finite set</a>, Preprint (English) of "Dénombrement des quasi-ordres sur un ensemble fini".
%H A006531 J. L. Chandon, <a href="/A006531/a006531.pdf">Letter to N. J. A. Sloane, May 1981</a>
%H A006531 Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Doignon/doignon40.html">Counting Biorders</a>, J. Integer Seqs., Vol. 6, 2003.
%H A006531 Bérénice Delcroix-Oger and Clément Dupont, <a href="https://arxiv.org/abs/2505.06094">Lie-operads and operadic modules from poset cohomology</a>, arXiv:2505.06094 [math.CO], 2025. See p. 28.
%H A006531 Yan X. Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv preprint arXiv:1508.00318 [math.CO], 2015.
%F A006531 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. [corrected by _Joel B. Lewis_, Mar 29 2011]
%F A006531 a(n) = Sum_{k=1..n} S(n, k) * k! * M(k-1), S(n, k): Stirling number of the second kind, M(n): Motzkin number, A001006. - Detlef Pauly, Jun 06 2002
%F A006531 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
%F A006531 a(n) ~ n! * sqrt(3)*(log(4/3))^(1/2-n)/(sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Aug 13 2013
%F A006531 E.g.f.: 1/(1 + (exp(-x) - 1)/(1 + (exp(-x) - 1)/(1 + (exp(-x) - 1)/(1 + (exp(-x) - 1)/(1 + ...))))), a continued fraction. - _Ilya Gutkovskiy_, Nov 18 2017
%F A006531 From _Peter Bala_, Jan 15 2018: (Start)
%F A006531 a(n) = Sum_{k = 0..n} (-1)^(n+k)*Catalan(k)*k!*Stirling2(n,k). Cf. A052895.
%F A006531 Conjecture: for fixed k = 1,2,..., the sequence a(n) (mod k) is eventually periodic with the exact period dividing phi(k), where phi(k) is Euler's totient function A000010. For example, modulo 10 the sequence becomes (1, 1, 3, 9, 3, 1, 3, 9, 3, ...) with an apparent period 1, 3, 9, 3 of length 4 = phi(10) beginning at a(1). (End)
%F A006531 Consider the transformation of a sequence u given by T(u)(m) = (-1)^m*Sum_{n=0..m} (u(n)/(n+1))*(Sum_{k=0..n}(-1)^k*binomial(n,k)*k^m). If u(n) = 1 then T(u)(n) = Bernoulli(n) (with Bernoulli(1) = 1/2), if u(n) = binomial(2*n,n) then T(u)(n) = a(n). - _Peter Luschny_, Jul 09 2020
%p A006531 A006531 := n->add(stirling2(n,k)*k!*A001006(k-1),k=1..n);
%t A006531 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 *)
%o A006531 (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 */
%Y A006531 Cf. A000108 (unlabeled semiorders: Catalan numbers), A052895.
%K A006531 nonn,nice,easy
%O A006531 0,3
%A A006531 _N. J. A. Sloane_