A230341 Number of permutations of [2n] in which the longest increasing run has length n.

1, 1, 16, 293, 5811, 133669, 3574957, 109546009, 3788091451, 145957544981, 6201593613645, 288084015576169, 14525808779580645, 790129980885855401, 46120599397152203401, 2875600728737862162481, 190740227037467026439611, 13411608375592255857753781

Offset: 0

Author

Alois P. Heinz, Oct 16 2013

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..300

Crossrefs

A diagonal of A008304.

Cf. A267433.

Programs

Maple

a:= proc(n) option remember; `if`(n<5, [1, 1, 16, 293, 5811][n+1],
      (2*(n+1)*(26615475780292426*n^4 +2862121494132556*n^3
        -240402559504315639*n^2 +79488454158677567*n
        +119546195807549142)*a(n-1)
      -n*(406022528821033256*n^4 -1031369150352151615*n^3
        +11028208356875758*n^2 -1654923205028490137*n
        +3900125789057762682)*a(n-2)
      +2*(n-1)*(421508861354067594*n^4 -1543365451253363033*n^3
        -602924004257000736*n^2 +6654606478117189961*n
        -5221800341103267066)*a(n-3)
      -4*(2*n-7)*(n-2)*(26655798868586248*n^3 +401269836638339496*n^2
        -2000296275137853913*n +2124466470996744981)*a(n-4)
      -8*(n-3)*(n-5)*(2*n-7)*(2*n-9)*(8655617328093650*n
        -14323734034655567)*a(n-5)) / (n*(n+2)*(13307737890146213*n^2
        -43906954139467620*n +22672341406878775)))
    end:
seq(a(n), n=0..25);

Mathematica

b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];
T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k + 1];
a[n_] := T[2n, n];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

Formula

a(n) = A008304(2*n,n).

Recurrence (of order 3): n*(n+2)*(12*n^7 - 101*n^6 + 355*n^5 - 668*n^4 + 631*n^3 - 71*n^2 - 344*n + 174)*a(n) = (n+1)*(48*n^9 - 272*n^8 + 453*n^7 - 10*n^6 - 518*n^5 - 741*n^4 + 4090*n^3 - 5810*n^2 + 3444*n - 720)*a(n-1) - 2*n*(2*n - 3)*(60*n^8 - 277*n^7 + 365*n^6 - 59*n^5 - 549*n^4 + 1619*n^3 - 2101*n^2 + 1228*n - 268)*a(n-2) + 4*(n-1)*(2*n - 5)*(2*n - 3)*(12*n^7 - 17*n^6 + n^5 + 12*n^4 - 91*n^3 + 101*n^2 - 12*n - 12)*a(n-3). - Vaclav Kotesovec, Jul 16 2014

a(n) ~ 2^(2*n+1/2)* n^(n+1) / exp(n). - Vaclav Kotesovec, Jul 16 2014