A109106 -id:A109106 - cp's OEIS frontend

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

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

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

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

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

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.

m:=50; R:=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

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

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

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

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

A020876 a(n) = ((5+sqrt(5))/2)^n + ((5-sqrt(5))/2)^n.

Original entry on oeis.org

2, 5, 15, 50, 175, 625, 2250, 8125, 29375, 106250, 384375, 1390625, 5031250, 18203125, 65859375, 238281250, 862109375, 3119140625, 11285156250, 40830078125, 147724609375, 534472656250, 1933740234375, 6996337890625, 25312988281250, 91583251953125

Offset: 0

N. J. A. Sloane

Number of no-leaf edge-subgraphs in Moebius ladder M_n.

			G.f. = 2 + 5*x + 15*x^2 + 50*x^3 + 175*x^4 + 625*x^5 + 2250*x^6 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Santiago Alzate, Oscar Correa, and Rigoberto Flórez, Fibonacci identities from Jordan Identities, arXiv:2009.02639 [math.NT], 2020.
Noah Giansiracusa, Fibonacci, Golden Ratio, and Vector Bundles, Mathematics (2021) Vol. 9, Issue 4, 426.
J. P. McSorley, Counting structures in the Moebius ladder, Discrete Math., 184 (1998), 137-164.
Kai Wang, Fibonacci Numbers And Trigonometric Functions Outline, (2019).
Index entries for linear recurrences with constant coefficients, signature (5,-5).

Cf. A020876, A093131, A005248.

Appears in A109106. - Johannes W. Meijer, Jul 01 2010

[Floor(((5+Sqrt(5))/2)^n+((5-Sqrt(5))/2)^n): n in [0..30]]; // Vincenzo Librandi, Aug 08 2014

G:=(x,n)-> cos(x)^n+cos(3*x)^n:
seq(simplify(4^n*G(Pi/10,2*n)), n=0..22); # Gary Detlefs, Dec 05 2010

