OFFSET
0,3
LINKS
Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..145 (terms 0..70 from Alois P. Heinz)
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905
FORMULA
a(n) ~ 2^(7*n+1) * n^(3*n) / (3^n * exp(3*n+3)). - Vaclav Kotesovec, Feb 21 2016
Recurrence: 81*(n-4)*(n-3)^2*(n-2)^3*a(n) = 27*(n-4)*(n-3)^2*(57*n^7 - 328*n^6 + 560*n^5 + 159*n^4 - 1591*n^3 + 1942*n^2 - 994*n + 192)*a(n-1) - 18*(n-4)*(n-1)^3*(2*n - 3)*(4*n - 7)*(4*n - 5)*(18*n^7 - 111*n^6 - 76*n^5 + 2183*n^4 - 6887*n^3 + 9632*n^2 - 6371*n + 1620)*a(n-2) + 24*(n-2)^3*(n-1)^4*(2*n - 5)*(2*n - 3)*(4*n - 11)*(4*n - 9)*(4*n - 7)*(4*n - 5)*(n^5 + 6*n^4 - 115*n^3 + 440*n^2 - 626*n + 288)*a(n-3) - 32*(n-3)^3*(n-2)^4*(n-1)^5*(2*n - 7)*(2*n - 5)*(2*n - 3)*(4*n - 15)*(4*n - 13)*(4*n - 11)*(4*n - 9)*(4*n - 7)*(4*n - 5)*a(n-4). - Vaclav Kotesovec, Mar 03 2016
EXAMPLE
a(2) = binomial(8,4) - 1 = 69 because there are binomial(8,4) = 70 sequences with 4 copies of 1 and 4 copies of 2 and only 22221111 does not have an increasing subsequence of length 2.
MATHEMATICA
Table[Sum[Sum[Sum[k!/(i1!*i2!*i3!*(k - i1 - i2 - i3)!)*(4*k)!/(i1 + 2*i2 + 3*i3 + 4*(k - i1 - i2 - i3))!*(-1)^(i1 + 2*i2 + 3*i3 + 4*(k - i1 - i2 - i3) - k)/(6^i1*2^i2), {i3, 0, k - i1 - i2}], {i2, 0, k - i1}], {i1, 0, k}], {k, 0, 20}] (* Vaclav Kotesovec, Mar 02 2016, after Horton and Kurn *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Feb 14 2016
STATUS
approved