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

1, 1, 2, 3, 6, 10, 20, 35, 70, 125, 250, 450, 900, 1625, 3250, 5875, 11750, 21250, 42500, 76875, 153750, 278125, 556250, 1006250, 2012500, 3640625, 7281250, 13171875, 26343750, 47656250, 95312500, 172421875, 344843750

Offset

0,3

Comments

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

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.

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

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.

Nachum Dershowitz, Between Broadway and the Hudson, arXiv:2006.06516 [math.CO], 2020.

Eric Weisstein's World of Mathematics, Trigonometric Identities.

Index entries for linear recurrences with constant coefficients, signature (0,5,0,-5).

Formula

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

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.

G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 + x / (1 - x / (1 - x / (1 + x / (1 + x)))))))). - Michael Somos, Feb 08 2015

Example

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 + ...

Maple

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);
r := j -> (-1)^(j/10) - (-1)^(1-j/10):
a := k -> add((2 + r(j))*r(j)^k, j in [1, 3, 5, 7, 9])/10:
seq(simplify(a(n)), n=0..30); # Peter Luschny, Sep 18 2020

Mathematica

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 *)

Prog

(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
(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

Crossrefs

This is row 9 of A094718.

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

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

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).

Cf. A216212 (P_9 starting in the middle).

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

Sequence in context: A319436 A061551 A026034 * A037031 A336675 A336678

Adjacent sequences: A178378 A178379 A178380 * A178382 A178383 A178384

Keyword

easy,nonn

Author

Johannes W. Meijer, May 27 2010, May 29 2010

Status

approved