A126126 -id:A126126 - cp's OEIS frontend

A110877 Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0) = 1, T(n,k) = 0 if n= 1: T(n,k) = T(n-1,k-1) + x*T(n-1,k) + T(n-1,k+1) with x = 3.

1, 1, 1, 2, 4, 1, 6, 15, 7, 1, 21, 58, 37, 10, 1, 79, 232, 179, 68, 13, 1, 311, 954, 837, 396, 108, 16, 1, 1265, 4010, 3861, 2133, 736, 157, 19, 1, 5275, 17156, 17726, 10996, 4498, 1226, 215, 22, 1, 22431, 74469, 81330, 55212, 25716, 8391, 1893

Offset: 0

Philippe Deléham, Sep 19 2005

Similar to A064189 (x = 1) and to A039599 (x = 2).
This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k >= 1. Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007
Row sums yield A126568. - Philippe Deléham, Oct 10 2007
5^n = (n-th row terms) dot (first n+1 terms in the series (1, 4, 7, 10, ...)). Example for row 4: 5^4 = 625 = (21, 58, 37, 10, 1) dot (1, 4, 7, 10, 13) = (21 + 232 + 259 + 100 + 13). - Gary W. Adamson, Jun 15 2011
Riordan array (2/(1+x+sqrt(1-6*x+5*x^2)), (1-3*x-sqrt(1-6*x+5*x^2))/(2*x)). - Philippe Deléham, Mar 04 2013

			Triangle begins:
      1;
      1,     1;
      2,     4,     1;
      6,    15,     7,     1;
     21,    58,    37,    10,     1;
     79,   232,   179,    68,    13,    1;
    311,   954,   837,   396,   108,   16,    1;
   1265,  4010,  3861,  2133,   736,  157,   19,   1;
   5275, 17156, 17726, 10996,  4498, 1226,  215,  22,  1;
  22431, 74469, 81330, 55212, 25716, 8391, 1893, 282, 25, 1;
  ...
From _Philippe Deléham_, Nov 07 2011: (Start)
Production matrix begins:
  1, 1;
  1, 3, 1;
  0, 1, 3, 1;
  0, 0, 1, 3, 1;
  0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 0, 1, 3, 1;
  0, 0, 0, 0, 0, 0, 0, 1, 3, 1;
  ... (End)

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Cf. A002212, A033321, A039599, A064189.

The inverse of A126126.

A110877 := proc(n,k)
    if k > n then
        0;
    elif n= 0 then
        1;
    elif k = 0 then
        procname(n-1,0)+procname(n-1,1) ;
    else
        procname(n-1,k-1)+3*procname(n-1,k)+procname(n-1,k+1) ;
    end if;
end proc: # R. J. Mathar, Sep 06 2013

T[0, 0, x_, y_] := 1; T[n_, 0, x_, y_] := x*T[n - 1, 0, x, y] + T[n - 1, 1, x, y]; T[n_, k_, x_, y_] := T[n, k, x, y] = If[k < 0 || k > n, 0, T[n - 1, k - 1, x, y] + y*T[n - 1, k, x, y] + T[n - 1, k + 1, x, y]]; Table[T[n, k, 1, 3], {n, 0, 49}, {k, 0, n}] // Flatten (* G. C. Greubel, Apr 21 2017 *)

T(n, 0) = A033321(n) and for k >= 1: T(n, k) = Sum_{j>=1} T(n-j, k-1)*A002212(j).
Sum_{k=0..n} T(m, k)*T(n, k) = T(m+n, 0) = A033321(m+n).
The triangle may also be generated from M^n * [1,0,0,0,...], where M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and (1,3,3,3,...) in the main diagonal. - Gary W. Adamson, Dec 17 2006
Sum_{k=0..n} T(n,k)*(3*k+1) = 5^n. - Philippe Deléham, Feb 26 2007
Sum_{k=0..n} T(n,k) = A126568(n). - Philippe Deléham, Oct 10 2007