Table[Sum[LucasL[2*i] Binomial[n, i], {i, 0, n}], {n, 0, 50}] (* T. D. Noe, Sep 10 2011 *)
CoefficientList[Series[(2 - 5 x)/(1 - 5 x + 5 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 08 2014 *)
LinearRecurrence[{5,-5},{2,5},30] (* Harvey P. Dale, Mar 13 2016 *)

[lucas_number2(n,5,5) for n in range(0,24)] # Zerinvary Lajos, Jul 08 2008

Also, a(n) = (sqrt(5)*phi)^n + (sqrt(5)/phi)^n, where phi = golden ratio. - N. J. A. Sloane, Aug 08 2014
Let S(n, m)=sum(k=0, n, binomial(n, k)*fibonacci(m*k)), then for n>0 a(n)= S(2*n, 2)/S(n, 2). - Benoit Cloitre, Oct 22 2003
From R. J. Mathar, Feb 06 2010: (Start)
a(n)= 5*a(n-1) - 5*a(n-2).
G.f.: (2-5*x)/(1-5*x+5*x^2). (End)
From Johannes W. Meijer, Jul 01 2010: (Start)
Lim_{k->infinity} a(n+k)/a(k) = (A020876(n) + A093131(n)*sqrt(5))/2.
Lim_{k->infinity} A020876(n)/A093131(n) = sqrt(5). (End)
Binomial transform of A005248. - Carl Najafi, Sep 10 2011
a(n) = 2*A030191(n) - 5*A030191(n-1). - R. J. Mathar, Mar 02 2012
From Kai Wang, Dec 22 2019: (Start)
a((2*m+1)*k)/a(k) = Sum_{i=0..m-1} (-1)^(i*(k+1))*a(2*(m-i)*k) + 5^(m*k).
A093131(m+r)*A093131(n+s) + A093131(m+s)*A093131(n+r) = (2*a(m+n+r+s) - 5^(n+s)*a(m-n)*a(r-s))/5.
a(m+r)*a(n+s) - a(m+s)*a(n+r) = 5^(n+s+1)*A093131(m-n)*A093131(r-s).
a(m+r)*a(n+s) + a(m+s)*a(n+r) = 2*a(m+n+r+s) + 5^(n+s)*a(m-n)*a(r-s).
a(m+r)*a(n+s) - 5*A093131(m+s)*A093131(n+r) = 5^(n+s)*a(m-n)*a(r-s).
a(m+r)*a(n+s) + 5*A093131(m+s)*A093131(n+r) = 2*a(m+n+r+s)+ 5^(n+s+1)*A093131(m-n)*A093131(r-s).
A093131(m-n) = (A093131(m)*a(n) - a(m)*A093131(n))/(2*5^n).
A093131(m+n) = (A093131(m)*a(n) + a(m)*A093131(n))/2.
a(n)^2 - a(n+1)*a(n-1) = -5^n.
a(n)^2 - a(n+r)*a(n-r) = -5^(n-r+1)*A093131(r)^2.
a(m)*a(n+1) - a(m+1)*a(n) = -5^(n+1)*A093131(m-n).
a(m+n) - 5^(n)*a(m-n) = 5*A093131(m)*A093131(n).
a(m+n) + 5^(n)*a(m-n) =  a(m)*a(n).
a(m-n) = (a(m)*a(n) - 5*A093131(m)*A093131(n))/(2*5^n).
a(m+n) = (a(m)*a(n) + 5*A093131(m)*A093131(n))/2.  (End)
E.g.f.: 2*exp(5*x/2)*cosh(sqrt(5)*x/2). - Stefano Spezia, Dec 27 2019

Definition simplified by N. J. A. Sloane, Aug 08 2014

A039717 Row sums of convolution triangle A030523.

Original entry on oeis.org

1, 4, 15, 55, 200, 725, 2625, 9500, 34375, 124375, 450000, 1628125, 5890625, 21312500, 77109375, 278984375, 1009375000, 3651953125, 13212890625, 47804687500, 172958984375, 625771484375, 2264062500000, 8191455078125

Offset: 1

Wolfdieter Lang

Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 10 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 3, s(2n) = 5.
With offset 0 = INVERT transform of A001792: (1, 3, 8, 20, 48, 112, ...). - Gary W. Adamson, Oct 26 2010
From Tom Copeland, Nov 09 2014: (Start)
The array belongs to a family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the o.g.f. (1-sqrt(1-4x/(1+(1-t)x)))/2 and inverse x*(1-x)/(1 + (t-1)*x*(1-x)). See A091867 for more info on this family. Here t = -4 (mod signs in the results).
Let C(x) = (1 - sqrt(1-4x))/2, an o.g.f. for the Catalan numbers A000108, with inverse Cinv(x) = x*(1-x) and P(x,t) = x/(1+t*x) with inverse P(x,-t).
O.g.f.: G(x) = x*(1-x)/(1 - 5x*(1-x)) = P(Cinv(x),-5).
Inverse O.g.f.: Ginv(x) = (1 - sqrt(1 - 4*x/(1+5x)))/2 = C(P(x,5)) (signed A026378). Cf. A030528. (End)
p-INVERT of (2^n), where p(s) = 1 - s - s^2; see A289780. - Clark Kimberling, Aug 10 2017

Michel Marcus, Table of n, a(n) for n = 1..1000
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
Index entries for linear recurrences with constant coefficients, signature (5,-5).

Appears in A109106.

Cf. A000045, A000108, A001792, A005043, A091867, A026378, A030528.

CoefficientList[Series[(1 - x) / (1 - 5 x + 5 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 10 2014 *)

Vec(x*(1-x)/(1-5*x+5*x^2) + O(x^40)) \\ Altug Alkan, Nov 20 2015

G.f.: x*(1-x)/(1-5*x+5*x^2) = g1(3, x)/(1-g1(3, x)), g1(3, x) := x*(1-x)/(1-2*x)^2 (g.f. first column of A030523).
From Paul Barry, Apr 16 2004: (Start)
Binomial transform of Fibonacci(2n+2).
a(n) = (sqrt(5)/2 + 5/2)^n*(3*sqrt(5)/10 + 1/2) - (5/2 - sqrt(5)/2)^n*(3*sqrt(5)/10 - 1/2). (End)
a(n) = (1/5)*Sum_{r=1..9} sin(3*r*Pi/10)*sin(r*Pi/2)*(2*cos(r*Pi/10))^(2*n).
a(n) = 5*a(n-1) - 5*a(n-2).
a(n) = Sum_{k=0..n} Sum_{i=0..n} binomial(n, i)*binomial(k+i+1, 2k+1). - Paul Barry, Jun 22 2004
From Johannes W. Meijer, Jul 01 2010: (Start)
Limit_{k->oo} a(n+k)/a(k) = (A020876(n) + A093131(n)*sqrt(5))/2.
Limit_{n->oo} A020876(n)/A093131(n) = sqrt(5).
(End)
From Benito van der Zander, Nov 19 2015: (Start)
Limit_{k->oo} a(k+1)/a(k) = 1 + phi^2 = (5 + sqrt(5)) / 2.
a(n) = a(n-1) * 3 + A081567(n-2) (not proved).
(End)
E.g.f.: exp(x*5/2) * (cosh(x*sqrt(5)/2) + (3/sqrt(5))*sinh(x*sqrt(5)/2)). - Fabian Pereyra, Oct 29 2024

A179135 a(n) = (3-sqrt(5))((3+sqrt(5))/10)^(-n)/2+(3+sqrt(5))((3-sqrt(5))/10)^(-n)/2.

Original entry on oeis.org

3, 35, 450, 5875, 76875, 1006250, 13171875, 172421875, 2257031250, 29544921875, 386748046875, 5062597656250, 66270263671875, 867489013671875, 11355578613281250, 148646453857421875, 1945807342529296875

Offset: 0

Johannes W. Meijer, Jul 01 2010

Index entries for linear recurrences with constant coefficients, signature (15, -25).

Cf. A109106.

with(GraphTheory): nmax:=72; P:=9: G:=PathGraph(P): A:= AdjacencyMatrix(G): for n from 0 to nmax do B(n):=A^n; A178381(n):=add(B(n)[1,k],k=1..P); od: for n from 0 to nmax/4-1 do a(n):= A178381(4*n+3) od: seq(a(n),n=0..nmax/4-1);

a(n) = A178381(4*n+3).
G.f.: (3-10*z)/(1-15*z+25*z^2).
Limit(a(n+k)/a(k), k=infinity) = A000351(n)*A130196(n)/(A128052(n) - A167808(2*n)*sqrt(5)).
Limit(A128052(n)/A167808(2*n),n=infinity) = sqrt(5).
a(n) = 5^n*Lucas(2*(n+1)). - Ehren Metcalfe, Apr 22 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A020876 a(n) = ((5+sqrt(5))/2)^n + ((5-sqrt(5))/2)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A039717 Row sums of convolution triangle A030523.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A179135 a(n) = (3-sqrt(5))*((3+sqrt(5))/10)^(-n)/2+(3+sqrt(5))*((3-sqrt(5))/10)^(-n)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A179135 a(n) = (3-sqrt(5))((3+sqrt(5))/10)^(-n)/2+(3+sqrt(5))((3-sqrt(5))/10)^(-n)/2.