A006902 a(n) = (2n)! * Sum_{k=0..n} (-1)^k * binomial(n,k) / (n+k)!.

1, 1, 5, 47, 641, 11389, 248749, 6439075, 192621953, 6536413529, 248040482741, 10407123510871, 478360626529345, 23903857657114837, 1290205338991689821, 74803882225482661259, 4636427218380366565889, 305927317398343461908785, 21410426012751471702223333

Offset: 0

Author

Simon Plouffe and N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Number of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length n. a(2) = 5: 1122, 1212, 1221, 2112, 2121. - Alois P. Heinz, Jan 18 2016

References

• J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congress. Numerantium, 33 (1981), 75-80.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..360 (terms n = 1..100 from T. D. Noe)
• Yassine El Maazouz and Jim Pitman, The Bernoulli clock: probabilistic and combinatorial interpretations of the Bernoulli polynomials by circular convolution, arXiv:2210.02027 [math.PR], 2022.

Crossrefs

Row n=2 of A047909.

Main diagonal of A267480.

Cf. A082545.

Programs

Magma

[Factorial(n)*Evaluate(LaguerrePolynomial(n, n), 1): n in [0..40]]; // G. C. Greubel, Aug 11 2022

Maple

a:= proc(n) option remember; `if`(n<3, [1$2, 5][n+1], (
      (n^3+n^2-7*n+4)*a(n-1)-2*(2*n-3)*(n-1)^3*a(n-2))/(n-2))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Jan 15 2016

Mathematica

Table[(-1)^k HypergeometricU[-k, 1+k, 1], {k,0,20}] (* Vladimir Reshetnikov, Feb 16 2011 *)

PARI

a(n)=round(hyperu(-n,n+1,1)*(-1)^n) \\ Charles R Greathouse IV, Dec 30 2014

SageMath

[factorial(n)*gen_laguerre(n,n,1) for n in (0..40)] # G. C. Greubel, Aug 11 2022

Formula

a(n) = n!*LaguerreL(n, n, 1). - Vladeta Jovovic, May 11 2003

(n-2)*a(n) - (n^3+n^2-7*n+4)*a(n-1) + 2*(2*n-3)*(n-1)^3*a(n-2) = 0. - Vladeta Jovovic, Jul 16 2004

a(n) ~ n^n*2^(2*n+1/2)/exp(n+1). - Vaclav Kotesovec, Jun 22 2013

a(n) = B_n(n*0!,(n-1)*1!, ..., 1*(n-1)!), where B_n(x1, ..., xn) is the n-th complete Bell polynomial. - Max Alekseyev, Jul 04 2015

a(n) = n!*binomial(2*n,n)*hypergeom([-n], [n+1], 1). - Peter Luschny, May 04 2017

a(n) = n!*Z(S_n; n, n-1, ..., 1) where Z(S_n) is the cycle index of the symmetric group of order n. - Sean A. Irvine, Nov 14 2017

a(n) = n! * [x^n] exp(-x/(1 - x))/(1 - x)^(n+1). - Ilya Gutkovskiy, Nov 21 2017

E.g.f.: exp(1-c(x))/sqrt(1-4*x), where c(x) = (1-sqrt(1-4*x))/(2*x) is the Catalan number generating function. - Ira M. Gessel, Jun 04 2021

Extensions

a(0)=1 prepended by Alois P. Heinz, Jan 15 2016