A047910 - OEIS

%I #28 Mar 07 2020 00:35:33

%S 1,1,19,1306,195709,50775091,20117051281,11260558754404,

%T 8445885515991841,8167981106765263789,9891092676022013399311,

%U 14655352586540027231760166,26075763312196388476329754309,54857291862194079908910267234631,134685123389924834385817028487259189

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

%C Old name was: Row 3 of A047909.

%H Alois P. Heinz, <a href="/A047910/b047910.txt">Table of n, a(n) for n = 0..200</a>

%H J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. <a href="http://www.ams.org/mathscinet-getitem?mr=681905">MR 681905</a>

%F 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.

%F 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

%F a(n) ~ 3^(3*n+1/2) * n^(2*n) / (2^n * exp(2*n+2)). - _Vaclav Kotesovec_, Feb 21 2016

%e 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

%p a:= proc(n) option remember; `if`(n<4, [1$2, 19, 1306][n+1],

%p       ((8*(-2970*n^3-7712*n^2+13777*n-25581+1700*n^4))*a(n-1)

%p       -(27*(3*n-7))*(3*n-10)*(3*n-8)*(3*n-11)*(1279*n-2397)*

%p       (n-2)^2*(n-3)^2*a(n-4) +(18*(3*n-7))*(3*n-8)*(1530*n^5

%p       -7569*n^4+16757*n^3-12919*n^2-34332*n+56657)*(n-2)^2*

%p       a(n-3) -(12*(-76223*n-62066*n^5+1530*n^7-474622*n^3

%p       +1611*n^6-161700+242849*n^4+474957*n^2))*a(n-2))/

%p       (2720*n-8016))

%p     end:

%p seq(a(n), n=0..20);  # _Alois P. Heinz_, Feb 04 2016

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

%Y Cf. A047909.

%K nonn

%O 0,3

%A _N. J. A. Sloane_

%E Terms a(0), a(5)-a(14) and new name from _Alois P. Heinz_, Jan 18 2016