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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001454 Number of permutations of length n with longest increasing subsequence of length 3.
(Formerly M4640 N1983)
7
1, 9, 61, 381, 2332, 14337, 89497, 569794, 3704504, 24584693, 166335677, 1145533650, 8017098273, 56928364553, 409558170361, 2981386305018, 21935294881644, 162951791097669, 1221201051018189, 9225637750090023, 70209505971502533, 537934326588404973 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,2

REFERENCES

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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 = 3..1000

R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.

J. M. Hammersley, A few seedings of research, in Proc. Sixth Berkeley Sympos. Math. Stat. and Prob., ed. L. M. le Cam et al., Univ. Calif. Press, 1972, Vol. I, pp. 345-394.

FORMULA

a(n) ~ 3^(2*n+4+1/2)/(16*Pi*n^4). - Vaclav Kotesovec, Aug 16 2013

MAPLE

a:= proc(n) option remember; `if`(n<3, 0, `if`(n=3, 1,

      (18*(n-1)*(2*n-5)*(3*n^2+2*n-3)*(n-2)^2*a(n-3)

      -(n-1)*(147*n^5-553*n^4+199*n^3+937*n^2-790*n+96)*a(n-2)

      +(n+1)*(42*n^5-146*n^4+21*n^3+171*n^2+14*n-48)*a(n-1))/

       ((n-3)*(n+1)*(3*n^2-4*n-2)*(n+2)^2)))

    end:

seq(a(n), n=3..30);  # Alois P. Heinz, Sep 28 2012

MATHEMATICA

h[l_List] := Module[{n = Length[l]}, Total[l]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]]; g[n_, i_, l_List] := If[n == 0 || i == 1, h[Join[l, Array[1&, n]]]^2, If[i<1, 0, Sum[g[n-i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; T[n_] := Table[g[n-k, Min[n-k, k], {k}], {k, 1, n}]; Table[T[n], {n, 3, 24}][[All, 3]] (* Jean-Fran├žois Alcover, Mar 11 2014, after Alois P. Heinz *)

CROSSREFS

Cf. A001453. Column k=3 of A047874.

Sequence in context: A125346 A190666 A016200 * A243877 A200674 A162769

Adjacent sequences:  A001451 A001452 A001453 * A001455 A001456 A001457

KEYWORD

nonn

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Pab Ter (pabrlos2(AT)hotmail.com), Oct 17 2005

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 17:15 EDT 2018. Contains 316529 sequences. (Running on oeis4.)