A094113 Total area of all 1-histograms of length n.

1, 7, 44, 268, 1609, 9583, 56792, 335448, 1976689, 11627735, 68308580, 400870468, 2350563097, 13773547487, 80663415344, 472175746096, 2762854639585, 16160861104423, 94502471413916, 552472329537660

Offset: 1

Author

Ralf Stephan, May 03 2004

Keywords

• nonn

Comments

Arises in analysis of first-come-first-served (FCFS) printer policy.

Links

• Fung Lam, Table of n, a(n) for n = 1..1300
• D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001.
• D. Merlini, R. Sprugnoli and M.C. Verri, Waiting patterns for a printer, Discrete Applied Mathematics, Volume 144, 359-373, 2004

Crossrefs

Cf. A001003, A035026.

Programs

Mathematica

Rest[CoefficientList[Series[(1+x-Sqrt[1-6*x+x^2])/(4*(1-6*x+x^2)), {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 23 2014 *)

Formula

G.f.: (1+x-sqrt(1-6*x+x^2))/(4*(1-6*x+x^2)).

Recurrence: (n+1)*a(n) = (8-n)*a(n-10) + 3*(10*n-71)*a(n-9) + (2263-365*n)*a(n-8) + 4*(570*n-3021)*a(n-7) + 2*(16654-3785*n)*a(n-6) + 6138*(2*n-7)*a(n-5) + 2*(9841-3785*n)*a(n-4) + 4*(570*n-969)*a(n-3) + (292-365*n)*a(n-2) + 3*(10*n+1)*a(n-1), n>=10. - Fung Lam, Feb 07 2014

Recurrence (of order 4): n*a(n) = 3*(4*n-3)*a(n-1) - 19*(2*n-3)*a(n-2) + 3*(4*n-9)*a(n-3) - (n-3)*a(n-4). - Vaclav Kotesovec, Feb 23 2014

a(n) ~ (sqrt(2)-1)/8 * (3+2*sqrt(2))^(n+1). - Vaclav Kotesovec, Feb 23 2014