A268847 Number of sequences with 4 copies each of 1,2,...,n and longest increasing subsequence of length n.

1, 1, 69, 31451, 46922017, 162588279629, 1077273394836829, 12084070123028603391, 211301962987912098409729, 5426679072605204732028894233, 195676681342450229063393365876181, 9562449832974304724626743446267704131, 615516610914323638585463757154352054695009

Offset: 0

Author

Alois P. Heinz, Feb 14 2016

Keywords

• nonn

Examples

			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.
		

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

Crossrefs

Row n=4 of A047909.

Programs

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

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