OFFSET
0,3
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.
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
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 *)
PROG
(PARI) a(n)=round(hyperu(-n, n+1, 1)*(-1)^n) \\ Charles R Greathouse IV, Dec 30 2014
(Magma) [Factorial(n)*Evaluate(LaguerrePolynomial(n, n), 1): n in [0..40]]; // G. C. Greubel, Aug 11 2022
(SageMath) [factorial(n)*gen_laguerre(n, n, 1) for n in (0..40)] # G. C. Greubel, Aug 11 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Jan 15 2016
STATUS
approved