login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A178381 Number of paths of length n starting at initial node of the path graph P_9. 15
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 (list; graph; refs; listen; history; text; internal format)
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.

Eric Weisstein, Trigonometric Identities, Wolfram Mathworld.

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

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) a(n)=([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; -5, 0, 5, 0]^n*[1; 1; 2; 3])[1, 1] \\ Charles R Greathouse IV, Oct 03 2016

(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

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

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

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), A178381 (P_9) and A001405 (P_infinity).

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

Sequence in context: A319436 A061551 A026034 * A037031 A056202 A001405

Adjacent sequences:  A178378 A178379 A178380 * A178382 A178383 A178384

KEYWORD

easy,nonn

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 24 16:10 EDT 2019. Contains 326295 sequences. (Running on oeis4.)