A047910 Number of words on {1,1,1,2,2,2,...,n,n,n} with longest increasing subsequence of length n.

1, 1, 19, 1306, 195709, 50775091, 20117051281, 11260558754404, 8445885515991841, 8167981106765263789, 9891092676022013399311, 14655352586540027231760166, 26075763312196388476329754309, 54857291862194079908910267234631, 134685123389924834385817028487259189

Offset

0,3

Comments

Old name was: Row 3 of A047909.

Links

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

J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Formula

Reference gives explicit formula (see page 79): a(k) = h3(k) = Sum_{i=0..k} (Sum_{j=0..k-i} k! * (3*k)! * (-1)^j / (i! * j! * (k-i-j)! * (k+j+2*i)! * 2^(k-i-j))), independently obtained by D. Jackson.

Recurrence: 8*(n-3)*(n-2)^2*a(n) = 4*(n-3)*(10*n^5 - 28*n^4 - 18*n^3 + 117*n^2 - 111*n + 32)*a(n-1) - 6*(n-1)^3*(3*n - 5)*(3*n - 4)*(n^4 + 3*n^3 - 37*n^2 + 71*n - 36)*a(n-2) + 9*(n-2)^3*(n-1)^4*(3*n - 8)*(3*n - 7)*(3*n - 5)*(3*n - 4)*a(n-3). - Vaclav Kotesovec, Feb 21 2016

a(n) ~ 3^(3*n+1/2) * n^(2*n) / (2^n * exp(2*n+2)). - Vaclav Kotesovec, Feb 21 2016

Example

a(2) = 19: 111222, 112122, 112212, 112221, 121122, 121212, 121221, 122112, 122121, 122211, 211122, 211212, 211221, 212112, 212121, 212211, 221112, 221121, 221211. - Alois P. Heinz, Jan 18 2016

Maple

a:= proc(n) option remember; `if`(n<4, [1$2, 19, 1306][n+1],
      ((8*(-2970*n^3-7712*n^2+13777*n-25581+1700*n^4))*a(n-1)
      -(27*(3*n-7))*(3*n-10)*(3*n-8)*(3*n-11)*(1279*n-2397)*
      (n-2)^2*(n-3)^2*a(n-4) +(18*(3*n-7))*(3*n-8)*(1530*n^5
      -7569*n^4+16757*n^3-12919*n^2-34332*n+56657)*(n-2)^2*
      a(n-3) -(12*(-76223*n-62066*n^5+1530*n^7-474622*n^3
      +1611*n^6-161700+242849*n^4+474957*n^2))*a(n-2))/
      (2720*n-8016))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 04 2016

Mathematica

Table[Sum[Sum[k!*(3*k)!*(-1)^j / (i!*j! * (k-i-j)! * (k+j+2*i)! * 2^(k-i-j)), {j, 0, k-i}], {i, 0, k}], {k, 0, 20}] (* Vaclav Kotesovec, Mar 02 2016, after Horton and Kurn *)

Crossrefs

Cf. A047909.

Sequence in context: A078955 A107673 A130037 * A357230 A237429 A177611

Adjacent sequences: A047907 A047908 A047909 * A047911 A047912 A047913

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Terms a(0), a(5)-a(14) and new name from Alois P. Heinz, Jan 18 2016

Status

approved