A003682 - hamilton paths - comments and (possibly constructive) criticism..

[Ralf Stephan]

> > the web page gives the recurrence
> >
> >   C(n) = 3C(n-1) - 3C(n-2) + C(n-3), C(1)=1, C(2)=4, C(3)=8
> >
> > whose solution is
> >
> >   C(n) = (n^2+3n-2)/2
> 
> Actually there is no problem with the recurrence or the formula - the 
> only problem is C(1) which is the "odd man out" in the scheme of 
> things. If you solve the recurrence, but using C(2), C(3) and C(4) as 
> the "base cases" then you get the stated formula, which is correct for 
> all values other than C(1).

Moreover, one can see this at once: the coefficients of C in the
recurrence are 1,3,3,1, a row of Pascal's triangle, and that recurrence
can therefore generate *any* polynomial of degree 2, just depending on
the start values. This generalizes to any recurrence with coefficients
a Pascal row.


ralf