A086828 a(1) = 0, a(2) = 1, a(3) = 1, a(4) = 7; thereafter, a(n) = a(n-1) + (n-1)*a(n-2).

0, 1, 1, 7, 11, 46, 112, 434, 1330, 5236, 18536, 76132, 298564, 1288280, 5468176, 24792376, 112283192, 533753584, 2554851040, 12696169136, 63793189936, 330412741792, 1733862920384, 9333355981600, 50946066070816

Offset

1,4

Comments

Number of states in a dynamic programming algorithm for the traveling salesman problem on graphs of bandwidth n (Gilmore et al., 1985).

These numbers obey the same recurrence as A000085 but with different initial conditions (Rote, 1992).

References

P. C. Gilmore et al., Well-solved special cases, pp. 87-143 of E. L. Lawler et al., eds., The Traveling Salesman Problem, Wiley, 1985.

G. Rote, The N-line traveling salesman problem, Networks 22 (1992), 91-108.

Links

G. C. Greubel, Table of n, a(n) for n = 1..799

Formula

E.g.f.: -5/2 + x/2 - x^2/2 + exp(x*(2+x)/2)/2 * (5 + 3*sqrt(2*Pi) * exp(1/2) * erf(1/sqrt(2)) - 3*sqrt(2*Pi) * exp(1/2) * erf((1+x)/sqrt(2))). - Vaclav Kotesovec, May 05 2015

a(n) ~ (5*sqrt(2) - 6*sqrt(Pi)*exp(1/2)*(1-erf(1/sqrt(2))))/4 * exp(sqrt(n)-n/2-1/4) * n^(n/2) * (1 + 7/(24*sqrt(n))). - Vaclav Kotesovec, May 05 2015

Mathematica

Flatten[{0, 1, RecurrenceTable[{a[3]==1, a[4]==7, a[n]==a[n-1]+(n-1)*a[n-2]}, a, {n, 3, 20}]}] (* Vaclav Kotesovec, May 05 2015 *)
Rest[CoefficientList[Series[-5/2 + x/2 - x^2/2 + E^(x*(2 + x)/2)/2 * (5 + 3*Sqrt[2*E*Pi]*Erf[1/Sqrt[2]] - 3*Sqrt[2*E*Pi]*Erf[(1 + x)/Sqrt[2]]), {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, May 05 2015 *)
nxt[{n_, a_, b_}]:={n+1, b, b+a*n}; Join[{0, 1}, NestList[nxt, {4, 1, 7}, 30][[All, 2]]] (* Harvey P. Dale, Mar 09 2022 *)

Crossrefs

Cf. A000085.

Sequence in context: A129865 A153377 A062209 * A117392 A105867 A166653

Adjacent sequences: A086825 A086826 A086827 * A086829 A086830 A086831

Keyword

nonn,easy

Author

N. J. A. Sloane, Aug 08 2003

Extensions

More terms from David Wasserman, Apr 01 2005

Status

approved