A238731 Riordan array ((1-2x)/(1-3x+x^2), x/(1-3*x+x^2)).

Original entry on oeis.org

1, 1, 1, 2, 4, 1, 5, 13, 7, 1, 13, 40, 33, 10, 1, 34, 120, 132, 62, 13, 1, 89, 354, 483, 308, 100, 16, 1, 233, 1031, 1671, 1345, 595, 147, 19, 1, 610, 2972, 5561, 5398, 3030, 1020, 203, 22, 1, 1597, 8495, 17984, 20410, 13893, 5943, 1610, 268, 25, 1, 4181

Offset: 0

Philippe Deléham, Mar 03 2014

Unsigned version of A124037 and A126126.
Subtriangle of the triangle given by (0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (1, 0, 2, -2, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938.
Row sums are A001075(n).
Diagonal sums are A133494(n).
Sum_{k=0..n} T(n,k)*x^k = A001519(n), A001075(n), A002320(n), A038723(n), A033889(n) for x = 0, 1, 2, 3, 4 respectively. - Philippe Deléham, Mar 05 2014

			Triangle begins:
1;
1, 1;
2, 4, 1;
5, 13, 7, 1;
13, 40, 33, 10, 1;
34, 120, 132, 62, 13, 1;
89, 354, 483, 308, 100, 16, 1;
233, 1031, 1671, 1345, 595, 147, 19, 1;...
Triangle (0, 1, 1, 1, 0, 0, 0, ...) DELTA (1, 0, 2, -2, 0, 0, ...) begins:
1;
0, 1;
0, 1, 1;
0, 2, 4, 1;
0, 5, 13, 7, 1;
0, 13, 40, 33, 10, 1;
0, 34, 120, 132, 62, 13, 1;
0, 89, 354, 483, 308, 100, 16, 1;
0, 233, 1031, 1671, 1345, 595, 147, 19, 1;...

Cf. A001519, A000012, A016777, A062708.

Cf. A001906, A124037, A126126.

(* The function RiordanArray is defined in A256893. *)
RiordanArray[(1-2#)/(1-3#+#^2)&, x/(1-3#+#^2)&, 10] // Flatten (* Jean-François Alcover, Jul 16 2019 *)

T(n,k) = 3*T(n-1,k) + T(n-1,k-1) - T(n-2,k), T(0,0) = T(1,0) = T(1,1) = 1, T(n,k) = 0 if k<0 or if k>n.

G.f.: (1-2*x)/(1-(y+3)*x+x^2). - Philippe Deléham, Mar 05 2014

A124037 Triangle read by rows: row n gives coefficients of increasing powers of x in characteristic polynomial of the matrix (-1)^n*M_n, where M_n is the tridiagonal matrix defined in the Comments line.

Original entry on oeis.org

1, 1, -1, 2, -4, 1, 5, -13, 7, -1, 13, -40, 33, -10, 1, 34, -120, 132, -62, 13, -1, 89, -354, 483, -308, 100, -16, 1, 233, -1031, 1671, -1345, 595, -147, 19, -1, 610, -2972, 5561, -5398, 3030, -1020, 203, -22, 1, 1597, -8495, 17984, -20410, 13893, -5943, 1610, -268, 25, -1, 4181, -24110, 56886, -73816, 59059

Offset: 0

Gary W. Adamson and Roger L. Bagula, Nov 03 2006

The matrices M_n for n=1, 2, 3, ... are:
1 X 1 {{1}},
2 X 2 {{1, -1}, {-1, 3}},
3 X 3 {{1, -1, 0}, {-1, 3, -1}, {0, -1, 3}},
4 X 4 {{1, -1, 0, 0}, {-1, 3, -1, 0}, {0, -1, 3, -1}, {0, 0, -1, 3}},
5 X 5 {{1, -1, 0, 0, 0}, {-1, 3, -1, 0, 0}, {0, -1, 3, -1, 0}, {0, 0, -1, 3, -1}, {0, 0, 0, -1, 3}},
6 X 6 {{1, -1, 0, 0, 0, 0}, {-1, 3, -1, 0, 0, 0}, {0, -1, 3, -1, 0, 0}, {0, 0, -1, 3, -1, 0}, { 0, 0, 0, -1, 3, -1}, {0, 0, 0, 0, -1, 3}}, ...
Subtriangle of the triangle given by (0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (1, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Mar 04 2014
Riordan array ((1-2*x)/(1-3*x+x^2), -x/(1-3*x+x^2)). - Philippe Deléham, Mar 04 2014

			Triangle begins:
{1},
{1, -1},
{2, -4, 1},
{5, -13, 7, -1},
{13, -40, 33, -10, 1},
{34, -120,132, -62, 13, -1},
{89, -354, 483, -308, 100, -16, 1},
For example, the characteristic polynomial of M_3 is x^3-7*x^2+13*x-5, so row 3 is 5, -13, 7, -1.
Triangle (0, 1, 1, 1, 0, 0, 0, ...) DELTA (1, -2, 0, 0, 0, ...) begins:
1;
0, 1;
0, 1, -1;
0, 2, -4, 1;
0, 5, -13, 7, -1;
0, 13, -40, 33, -10, 1;
0, 34, -120, 132, -62, 13, -1;
0, 89, -354, 483, -308, 100, -16, 1; - _Philippe Deléham_, Mar 04 2014

Cf. A126126.

T[n_, m_, d_] := If[ n == m && n > 1 && m > 1, 3, If[n == m - 1 || n == m + 1, -1, If[n == m == 1, 1, 0]]] M[d_] := Table[T[n, m, d], {n, 1, d}, {m, 1, d}] Table[M[d], {d, 1, 10}] Table[Det[M[d]], {d, 1, 10}] Table[Det[M[d] - x*IdentityMatrix[d]], {d, 1, 10}] a = Join[{M[1]}, Table[CoefficientList[Det[M[d] - x*IdentityMatrix[ d]], x], {d, 1, 10}]] Flatten[a] MatrixForm[a]

@CachedFunction
def T(n,k):
    if n< 0: return 0
    if n==0: return 1 if k == 0 else 0
    h = T(n-1,k) if n==1 else 3*T(n-1,k)
    return T(n-1,k-1) - T(n-2,k) - h
A124037 = lambda n,k: (-1)^n*T(n,k)
for n in (0..9): [A124037(n,k) for k in (0..n)] # Peter Luschny, Nov 20 2012

T(n,k) = 3*T(n-1,k) - T(n-1,k-1) - T(n-2,k), T(0,0) = 1, T(1,0) = 1, T(1,1) = -1, T(n,k) = 0 if k<0 or if k>n. - Philippe Deléham, Mar 04 2014

G.f.: -(-1+2*x)/(1-3*x+x^2+x*y). - R. J. Mathar, Aug 11 2015

Edited by N. J. A. Sloane, Mar 02 2008

A238846 Expansion of (1-2x)/(1-3x+x^2)^2.

Original entry on oeis.org

1, 4, 13, 40, 120, 354, 1031, 2972, 8495, 24110, 68016, 190884, 533293, 1484020, 4115185, 11375764, 31358376, 86223942, 236540915, 647556620, 1769374931, 4826148314, 13142564448, 35736448200, 97037995225, 263156279524, 712795854421, 1928547574912, 5212430732760

Offset: 0

Philippe Deléham, Mar 05 2014

Convolution of 1, 1, 2, 5, 13, ... (A001519(n)) with 1, 3, 8, 21, 55, ... (A001906(n+1)).

			a(0) = 1*1 = 1;
a(1) = 1*3 + 1*1 = 4;
a(2) = 1*8 + 1*3 + 2*1 = 13;
a(3) = 1*21 + 1*8 + 2*3 + 5*1 = 40;
a(4) = 1*55 + 1*21 + 2*8 + 5*3 + 13*1 = 120; etc. (from first recurrence formula).
a(0) = 3*0 - 0 + 1 = 1;
a(1) = 3*1 - 0 + 1 = 4;
a(2) = 3*4 - 1 + 2 = 13;
a(3) = 3*13 - 4 + 5 = 40;
a(4) = 3*40 - 13 + 13 = 120; etc (from second recurrence formula).
G.f. = 1 + 4*x + 13*x^2 + 40*x^3 + 120*x^4 + 354*x^5 + 1031*x^6 + ... - _Michael Somos_, Nov 23 2021

Michael De Vlieger, Table of n, a(n) for n = 0..2385
Sergi Elizalde, Rigoberto Flórez, and José Luis Ramírez, Enumerating symmetric peaks in non-decreasing Dyck paths, Ars Mathematica Contemporanea (2021).
David Eppstein, Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time, arXiv:2303.00147 [cs.CG], 2023, p. 20.
Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, J. Int. Seq. (2025) Vol. 28, Art. No. 25.1.6. See pp. 6, 15, 17, 19.
Valentin Ovsienko, Shadow sequences of integers, from Fibonacci to Markov and back, arXiv:2111.02553 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Cf. A000045, A001519, A001906.

Cf. A001870, A001871, A197649.

LinearRecurrence[{6, -11, 6, -1}, {1, 4, 13, 40}, 30] (* Bruno Berselli, Mar 06 2014 *)
a[ n_] := If[n < 0, SeriesCoefficient[ x^3*(2 - x)/(1 - 3*x + x^2)^2, {x, 0, -n}], SeriesCoefficient[ (1 - 2*x)/(1 - 3*x + x^2)^2, {x, 0, n}]]; (* Michael Somos, Nov 23 2021 *)

{a(n) = if(n<0, polcoeff( x^3*(2-x)/(1-3*x+x^2)^2 + x*O(x^-n), -n), polcoeff( (1-2*x)/(1-3*x+x^2)^2 + x*O(x^n), n))}; /* Michael Somos, Nov 23 2021 */

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4) for n>3, a(0)=1, a(1)=4, a(2)=13, a(3)=40.
a(n) = 3*a(n-1) - a(n-2) + A001519(n) for n>1, a(0)=1, a(1)=4.
a(n) = A238731(n+1, 1).
a(n) = -A124037(n+1, 1).
a(n) = (-1)^n*A126126(n+1, 1).
a(n) = ( (3 + sqrt(5))^(1+n)*(8 - (1 - sqrt(5))*(13 + 5*n)) + (3 - sqrt(5))^(1+n)*(8 - (1 + sqrt(5))*(13 + 5*n)) ) / (25*2^(2+n)). - Bruno Berselli, Mar 06 2014
From Philippe Deléham, Mar 06 2014: (Start)
a(n) = 2*A001870(n) - A001871(n).
a(n) = A197649(n+1) - 3*A001871(n-1).
a(n) = A001871(n) - 2*A001871(n-1). (End)
0 = 2 + a(n)*(a(n+1) - a(n+3)) + a(n+1)*(-6*a(n+1) + 12*a(n+2)) + a(n+2)*(-6*a(n+2) + a(n+3)) for all n in Z. - Michael Somos, Nov 23 2021
E.g.f.: exp(3*x/2)*(5*(5 + 4*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(17 + 10*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

cp's OEIS Frontend

A110877 Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0) = 1, T(n,k) = 0 if n= 1: T(n,k) = T(n-1,k-1) + x*T(n-1,k) + T(n-1,k+1) with x = 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A238731 Riordan array ((1-2*x)/(1-3*x+x^2), x/(1-3*x+x^2)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A124037 Triangle read by rows: row n gives coefficients of increasing powers of x in characteristic polynomial of the matrix (-1)^n*M_n, where M_n is the tridiagonal matrix defined in the Comments line.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A238846 Expansion of (1-2*x)/(1-3*x+x^2)^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A238731 Riordan array ((1-2x)/(1-3x+x^2), x/(1-3*x+x^2)).

A238846 Expansion of (1-2x)/(1-3x+x^2)^2.