A107839 -id:A107839 - cp's OEIS frontend

A106709 Expansion of g.f. -2x/(1 - 5x + 2*x^2).

0, -2, -10, -46, -210, -958, -4370, -19934, -90930, -414782, -1892050, -8630686, -39369330, -179585278, -819187730, -3736768094, -17045465010, -77753788862, -354678014290, -1617882493726, -7380056440050, -33664517212798, -153562473183890, -700483331493854

Offset: 0

Roger L. Bagula, May 30 2005

Let T(n,k) denote the k-th element of row n of Stern's triangle (see A337277). Then b(n) = Sum_k T(n,k)*T(n,k+1) gives the present sequence (without the signs). - N. J. A. Sloane, Nov 19 2020

G. C. Greubel, Table of n, a(n) for n = 0..1000
Richard P. Stanley, Some Linear Recurrences Motivated by Stern's Diatomic Array, arXiv:1901.04647 [math.CO], 2019. Also American Mathematical Monthly 127.2 (2020): 99-111.
Index entries for linear recurrences with constant coefficients, signature (5,-2).

Cf. A107839, A337277.

I:=[0,-2]; [n le 2 select I[n] else 5*Self(n-1) - 2*Self(n-2): n in [1..41]]; // G. C. Greubel, Sep 10 2021

a:= n-> (<<0|-2>, <1|5>>^n)[1,2]:
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 19 2020

LinearRecurrence[{5,-2}, {0,-2}, 41] (* G. C. Greubel, Sep 10 2021 *)

[-round(sqrt(2)^(n+1)*chebyshev_U(n-1, 5/(2*sqrt(2)))) for n in (0..40)] # G. C. Greubel, Sep 10 2021

a(n) = -2*A107839(n-1), n>0.
a(n) = first entry of v(n), where v(n) = M*v(n-1), M is the 2 X 2 matrix ({0, -2}, {1, 5}) and v(0) is the column vector (0, 1).
G.f.: -2*x/(1-5*x+2*x^2). - Alois P. Heinz, Nov 26 2020
a(n) = -sqrt(2)^(n+1)*ChebyshevU(n-1, 5/(2*sqrt(2))). - G. C. Greubel, Sep 10 2021

Edited by N. J. A. Sloane, Apr 30 2006

New name by G. C. Greubel, Sep 10 2021

A152268 Expansion of g.f. x/(1-7x+8x^2).

Original entry on oeis.org

0, 1, 7, 41, 231, 1289, 7175, 39913, 221991, 1234633, 6866503, 38188457, 212387175, 1181202569, 6569320583, 36535623529, 203194800039, 1130078612041, 6284991883975, 34954314291497, 194400264968679, 1081167340448777

Offset: 0

Roger L. Bagula, Dec 01 2008

Binomial transform of 0, 1, 5, 23, 105, ... (A107839 with an additional initial term 0) and second binomial transform of 0, 1, 3, 11, 39, ... (A007482 with an additional initial term 0). - Klaus Purath, Sep 09 2024

Index entries for linear recurrences with constant coefficients, signature (7,-8).

[lucas_number1(n,7,8) for n in range(0, 22)] # Zerinvary Lajos, Apr 23 2009

From R. J. Mathar, Dec 04 2008: (Start)
a(n) = 7*a(n-1) - 8*a(n-2).
G.f.: x/(1-7*x+8*x^2). (End)

A159289 a(n+1) = 5a(n) - 2a(n-1).

Original entry on oeis.org

5, 21, 95, 433, 1975, 9009, 41095, 187457, 855095, 3900561, 17792615, 81161953, 370224535, 1688798769, 7703544775, 35140126337, 160293542135, 731187458001, 3335350205735, 15214376112673, 69401180151895, 316577148534129

Offset: 0

Creighton Dement, Apr 08 2009

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5, -2).

Cf. A107839.

I:=[5, 21]; [n le 2 select I[n] else 5*Self(n-1) - 2*Self(n-2): n in [1..30]]; // G. C. Greubel, Jun 27 2018

LinearRecurrence[{5, -2}, {5, 21}, 50] (* G. C. Greubel, Jun 27 2018 *)

