login
Number of paths of length n starting at initial node of the path graph P_9.
18

%I #41 Feb 21 2023 07:33:25

%S 1,1,2,3,6,10,20,35,70,125,250,450,900,1625,3250,5875,11750,21250,

%T 42500,76875,153750,278125,556250,1006250,2012500,3640625,7281250,

%U 13171875,26343750,47656250,95312500,172421875,344843750

%N Number of paths of length n starting at initial node of the path graph P_9.

%C Counts all paths of length n, n>=0, starting at initial node on the path graph P_9, see the Maple program.

%C The a(n) represent the number of possible chess games, ignoring the fifty-move and the triple repetition rules, after n moves by White in the following position: White Ka1, Nh1, pawns a2, b6, c2, d6, f2, g3 and g4; Black Ka8, Bc8, pawns a3, b7, c3, d7, f3 and g5.

%C The path graphs P_(2*p) have as limit(a(n+1)/a(n), n =infinity) = 2 resp. hypergeom([(p-1)/(2*p+1),(p+2)/(2*p+1)],[1/2],3/4) and the path graphs P_(2*p+1) have as limit(a(n+1)/a(n), n =infinity) = 1+cos(Pi/(p+1)), p>=1; see the crossrefs. - _Johannes W. Meijer_, Jul 01 2010

%H G. C. Greubel, <a href="/A178381/b178381.txt">Table of n, a(n) for n = 0..1000</a>

%H Johann Cigler, <a href="http://arxiv.org/abs/1501.04750">Some remarks and conjectures related to lattice paths in strips along the x-axis</a>, arXiv:1501.04750 [math.CO], 2015-2016.

%H Nachum Dershowitz, <a href="https://arxiv.org/abs/2006.06516">Between Broadway and the Hudson</a>, arXiv:2006.06516 [math.CO], 2020.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/topics/TrigonometricIdentities.html">Trigonometric Identities</a>.

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

%F G.f.: (1+x-3*x^2-2*x^3+x^4)/(1-5*x^2+5*x^4).

%F a(n) = 5*a(n-2) - 5*a(n-4) for n>=5 with a(0)=1, a(1)=1, a(2)=2, a(3)=3 and a(4)=6.

%F G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 + x / (1 - x / (1 - x / (1 + x / (1 + x)))))))). - _Michael Somos_, Feb 08 2015

%e G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 35*x^7 + 70*x^8 + ...

%p with(GraphTheory): P:=9: G:=PathGraph(P): A:= AdjacencyMatrix(G): nmax:=36; for n from 0 to nmax do B(n):=A^n; a(n):=add(B(n)[1,k],k=1..P); od: seq(a(n),n=0..nmax);

%p r := j -> (-1)^(j/10) - (-1)^(1-j/10):

%p a := k -> add((2 + r(j))*r(j)^k, j in [1, 3, 5, 7, 9])/10:

%p seq(simplify(a(n)), n=0..30); # _Peter Luschny_, Sep 18 2020

%t CoefficientList[Series[(1+x-3*x^2-2*x^3+x^4)/(1-5*x^2+5*x^4), {x,0,50}], x] (* _G. C. Greubel_, Sep 18 2018 *)

%o (PARI) x='x+O('x^50); Vec((1+x-3*x^2-2*x^3+x^4)/(1-5*x^2+5*x^4)) \\ _G. C. Greubel_, Sep 18 2018

%o (Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1+x-3*x^2-2*x^3+x^4)/(1-5*x^2+5*x^4))); // _G. C. Greubel_, Sep 18 2018

%Y This is row 9 of A094718.

%Y a(2*n) = A147748(n) and a(2*n+1) = A081567(n).

%Y a(4*n+2) = A109106(n) and a(4*n+3) = A179135(n).

%Y Cf. A000007 (P_1), A000012 (P_2), A016116 (P_3), A000045 (P_4), A038754 (P_5), A028495 (P_6), A030436 (P_7), A061551 (P_8), this sequence (P_9), A336675 (P_10), A336678 (P_11), and A001405 (P_infinity).

%Y Cf. A216212 (P_9 starting in the middle).

%Y Cf. A033191, A179131, A179132, A128052, A179133.

%K easy,nonn

%O 0,3

%A _Johannes W. Meijer_, May 27 2010, May 29 2010