login
Number of permutations of length n with longest increasing subsequence of length 3.
(Formerly M4640 N1983)
7

%I M4640 N1983 #39 Feb 03 2022 05:55:46

%S 1,9,61,381,2332,14337,89497,569794,3704504,24584693,166335677,

%T 1145533650,8017098273,56928364553,409558170361,2981386305018,

%U 21935294881644,162951791097669,1221201051018189,9225637750090023,70209505971502533,537934326588404973

%N Number of permutations of length n with longest increasing subsequence of length 3.

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

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A001454/b001454.txt">Table of n, a(n) for n = 3..1000</a>

%H R. M. Baer and P. Brock, <a href="http://dx.doi.org/10.1090/S0025-5718-1968-0228216-8">Natural sorting over permutation spaces</a>, Math. Comp. 22 1968 385-410.

%H J. M. Hammersley, <a href="http://projecteuclid.org/euclid.bsmsp/1200514101">A few seedings of research</a>, 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.

%F a(n) ~ 3^(2*n + 4 + 1/2)/(16*Pi*n^4). - _Vaclav Kotesovec_, Aug 16 2013

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

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

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

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

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

%p end:

%p seq(a(n), n=3..30); # _Alois P. Heinz_, Sep 28 2012

%t 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_ *)

%Y Cf. A001453. Column k=3 of A047874.

%K nonn

%O 3,2

%A _N. J. A. Sloane_

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