x='x+O('x^30); Vec(-(-5+4*x)/(1-5*x+2*x^2)) \\ G. C. Greubel, Jun 27 2018

From R. J. Mathar, Apr 10 2009: (Start)
G.f.: -(-5+4*x)/(1-5*x+2*x^2).
a(n) = 5*A107839(n) - 4*A107839(n-1). (End)

A193727 Mirror of the triangle A193726.

Original entry on oeis.org

1, 2, 1, 10, 9, 2, 50, 65, 28, 4, 250, 425, 270, 76, 8, 1250, 2625, 2200, 920, 192, 16, 6250, 15625, 16250, 9000, 2800, 464, 32, 31250, 90625, 112500, 77500, 32000, 7920, 1088, 64, 156250, 515625, 743750, 612500, 315000, 103600, 21280, 2496, 128

Offset: 0

Clark Kimberling, Aug 04 2011

This triangle is obtained by reversing the rows of the triangle A193726.

Triangle T(n,k), read by rows, given by (2,3,0,0,0,0,0,0,0,...) DELTA (1,1,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 05 2011

			First six rows:
     1;
     2,    1;
    10,    9,    2;
    50,   65,   28,   4;
   250,  425,  270,  76,   8;
  1250, 2625, 2200, 920, 192; 16;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A011782, A015535, A020699, A081040, A084938.

Cf. A107839, A133494, A169634, A193722, A193726.

function T(n, k) // T = A193727
  if k lt 0 or k gt n then return 0;
  elif n lt 2 then return n-k+1;
  else return 5*T(n-1, k) + 2*T(n-1, k-1);
  end if;
end function;
[T(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Dec 02 2023

(* First program *)
z = 8; a = 1; b = 2; c = 1; d = 2;
p[n_, x_] := (a*x + b)^n ; q[n_, x_] := (c*x + d)^n
t[n_, k_] := Coefficient[p[n, x], x^k]; t[n_, 0] := p[n, x] /. x -> 0;
w[n_, x_] := Sum[t[n, k]*q[n + 1 - k, x], {k, 0, n}]; w[-1, x_] := 1
g[n_] := CoefficientList[w[n, x], {x}]
TableForm[Table[Reverse[g[n]], {n, -1, z}]]
Flatten[Table[Reverse[g[n]], {n, -1, z}]]  (* A193726 *)
TableForm[Table[g[n], {n, -1, z}]]
Flatten[Table[g[n], {n, -1, z}]]  (* A193727 *)
(* Second program *)
T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[n<2, n-k+1, 5*T[n-1, k] + 2*T[n-1, k-1]]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Dec 02 2023 *)

def T(n, k): # T = A193727
    if (k<0 or k>n): return 0
    elif (n<2): return n-k+1
    else: return 5*T(n-1, k) + 2*T(n-1, k-1)
flatten([[T(n, k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Dec 02 2023

T(n,k) = A193726(n,n-k).
T(n,k) = 2*T(n-1,k-1) + 5*T(n-1,k) with T(0,0)=T(1,1)=1 and T(1,0)=2. - Philippe Deléham, Oct 05 2011
G.f.: (1-3*x-x*y)/(1-5*x-2*x*y). - R. J. Mathar, Aug 11 2015
From G. C. Greubel, Dec 02 2023: (Start)
T(n, 0) = A020699(n).
T(n, 1) = A081040(n-1).
T(n, n) = A011782(n).
Sum_{k=0..n} T(n, k) = A169634(n-1) + (4/7)*[n=0].
Sum_{k=0..n} (-1)^k * T(n, k) = A133494(n).
Sum_{k=0..floor(n/2)} T(n-k, k) = 2*A015535(n) + A015535(n-1) + (1/2)*[n=0].
Sum_{k=0..floor(n/2)} (-1)^k * T(n-k, k) = 2*A107839(n-1) - A107839(n-2) + (1/2)*[n=0]. (End)

A359987 Number of edge cuts in the n-ladder graph P_2 X P_n.

Original entry on oeis.org

1, 11, 105, 919, 7713, 63351, 514321, 4148839, 33347041, 267489431, 2143168305, 17160184519, 137349160833, 1099102033911, 8794224638161, 70360221445159, 562911076526881, 4503422288363351, 36027988077717105, 288226686123491719, 2305826176955087553, 18446667292472959671

Offset: 1

Andrew Howroyd, Jan 28 2023

Andrew Howroyd, Table of n, a(n) for n = 1..500
Eric Weisstein's World of Mathematics, Edge Cut.
Eric Weisstein's World of Mathematics, Ladder Graph.
Index entries for linear recurrences with constant coefficients, signature (13,-42,16).

Row 2 of A359990.
Cf. A013730, A107839, A356828 (vertex cuts), A359989.
Cf. A359621, A359622.

LinearRecurrence[{13, -42, 16}, {1, 11, 105}, 25] (* Paolo Xausa, Jun 24 2024 *)
Table[2^(3 n - 2) + (((5 - Sqrt[17])/2)^n - ((5 + Sqrt[17])/2)^n)/Sqrt[17], {n, 20}] // Expand (* Eric W. Weisstein, Nov 03 2024 *)
CoefficientList[Series[-(1 - 2 x + 4 x^2)/((-1 + 8 x) (1 - 5 x + 2 x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Nov 03 2024 *)

Vec((1 - 2*x + 4*x^2)/((1 - 8*x)*(1 - 5*x + 2*x^2)) + O(x^25))

a(n) = 13*a(n-1) - 42*a(n-2) + 16*a(n-3) for n > 3.
a(n) = A013730(n-1) - A107839(n-1).
G.f.: x*(1 - 2*x + 4*x^2)/((1 - 8*x)*(1 - 5*x + 2*x^2)).

A109165 a(n) = 5a(n-2) - 2a(n-4), n >= 4.

Original entry on oeis.org

1, 2, 5, 10, 23, 46, 105, 210, 479, 958, 2185, 4370, 9967, 19934, 45465, 90930, 207391, 414782, 946025, 1892050, 4315343, 8630686, 19684665, 39369330, 89792639, 179585278, 409593865, 819187730, 1868384047, 3736768094, 8522732505

Offset: 0

Creighton Dement, Aug 18 2005

Floretion Algebra Multiplication Program, FAMP Code: 4kbaseksigcycsumseq[ - .25'i - .25i' + .25'ii' + .25'jj' + .25'kk' + .25'jk' + .25'kj' + .25e], sumtype: (Y[15], *, vesy)

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

Cf. A107839, A106709, A005824, A054486.

a(2n) = A107839(n), a(2n+1) = A106709(n+1), a(n) - a(n-1) = A005824(n+2).

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

A340309 Number of ordered pairs of vertices which have two different shortest paths between them in the n-Hanoi graph (3 pegs, n discs).

Original entry on oeis.org

0, 6, 48, 282, 1476, 7302, 35016, 164850, 767340, 3546366, 16315248, 74837802, 342621396, 1566620022, 7157423256, 32682574050, 149184117180, 680813718126, 3106475197248, 14173073072922, 64659388538916, 294971717255142, 1345602571317096, 6138257708432850

Offset: 1

Kevin Ryde, Jan 04 2021

Vertices of the Hanoi graph are configurations of discs on pegs in the Towers of Hanoi puzzle.  Edges are a move of a disc from one peg to another.
The shortest path between a pair of vertices u,v may be unique, or there may be 2 different paths.  a(n) is the number of vertex pairs with 2 shortest paths.  Pairs are ordered, so both u,v and v,u are counted.
For a given vertex u, Hinz et al. characterize and count the destinations v which have 2 shortest paths.  Their total x_n is the number of vertex pairs in the graph of n+1 discs.  The present sequence is for n discs so a(n) = x_{n-1}.

			For n=3 discs, the Hanoi graph is
                *           \
               / \          | top
              A---*         | subgraph,
             /     \        | of n-1 = 2
            B       *       | discs
           / \     / \      |
          C---D---E---*     /
         /             \          two shortest
        *               *           paths for
       / \             / \           A to S
      *---*           *---*          B to T
     /     \         /     \         C to R
    *       *       R       *        C to U
   / \     / \     / \     / \       D to S
  *---*---*---*---S---T---U---*
Going from the top subgraph down to the bottom right subgraph, there are 5 vertex pairs with two shortest paths.  C to R goes around the middle 12-cycle either right or left, and likewise D to S.  The other pairs also go each way around the middle.  There are 6 ordered pairs of n-1 subgraphs repeating these 5 pairs.
Within the n-1 = 2 disc top subgraph, A and E are in separate n-2 subgraphs (unit triangles) and they are the only pair with two shortest paths.  Again 6 combinations of these, and in 3 subgraphs.  Total a(3) = 6*5 + 6*3*1 = 48.

Kevin Ryde, Table of n, a(n) for n = 1..500
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Daniele Parisse, and Ciril Petr, Metric Properties of the Tower of Hanoi Graphs and Stern's Diatomic Sequence, European Journal of Combinatorics, volume 26, 2005, pages 693-708. See proposition 3.9.
Index entries for linear recurrences with constant coefficients, signature (8,-17,6).
Index entries for sequences related to Towers of Hanoi

Cf. A052984, A107839.

my(p=Mod('x, 'x^2-5*'x+2)); a(n) = (vecsum(Vec(lift(p^(n+1)))) - 3^n)*3/2;

With P = (5 + sqrt(17))/2 = A082486, and M = (5 - sqrt(17))/2:
a(n) = (3/(4*sqrt(17)))*( (sqrt(17)+1)*P^n - 2*sqrt(17)*3^n + (sqrt(17)-1)*M^n ). [Hinz et al.]
a(n) = (6/sqrt(17)) * Sum_{k=0..n-1} 3^k * (P^(n-1-k) - M^(n-1-k)) [Hinz et al.].
a(n) = 3*a(n-1) + 6*A107839(n-2), paths within and between subgraphs n-1.
a(n) = 8*a(n-1) - 17*a(n-2) + 6*a(n-3).
a(n) = (A052984(n) - 3^n)*3/2.
G.f.: 6*x^2/((1 - 5*x + 2*x^2)*(1 - 3*x)).
G.f.: (3/2 - 3*x)/(1 - 5*x + 2*x^2) - (3/2)/(1 - 3*x).

A106835 Expansion of 2x^2(-2+9x+3x^2)/((2x^2+5x-1)(2x^2-5*x+1)).

Original entry on oeis.org

0, 4, 22, 114, 590, 3066, 15998, 83786, 440270, 2320314, 12260382, 64931114, 344562670, 1831630106, 9751275838, 51981730186, 277413656590, 1481919831674, 7922862005342, 42388551182314, 226923616315950, 1215450062928346

Offset: 1

Roger L. Bagula, May 30 2005

Index entries for linear recurrences with constant coefficients, signature (10,-25,0,4).

M = {{0, 0, 0, 2}, {1, 5, 0, 0}, {0, 2, 0, 0}, {0, 0, 1, 5}};
v[1] = {0, 1, 1, 2};
v[n_] := v[n] = M.v[n - 1];
a = Table[v[n][[1]], {n, 1, 50}]
LinearRecurrence[{10,-25,0,4},{0,4,22,114},30] (* Harvey P. Dale, Jul 05 2025 *)

From R. J. Mathar_, Apr 07 2009: (Start)
G.f.: 2*x^2*(-2+9*x+3*x^2)/((2*x^2+5*x-1)*(2*x^2-5*x+1)).
a(n)=(-7*A107839(n)+33*A107839(n-1)+A015535(n+1)-3*A015535(n))/4.
a(n) = 10*a(n-1)-25*a(n-2)+4*a(n-4).  (End)

Edited by Associate Editors of the OEIS, Apr 05 2009

Meaningful name from Joerg Arndt, Dec 26 2022

A191897 Coefficients of the Z(n,x) polynomials; Z(0,x) = 1, Z(1,x) = x and Z(n,x) = xZ(n-1,x) - 2Z(n-2,x), n >= 2.

Original entry on oeis.org

1, 1, 0, 1, 0, -2, 1, 0, -4, 0, 1, 0, -6, 0, 4, 1, 0, -8, 0, 12, 0, 1, 0, -10, 0, 24, 0, -8, 1, 0, -12, 0, 40, 0, -32, 0, 1, 0, -14, 0, 60, 0, -80, 0, 16, 1, 0, -16, 0, 84, 0, -160, 0, 80, 0, 1, 0, -18, 0, 112, 0, -280, 0, 240, 0, -32

Offset: 0

Paul Curtz, Jun 19 2011

The coefficients of the Z(n,x) polynomials by decreasing exponents, see the formulas, define this triangle.

			The first few rows of the coefficients of the Z(n,x) are
  1;
  1,    0;
  1,    0,   -2;
  1,    0,   -4,    0;
  1,    0,   -6,    0,    4;
  1,    0,   -8,    0,   12,    0;
  1,    0,  -10,    0,   24,    0,   -8;
  1,    0,  -12,    0,   40,    0,  -32,    0;
  1,    0,  -14,    0,   60,    0,  -80,    0,   16;
  1,    0,  -16,    0,   84,    0, -160,    0,   80,    0;

Row sums: A107920(n+1). Main diagonal: A077966(n).
Z(n,x=1) = A107920(n+1), Z(n,x=2)  = A009545(n+1),
Z(n,x=3) = A000225(n+1), Z(n,x=4)  = A007070(n),
Z(n,x=5) = A107839(n),   Z(n,x=6)  = A154244(n),
Z(n,x=7) = A186446(n),   Z(n,x=8)  = A190975(n+1),
Z(n,x=9) = A190979(n+1), Z(n,x=10) = A190869(n+1).
Row sum without sign: A113405(n+1).
Cf. A128099, A013609.

nmax:=10: Z(0, x):=1 : Z(1, x):=x: for n from 2 to nmax do Z(n, x) := x*Z(n-1, x) - 2*Z(n-2, x) od: for n from 0 to nmax do for k from 0 to n do T(n, k) := coeff(Z(n, x), x, n-k) od: od: seq(seq(T(n, k), k=0..n), n=0..nmax); # Johannes W. Meijer, Jun 27 2011, revised Nov 29 2012

a[n_, k_] := If[OddQ[k], 0, 2^(k/2)*Coefficient[ ChebyshevU[n, x/2], x, n-k]]; Flatten[ Table[ a[n, k], {n, 0, 10}, {k, 0, n}]] (* Jean-François Alcover, Aug 02 2012, from 2nd formula *)

Z(0,x) = 1, Z(1,x) = x and Z(n,x) = x*Z(n-1,x) - 2*Z(n-2,x), n >= 2.

a(n,k) = A077957(k) * A053119(n,k). - Paul Curtz, Sep 30 2011

Edited and information added by Johannes W. Meijer, Jun 27 2011

cp's OEIS Frontend

A106709 Expansion of g.f. -2*x/(1 - 5*x + 2*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A152268 Expansion of g.f. x/(1-7*x+8*x^2).

Views

Author

Keywords

Comments

Links

Programs

Sage

Formula

A159289 a(n+1) = 5*a(n) - 2*a(n-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A193727 Mirror of the triangle A193726.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A359987 Number of edge cuts in the n-ladder graph P_2 X P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A109165 a(n) = 5*a(n-2) - 2*a(n-4), n >= 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A340309 Number of ordered pairs of vertices which have two different shortest paths between them in the n-Hanoi graph (3 pegs, n discs).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A106835 Expansion of 2*x^2*(-2+9*x+3*x^2)/((2*x^2+5*x-1)*(2*x^2-5*x+1)).

Views

Author

A106709 Expansion of g.f. -2x/(1 - 5x + 2*x^2).

A152268 Expansion of g.f. x/(1-7x+8x^2).

A159289 a(n+1) = 5a(n) - 2a(n-1).

A109165 a(n) = 5a(n-2) - 2a(n-4), n >= 4.

A106835 Expansion of 2x^2(-2+9x+3x^2)/((2x^2+5x-1)(2x^2-5*x+1)).

A191897 Coefficients of the Z(n,x) polynomials; Z(0,x) = 1, Z(1,x) = x and Z(n,x) = xZ(n-1,x) - 2Z(n-2,x), n >= 2.