login
Number of (undirected) Hamiltonian paths in the n-ladder graph K_2 X P_n.
8

%I #50 Apr 24 2024 05:19:20

%S 1,4,8,14,22,32,44,58,74,92,112,134,158,184,212,242,274,308,344,382,

%T 422,464,508,554,602,652,704,758,814,872,932,994,1058,1124,1192,1262,

%U 1334,1408,1484,1562,1642,1724,1808,1894,1982,2072,2164

%N Number of (undirected) Hamiltonian paths in the n-ladder graph K_2 X P_n.

%C Equals row sums of triangle A144336. - _Gary W. Adamson_, Sep 18 2008

%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

%H Andrew Howroyd, <a href="/A003682/b003682.txt">Table of n, a(n) for n = 1..1000</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian Path</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LadderGraph.html">Ladder Graph</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).

%F For n>1, a(n) = n^2 - n + 2 = A014206(n-1).

%F Equals binomial transform of [1, 3, 1, 1, -1, 1, -1, 1, ...]. - _Gary W. Adamson_, Apr 23 2008

%F G.f.: x(1 + x - x^2 + x^3)/(1-x)^3. - _R. J. Mathar_, Dec 16 2008

%F a(n) = floor((n^3 + 2*n)/(n+1)). - _Gary Detlefs_, Feb 20 2010

%F Except for the first term, a(n) = 2*n + a(n-1), (with a(1)=4). - _Vincenzo Librandi_, Dec 06 2010

%F a(0)=1, a(1)=4, a(2)=8, a(3)=14, a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - _Harvey P. Dale_, Jun 14 2011

%F Sum_{n>=1} 1/a(n) = 1/2 + Pi*tanh(Pi*sqrt(7)/2)/sqrt(7) = 1.686827... - _R. J. Mathar_, Apr 24 2024

%p a:=n->sum(binomial(2,2*j)+n,j=0..n): seq(a(n), n=0..46); # _Zerinvary Lajos_, Feb 22 2007

%p seq(floor((n^3+2*n)/(n+1)),n=1..47); # _Gary Detlefs_, Feb 20 2010

%t Join[{1}, Table[n^2 - n + 2, {n, 2, 50}]] (* _Harvey P. Dale_, Jun 14 2011 *)

%t Join[{1}, LinearRecurrence[{3, -3, 1}, {4, 8, 14}, 50]] (* _Harvey P. Dale_, Jun 14 2011 *)

%o (PARI) a(n)=if(n>1, n^2-n+2, 1) \\ _Charles R Greathouse IV_, Jan 05 2018

%Y Row n=2 of A332307.

%Y Equals A002061(n) + 1, n > 1.

%Y Cf. A144336. - _Gary W. Adamson_, Sep 18 2008

%K nonn,easy

%O 1,2

%A _Frans J. Faase_