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

[Gordon Royle]

>
> The default product I normally take to be Cartesian. But it wouldn't 
> hurt
> to help us out by adding "Cartesian".
>
> Another name for these would be ladder graphs.

Better be careful here.. the "ladder" is a well-known graph which is 
the Cartesian product of K_2 and a *cycle* not a path..

>> e the comment could be
>> upgraded to a "formula".
>
> 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).

C(1) counts hamilton paths in K_2 and according to the formula it 
"wants" to be equal to 2, but collapses to 1 in this small case.

Gordon