A001454 Number of permutations of length n with longest increasing subsequence of length 3.

1, 9, 61, 381, 2332, 14337, 89497, 569794, 3704504, 24584693, 166335677, 1145533650, 8017098273, 56928364553, 409558170361, 2981386305018, 21935294881644, 162951791097669, 1221201051018189, 9225637750090023, 70209505971502533, 537934326588404973

Offset: 3

Author

N. J. A. Sloane

Keywords

• nonn

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.

Crossrefs

Cf. A001453. Column k=3 of A047874.

Programs

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 *)

Formula

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

Extensions

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