A080938 -id:A080938 - cp's OEIS frontend

A080937 Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps with all values <= 5.

1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, 45542, 147798, 479779, 1557649, 5057369, 16420730, 53317085, 173118414, 562110290, 1825158051, 5926246929, 19242396629, 62479659622, 202870165265, 658715265222, 2138834994142, 6944753544643, 22549473023585

Offset: 0

Henry Bottomley, Feb 25 2003

With interpolated zeros (1,0,1,0,2,...), counts closed walks of length n at start or end node of P_6. The sequence (0,1,0,2,...) counts walks of length n between the start and second node. - Paul Barry, Jan 26 2005
HANKEL transform of sequence and the sequence omitting a(0) is the sequence A130716. This is the unique sequence with that property. - Michael Somos, May 04 2012
From Wolfdieter Lang, Mar 30 2020: (Start)
a(n) is also the upper left entry of the n-th power of the 3 X 3 tridiagonal matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: a(n) = ((M_3)^n)[1,1].
Proof: (M_3)^n = b(n-2)*(M_3)^2 - (6*b(n-3) - b(n-4))*M_3 + b(n-3)*1_3, for n >= 0, with b(n) = A005021(n), for n >= -4. For the proof of this see a comment in A005021. Hence (M_3)^n[1,1] = 2*b(n-2) - 5*b(n-3) + b(n-4), for n >= 0. This proves the 3 X 3 part of the conjecture in A332602 by Gary W. Adamson.
The formula for a(n) given below in terms of r = rho(7) = A160389 proves that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796..., because r - 2/r = 0.6920... < 1, and r^2 - 3 = 0.2469... < 1. This limit was conjectured in A332602 by Gary W. Adamson.
(End)

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 131*x^6 + 417*x^7 + 1341*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..600
Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 27.
Jean-Luc Baril, Toufik Mansour, José L. Ramírez, and Mark Shattuck, Catalan words avoiding a pattern of length four, Univ. de Bourgogne (France, 2024). See p. 3.
Jean-Luc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
Wei Chen, Enumeration of Set Partitions Refined by Crossing and Nesting Numbers, MS Thesis, Department of Mathematics. Simon Fraser University, Fall 2014. Table 4.1, line k=2.
Johann Cigler, Number of bounded Dyck paths with "negative length", MathOverflow question, Sep 26 2020.
Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Paul Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
Stefan Felsner and Daniel Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
Matthew Hyatt and Jeffrey Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012
Aleksandar Ilic and Andreja Ilic, On the number of restricted Dyck paths, Filomat 25:3 (2011), 191-201; DOI: 10.2298/FIL1103191I.
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (Corollary 3, case k=5, pages 10-11). - From _N. J. A. Sloane_, May 09 2012
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs, arXiv:2011.07621 [math.CO], 2020. See also J. of Algebraic Combinatorics (2021) Vol. 53, 613-638.
Toufik Mansour and Mark Shattuck, Some enumerative results related to ascent sequences, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 22 2012
Sophie Morier-Genoud, Valentin Ovsienko, and Serge Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, arXiv:1008.3359 [math.AG], 2010-2011. - From _N. J. A. Sloane_, Dec 26 2012
Sophie Morier-Genoud, Valentin Ovsienko, and Serge Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987. - From _N. J. A. Sloane_, Dec 26 2012
David Nečas and Ivan Ohlídal, Consolidated series for efficient calculation of the reflection and transmission in rough multilayers, Optics Express, Vol. 22, 2014, No. 4; DOI:10.1364/OE.22.004499.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Lara Pudwell, Pattern avoidance in trees, slides from a talk, mentions many sequences, 2012. - From _N. J. A. Sloane_, Jan 03 2013
Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, 2014.
Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
Index entries for linear recurrences with constant coefficients, signature (5,-6,1).

Cf. A000007, A000012, A001519, A007051, A011782, A024175, A080937, A080938.
Cf. A033191 which essentially provide the same sequence for different limits and tend to A000108.
Cf. A005021, A094790, A094789.
Cf. A211216, A005021, A160389, A116425, A332602.

I:=[1,1,2]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jan 09 2016

a:= n-> (<<0|1|0>, <0|0|1>, <1|-6|5>>^n. <<1, 1, 2>>)[1, 1]:
seq(a(n), n=0..35);  # Alois P. Heinz, Nov 09 2012

nn=56;Select[CoefficientList[Series[(1-4x^2+3x^4)/(1-5x^2+6x^4-x^6), {x,0,nn}], x],#>0 &] (* Geoffrey Critzer, Jan 26 2014 *)
LinearRecurrence[{5,-6,1},{1,1,2},30] (* Jean-François Alcover, Jan 09 2016 *)

a=vector(99); a[1]=1; a[2]=2;a[3]=5; for(n=4,#a,a[n]=5*a[n-1]-6*a[n-2] +a[n-3]); a \\ Charles R Greathouse IV, Jun 10 2011

{a(n) = if( n<0, n = -n; polcoeff( (1 - 3*x + x^2) / (1 - 6*x + 5*x^2 - x^3) + x * O(x^n), n), polcoeff( (1 - 4*x + 3*x^2) / (1 - 5*x + 6*x^2 - x^3) + x * O(x^n), n))} /* Michael Somos, May 04 2012 */

a(n) = A080934(n,5).
G.f.: (1-4*x+3*x^2)/(1-5*x+6*x^2-x^3). - Ralf Stephan, May 13 2003
a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3). - Herbert Kociemba, Jun 11 2004
a(n) = A096976(2*n). - Floor van Lamoen, Nov 02 2005
a(n) = (4/7-4/7*cos(1/7*Pi)^2)*(4*(cos(Pi/7))^2)^n + (1/7-2/7*cos(1/7*Pi) + 4/7*cos(1/7*Pi)^2)*(4*(cos(2*Pi/7))^2)^n + (2/7+2/7*cos(1/7*Pi))*(4*(cos(3*Pi/7))^2)^n for n>=0. - Richard Choulet, Apr 19 2010
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x))))). - Michael Somos, May 04 2012
a(-n) = A038213(n). a(n + 2) * a(n) - a(n + 1)^2 = a(1 - n). Convolution inverse is A123183 with A123183(0)=1. - Michael Somos, May 04 2012
From Wolfdieter Lang, Mar 30 2020: (Start)
In terms of the algebraic number r = rho(7) = A160389 of degree 3 the formula given by Richard Choulet becomes a(n) = (1/7)*(r)^(2*n)*(C1(r) + C2(r)*(r - 2/r)^(2*n) + C3(r)*(r^2 - 3)^(2*n)), with C1(r) = 4 - r^2, C2(r) = 1 - r + r^2, and C3 = 2 + r.
a(n) = ((M_3)^n)[1,1] = 2*b(n-2) - 5*b(n-3) + b(n-4), for n >= 0, with the 3 X 3 tridiagonal matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602, and b(n) = A005021(n) (with offset n >= -4). (End)

A211216 Expansion of (1-8x+21x^2-20x^3+5x^4)/(1-9x+28x^2-35x^3+15x^4-x^5).

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, 58766, 207783, 740924, 2660139, 9603089, 34818270, 126676726, 462125928, 1689438278, 6186432967, 22682699779, 83249302471, 305773834030, 1123771473120, 4131947428007, 15197952958467, 55915691993228

Offset: 0

Bruno Berselli, May 11 2012

In the paper of Kitaev, Remmel and Tiefenbruck (see the Links section), Q_(132)^(k,0,0,0)(x,0) represents a generating function depending on k and x.
For successive values of k we have:
k=1, the g.f. of A000012: 1/(1-x);
k=2,      "      A011782: (1-x)/(1-2*x);
k=3,      "      A001519: (1-2*x)/(1-3*x+x^2);
k=4,      "      A124302: (1-3*x+x^2)/(1-4*x+3*x^2);
k=5,      "      A080937: (1-4*x+3*x^2)/(1-5*x+6*x^2-x^3);
k=6,      "      A024175: (1-5*x+6*x^2-x^3)/(1-6*x+10*x^2-4*x^3);
k=7,      "      A080938: (1-6*x+10*x^2-4*x^3)/(1-7*x+15*x^2-10*x^3+x^4);
k=8,      "      A033191: (1-7*x+15*x^2-10*x^3+x^4)/(1-8*x+21*x^2
                           -20*x^3+5*x^4).
This sequence corresponds to the case k=9.
We observe that the coefficients of numerators and denominators are in A115139.
In general, Q_(132)^(k,0,0,0)(x,0) is the generating function for Dyck paths whose maximum height is less than or equal to k; also, it is the generating function of rooted binary trees T which have no nodes 'eta' such that there are >= k left edges on the path from 'eta' to the root of T (see cited paper, page 11).

Bruno Berselli, Table of n, a(n) for n = 0..1000
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (page 10, Corollary 3).
K. Mészáros, A. H. Morales, and J. Striker, On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope, arXiv preprint arXiv:1510.03357 [math.CO], 2015-2019.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Index entries for linear recurrences with constant coefficients, signature (9,-28,35,-15,1).

Cf. A000108, A001519, A011782, A024175, A033191, A080937, A080938, A124302.

Cf. square array in A080934.

m:=28; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-8*x+21*x^2-20*x^3+5*x^4)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5)));

CoefficientList[Series[(1 - 8 x + 21 x^2 - 20 x^3 + 5 x^4)/(1 - 9 x + 28 x^2 - 35 x^3 + 15 x^4 - x^5), {x, 0, 27}], x]

Vec((1-8*x+21*x^2-20*x^3+5*x^4)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5)+O(x^28))

G.f.: (1-3*x+x^2)*(1-5*x+5*x^2)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5).
G.f.: 1/(1-x/(1-x/(1-x/(1-x/(1-x/(1-x/(1-x/(1-x/(1-x))))))))). - Philippe Deléham, Mar 14 2013
a(n) = A000108(n) + Sum_{k=1..n} (4*binomial(2*n, n+11*k) - binomial(2*n+2, n+11*k+1)). - Greg Dresden, Jan 28 2023

A080934 Square array read by antidiagonals of number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2n steps with all values less than or equal to k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 8, 1, 0, 1, 1, 2, 5, 13, 16, 1, 0, 1, 1, 2, 5, 14, 34, 32, 1, 0, 1, 1, 2, 5, 14, 41, 89, 64, 1, 0, 1, 1, 2, 5, 14, 42, 122, 233, 128, 1, 0, 1, 1, 2, 5, 14, 42, 131, 365, 610, 256, 1, 0, 1, 1, 2, 5, 14, 42, 132, 417, 1094, 1597, 512, 1, 0

Offset: 0

Henry Bottomley, Feb 25 2003

Number of permutations in S_n avoiding both 132 and 123...k.
T(n,k) = number of rooted ordered trees on n nodes of depth <= k. Also, T(n,k) = number of {1,-1} sequences of length 2n summing to 0 with all partial sums are >=0 and <= k. Also, T(n,k) = number of closed walks of length 2n on a path of k nodes starting from (and ending at) a node of degree 1. - Mitch Harris, Mar 06 2004
Also T(n,k) = k-th coefficient in expansion of the rational function R(n), where R(1) = 1, R(n+1) = 1/(1-x*R(n)), which means also that lim(n->inf,R(n)) = g.f. of Catalan numbers (A000108) wherever it has real value (see Mansour article). - Clark Kimberling and Ralf Stephan, May 26 2004
Row n of the array gives Taylor series expansion of F_n(t)/F_{n+1}(t), where F_n(t) are the Fibonacci polynomials defined in A259475 [Kreweras, 1970]. - N. J. A. Sloane, Jul 03 2015

			T(3,2) = 4 since the paths of length 2*3 (7 points) with all values less than or equal to 2 can take the routes 0101010, 0101210, 0121010 or 0121210, but not 0123210.
From _Peter Luschny_, Aug 27 2014: (Start)
Trees with n nodes and height <= h:
h\n  1  2  3  4   5   6    7    8     9    10     11
---------------------------------------------------------
[ 1] 1, 0, 0, 0,  0,  0,   0,   0,    0,    0,     0, ...  A063524
[ 2] 1, 1, 1, 1,  1,  1,   1,   1,    1,    1,     1, ...  A000012
[ 3] 1, 1, 2, 4,  8, 16,  32,  64,  128,  256,   512, ...  A011782
[ 4] 1, 1, 2, 5, 13, 34,  89, 233,  610, 1597,  4181, ...  A001519
[ 5] 1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281,  9842, ...  A124302
[ 6] 1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, ...  A080937
[ 7] 1, 1, 2, 5, 14, 42, 132, 428, 1416, 4744, 16016, ...  A024175
[ 8] 1, 1, 2, 5, 14, 42, 132, 429, 1429, 4846, 16645, ...  A080938
[ 9] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16778, ...  A033191
[10] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, ...  A211216
---------------------------------------------------------
The generating functions are listed in A211216. Note that the values up to the main diagonal are the Catalan numbers A000108.
(End)

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, Pattern-restricted cyclic permutations with a pattern-restricted cycle form, arXiv:2408.15000 [math.CO], 2024. See also Enum. Comb. Appl. (2025) Vol. 5, No. 1, Art. No. S2R3. See p. 7.
Nicolaas Govert de Bruijn, Donald E. Knuth, and Stephen O. Rice, The Average Height of Planted Plane Trees, Graph Theory and Computing, (1972) 15-22.
Yann Dijoux, Chebyshev polynomials involved in the Householder's method for square roots, arXiv:2501.04703 [math.GM], 2024. Mentions this sequence.
Andrzej Dudek, Jarosław Grytczuk, and Andrzej Ruciński, Largest bipartite sub-matchings of a random ordered matching or a problem with socks, arXiv:2402.02223 [math.CO], 2024.
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
Aleksandar Ilic and Andreja Ilic, On the number of restricted Dyck paths, Filomat 25:3 (2011), 191-201; DOI: 10.2298/FIL1103191I.
Anthony Joseph and Polyxeni Lamprou, A new interpretation of Catalan numbers, arXiv preprint arXiv:1512.00406 [math.CO], 2015.
Myrto Kallipoliti, Robin Sulzgruber, and Eleni Tzanaki, Patterns in Shi tableaux and Dyck paths, arXiv:2006.06949 [math.CO], 2020.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (page 10, Corollary 3).
Christian Krattenthaler, Permutations with restricted patterns and Dyck paths, arXiv:math/0002200 [math.CO], 2000.
Germain Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41. See page 38.
Germain Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs, arXiv:2011.07621 [math.CO], 2020. See also J. of Algebraic Combinatorics (2021) Vol. 53, 613-638.
Toufik Mansour, Restricted even permutations and Chebyshev polynomials, arXiv:math/0302014 [math.CO], 2003.
Toufik Mansour and Alek Vainshtein, Restricted permutations, continued fractions and Chebyshev polynomials, arXiv:math/9912052 [math.CO], 1999-2000.
Dimana Miroslavova Pramatarova, Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions, MIT Res. Sci. Instit. (2025). See pp. 5-6.
Thomas Tunstall, Tim Rogers, and Wolfram Möbius, Assisted percolation of slow-spreading mutants in heterogeneous environments, arXiv:2303.01579 [q-bio.PE], 2023.
Vince White, Enumeration of Lattice Paths with Restrictions, (2024). Electronic Theses and Dissertations. 2799. See pp. 20, 25.

Cf. A000108, A079214, A080935, A080936. Rows include A000012, A057427, A040000 (offset), columns include (essentially) A000007, A000012, A011782, A001519, A007051, A080937, A024175, A080938, A033191, A211216. Main diagonal is A000108.

Cf. A094718 (involutions). Cf. also A259475.

# As a triangular array:
b:= proc(x, y, k) option remember; `if`(y>min(k, x) or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, k)+ b(x-1, y+1, k)))
    end:
A:= (n, k)-> b(2*n, 0, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Aug 06 2012
# As a square array:
A := proc(n,k) option remember; local j; if n = 1 then 1 elif k = 1 then 0 else add(A(n-j,k)*A(j,k-1), j=1..n-1) fi end:
linalg[matrix](10, 12, (n,k) -> A(k,n)); # Peter Luschny, Aug 27 2014

A[n_, k_] := A[n, k] = Which[n == 1, 1, k == 1, 0, True, Sum[A[n-j, k]*A[j, k-1], {j, 1, n-1}]]; Table[A[k-n+1, n], {k, 1, 13}, {n, k, 1, -1}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Peter Luschny *)

A(N, K) = {
  my(m = matrix(N, K, n, k, n==1));
  for (n = 2, N,
  for (k = 2, K,
       m[n,k] = sum(i = 1, n-1, m[n-i,k] * m[i,k-1])));
  return(m);
}
A(11,10)~  \\ Gheorghe Coserea, Jan 13 2016

T(n, k) = Sum_{0A080935(n, k) = T(n, k-1)+A080936(n, k); for k>=n T(n, k) = A000108(n).
T(n, k) = 2^(2n+1)/(k+2) * Sum_{i=1..k+1} (sin(Pi*i/(k+2))*cos(Pi*i/(k+2))^n)^2 for n>=1. - Herbert Kociemba, Apr 28 2004
G.f. of n-th row: B(n)/B(n+1) where B(j)=[(1+sqrt(1-4x))/2]^j-[(1-sqrt(1-4x))/2]^j.

A094829 Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 6.

Original entry on oeis.org

1, 6, 27, 109, 417, 1548, 5644, 20349, 72846, 259579, 922209, 3269889, 11579032, 40967400, 144863001, 512050438, 1809503019, 6393427173, 22587086305, 79791176292, 281856708180, 995606748757, 3516721295214

Offset: 2

Herbert Kociemba, Jun 13 2004

In general, a(n) = (2/m)*Sum_{r=1..m-1} sin(r*j*Pi/m)*sin(r*k*Pi/m)*(2*cos(r*Pi/m))^(2n+1) counts (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < m and |s(i)-s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = j, s(2n+1) = k.
a(n)/a(n-1) tends to 3.53208888...; = 2 + 2*cos(2*Pi/9) = A332438. - Gary W. Adamson, May 29 2008
From Wolfdieter Lang, Mar 27 2020: (Start)
The explicit form is written in terms of r = rho(9) = 2*cos(Pi/9) = A332437 as a Binet - de Moivre type formula a(n+2) = r^(2*(n+1))*(A(r) + Bp(r)*Cp(r)^(n+1)) + Bm(r)*Cm(r)^(n+1)), with A(r) = (1/9)*(2 + 5*r -r^2), approx. 0.87387081, Bp(r) = (1/18)*((14*r^2 - 5*r - 42)*sqrt(3*(3*r + 1)*(r - 1)) + r^2 - 5*r - 2) = (1/9)*(8 - r - 4*r^2), approx. -0.88974898, Cp(r) = (1/2)*(9*r^2 - 3*r - 26)*(3*r - 1 + sqrt(3*(3*r+1)*(r-1))) = 32 + 4*r - 11*r^2, approx. 0.66456322, Bm(r) = (1/18)*(-(14*r^2 - 5*r - 42)*sqrt(3*(3*r + 1)*(r - 1)) + r^2 - 5*r - 2) = (1/9)*(-10 -4*r + 5*r^2), approx. 0.01587816, and Cm(r) = (1/2)*(9*r^2 - 3*r - 26)*(3*r - 1 - sqrt(3*(3*r + 1)*(r - 1))) = 21 + 2*r - 7*r^2, approx. 0.03414828, for n >= 0.
Proof by partial fraction decomposition of the g.f. using the roots of 1 - 6*x + 9*x^2 - x^3 written in terms of r, which are X1(r) = 1/r^2 = 9 + r - 3*r^2, approx. 0.28311858, Xp(r) = (r/2)*(3*r - 1 + sqrt((3*(3*r+1))*(r-1))) = 1 + 2*r + r^2, approx. 8.29085937, Xm(r) = (r/2)*(3*r - 1 - sqrt((3*(3*r + 1))*(r - 1))) = -1 - 3*r + 2*r^2, approx. 0.42602205. Xp(r)*Xm(r) = r^2. The reduction with the minimal polynomial of r = rho(9), i.e., C(9, x) = x^3 - 3*x - 1 (see A187360) has been used to avoid all powers of r larger than 2. The reciprocal roots turn out to be the roots of the minimal polynomial of r^2, see A332438. 1/X1(r) = r^2, 1/Xp(r) = 2 - r, and 1/Xm(r) = 4 + r - r^2.
This proves the above stated limit of a(n+3)/a(n+2) for n to infinity, namely r^2 = A332438, approx. 3.53208889.
(End)

Michael De Vlieger, Table of n, a(n) for n = 2..1825
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Index entries for linear recurrences with constant coefficients, signature (6,-9,1).

Cf. A080938, A094256, A332437, A332438.

Drop[CoefficientList[Series[x^2/(1 - 6 x + 9 x^2 - x^3), {x, 0, 24}], x], 2] (* Michael De Vlieger, Aug 05 2021 *)

a(n) = (2/9)*Sum_{r=1..8} sin(r*Pi/9)*sin(2*r*Pi/3)*(2*cos(r*Pi/9))^(2*n+1), for n >= 2.
a(n) = 6*a(n-1) - 9*a(n-2) + a(n-3).
G.f.: x^2/(1 - 6x + 9x^2 - x^3).
For the explicit form of a(n+2), for n >= 0, see a comment above. - Wolfdieter Lang, Mar 26 2020

A094256 Expansion of x / ( (x-1)(x^3 - 9x^2 + 6*x - 1) ).

Original entry on oeis.org

1, 7, 34, 143, 560, 2108, 7752, 28101, 100947, 360526, 1282735, 4552624, 16131656, 57099056, 201962057, 714012495, 2523515514, 8916942687, 31504028992, 111295205284, 393151913464, 1388758662221, 4905479957435, 17327203698086, 61202661233823, 216176614077600

Offset: 1

Gary W. Adamson, Apr 25 2004

Previous name was: Let M = the 4 X 4 matrix [0 1 0 0 / 0 0 1 0 / 0 0 0 1 / -1 10 -15 7]. Perform M^n * [1 0 0 0] = [p q r s]. Then a(n-3), a(n-2), a(n-1), a(n) = -p, -q, -r, -s respectively.
a(n)/a(n-1) tends to 3.53208888624... = 4*cos^2(Pi/9), which is an eigenvalue of the matrix and a root of the polynomial x^4 - 6x^3 + 15x^2 -10x + 1 = 0 (having roots 4*cos^2(r*Pi/9), with r = 1,2,3,4).
Number of (s(0), s(1), ..., s(2n+4)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+4, s(0) = 1, s(2n+4) = 7. - Herbert Kociemba, Jun 13 2004
From Wolfdieter Lang, Mar 27 2020: (Start)
This sequence, with offset -5, starting with -85, -10, -1, 0, 0, 0, 1, 7, ... appears in the formula for the n-th power of the 4 X 4 tridiagonal matrix given in A332602 as M_4 = matrix([1,1,0,0], [1,2,1,0], [0,1,2,1], [0,0,1,2]): (M_4)^n = a(n-2)*(M_4)^3 + b(n)*(M_4)^2 + c(n)*M_4 - a(n-3)*1_4, for n >= 0, with the 4 X 4 unit Matrix 1_4, b(n) = -15*a(n-3) + 10*a(n-4) - a(n-5), and c(n) = 10*a(n-3) - a(n-4). Proof from the characteristc polynomial of M_4 (see a comment in A332602) and the Cayley-Hamilton theorem.
From the proof that A094829(n+3)/A094829(n+2) -> rho(9)^2 = A332438 for n-> infinitiy, with rho(9) = 2*cos(Pi/9) = A332437 (see a comment in A094829), and a formula given below the same limit is obtained for a(n+1)/a(n) for n -> infinity, as stated in a comment above. (End)

			a(2), a(3), a(4), a(5) = 7, 34, 143, 560, since M^5 * [1 0 0 0] = [ -7 -34 -143 -560].
Cayley-Hamilton: (M_4)^5 = a(3)*(M_4)^3 + b(5)*(M_4)^2 + c(5)*M_4 - a(2)*1_4 = 34*(M_4)^3 - 95*(M_4)^2 + 69*M_4 - 7*1_4. - _Wolfdieter Lang_, Mar 27 2020

C. V. Durell and A. Robson, "Advanced Trigonometry", Dover 2003, p. 216.

Michael De Vlieger, Table of n, a(n) for n = 1..1824
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Index entries for linear recurrences with constant coefficients, signature (7,-15,10,-1).

a(n) = A005023(n-1), n > 1. - R. J. Mathar, Sep 05 2008

Cf. A080938, A094829, A332602, A332437, A332438.

I:=[1,7,34,143]; [n le 4 select I[n] else 7*Self(n-1) - 15*Self(n-2) + 10*Self(n-3) - Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jul 25 2015

Table[ (MatrixPower[{{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {-1, 10, -15, 7}}, n].{-1, 0, 0, 0})[[4]], {n, 24}] (* Robert G. Wilson v, Apr 28 2004 *)
LinearRecurrence[{7, -15, 10, -1}, {1, 7, 34, 143}, 40] (* Vincenzo Librandi, Jul 25 2015 *)

Vec(x / ( (x-1)*(x^3-9*x^2+6*x-1) ) + O(x^30)) \\ Michel Marcus, Jul 25 2015

From Herbert Kociemba, Jun 13 2004: (Start)
a(n) = (2/9)*Sum_{r=1..8} sin(r*Pi/9)*sin(7*r*Pi/9)*(2*cos(r*Pi/9))^(2n+4).
a(n) = 7*a(n-1) - 15*a(n-2) + 10*a(n-3) - a(n-4).
G.f.: x / ( (x-1)*(x^3 - 9*x^2 + 6*x - 1) ). (End)
3*a(n) = 1 - A094829(n+2) + 8*A094829(n+1) - A094829(n). - R. J. Mathar, Jun 29 2012 [offset corrected, and A094829(1) = 0. - Wolfdieter Lang, Mar 27 2020]
a(n) = (1/3)*(1 + 2*A094829(n+1) + 8*A094829(n) - A094829(n-1)), for n >= 1, with A094829(1) and A094829(0) = 0. - Wolfdieter Lang, Mar 27 2020

More terms from Robert G. Wilson v, Apr 28 2004
a(25)-a(26) from Vincenzo Librandi, Jul 25 2015
New name (using g.f. from Herbert Kociemba) from Joerg Arndt, Jul 25 2015

A332602 Tridiagonal matrix M read by antidiagonals: main diagonal is 1,2,2,2,2,..., two adjacent diagonals are 1,1,1,1,1,...

Original entry on oeis.org

1, 1, 1, 0, 2, 0, 0, 1, 1, 0, 0, 0, 2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane, Mar 06 2020, following a suggestion from Gary W. Adamson

From Gary W. Adamson, Mar 11 2020: (Start)
The upper left entry of M^n gives the Catalan numbers A000108. Extracting 2 X 2, 3 X 3, and 4 X 4 submatrices from M; then generating sequences from the upper left entries of M^n, we obtain the following sequences:
1, 1, 2, 5, 13, ... = A001519 and the convergent is 2.61803... = 2 + 2*cos(2*Pi/5) = (2*cos(Pi/5))^2.
1, 1, 2, 5, 14, 42, 131, ... = A080937 and the convergent is 3.24697... = 2 + 2*cos(2*Pi/7) = (2*cos(Pi/7))^2.
1, 1, 2, 5, 14, 42, 132, 429, 1429, ... = A080938 and the convergent is 3.53208... = 2 + 2*cos(2*Pi/9) = (2*cos(Pi/9))^2. (End)
The characteristic polynomial for the N X N main submatrix M_N is Phi(N, x) = S(N, 2-x) - S(N-1, 2-x), with Chebyshev's S polynomial (see A049310) evaluated at 2-x. Proof by determinant expansion, to obtain the recurrence Phi(N, x) - (x-2)*Phi(N-1, x) - Phi(N-2, x), for N >= 2, and Phi(0, x) = 1 and Phi(1, x) = 1 - x, that is Phi(-1, x) = 1. The trace is tr(M_N) = 1 + 2^(N-1) = A000051(N-1), and Det(M_N) = 1. - Wolfdieter Lang, Mar 13 2020
The explicit form of the characteristic polynomial for the N X N main submatrix M_N is Phi(N, x) := Det(M_N - x*1_N) = Sum_{k=0..N} binomial(N+k, 2*k)*(-x)^k = Sum_{k=0..N} A085478(N, k)*(-x)^k, for N >= 0, with Phi(0, x) := 1. Proof from the recurrence given in the preceding comment. - Wolfdieter Lang, Mar 25 2020
For the proofs of the 2 X 2, 3 X 3 and 4 X 4 conjectures, see the comments in the respective A-numbers A001519, A080937 and A080938. - Wolfdieter Lang, Mar 30 2020
Replace the main diagonal 1,2,2,2,... of the matrix M with 1,0,0,0,...; 1,1,1,1,...; 1,3,3,3,...; 1,2,1,2,...; 1,2,3,4,...; 1,0,1,0...; and 1,1,0,0,1,1,0,0,.... Take powers of M and extract the upper left terms, resulting in respectively: A001405, A001006, A033321, A176677, A006789, A090344, and A007902. - Gary W. Adamson, Apr 12 2022
The statement that the upper left entry of M^n is a Catalan number is equivalent to Exercise 41 of R. Stanley, "Catalan Numbers." - Richard Stanley, Feb 28 2023
If the upper left 1 in matrix M is replaced with 3, taking powers of the resulting matrix and extracting the upper left terms apparently results in sequence A001700. - Gary W. Adamson, Apr 03 2023

			The matrix begins:
  1, 1, 0, 0, 0, ...
  1, 2, 1, 0, 0, ...
  0, 1, 2, 1, 0, ...
  0, 0, 1, 2, 1, ...
  0, 0, 0, 1, 2, ...
  ...
The first few antidiagonals are:
  1;
  1, 1;
  0, 2, 0;
  0, 1, 1, 0;
  0, 0, 2, 0, 0;
  0, 0, 1, 1, 0, 0;
  0, 0, 0, 2, 0, 0, 0;
  0, 0, 0, 1, 1, 0, 0, 0;
  0, 0, 0, 0, 2, 0, 0, 0, 0;
  0, 0, 0, 0, 1, 1, 0, 0, 0, 0;
  ...
Characteristic polynomial of the 3 X 3 matrix M_3: Phi(3, x) = 1 - 6*x + 5*x^2 - x^3, from {A085478(3, k)}_{k=0..3} = {1, 6, 5, 1}. - _Wolfdieter Lang_, Mar 25 2020

Richard P. Stanley, "Catalan Numbers", Cambridge University Press, 2015.

Cf. A000108, A000051, A001519, A049310, A080937, A080938, A085478.
Cf. A001006, A001405, A006789, A033321, A176677, A090344, A007902.
Cf. A001333 (permanent of the matrix M).
Cf. A054142, A053123, A011973 (characteristic polynomials of submatrices of M).
Cf. A001700.

A217315 Square array T, read by antidiagonals: T(n,k) = 0 if n-k >= 1 or if k-n >= 8, T(0,k)= 1 if 0<=k<=7, T(n,k) = T(n-1,k) + T(n,k-1).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 5, 0, 0, 0, 1, 5, 9, 5, 0, 0, 0, 1, 6, 14, 14, 0, 0, 0, 0, 0, 7, 20, 28, 14, 0, 0, 0, 0, 0, 7, 27, 48, 42, 0, 0, 0, 0, 0, 0, 0, 34, 75, 90, 42, 0, 0, 0, 0, 0, 0, 0, 34, 109, 165, 132, 0, 0, 0, 0, 0, 0, 0, 0, 0, 143, 274, 297, 132, 0, 0, 0, 0, 0, 0, 0, 0, 0, 143, 417, 571, 429, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Philippe Deléham, Mar 17 2013

A hexagon arithmetic of E. Lucas.

			Square array begins:
1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, ... row n=0
0, 1, 2, 3, 4, 5, 6, 7, 7, 0, 0, 0, 0, 0, 0, ... row n=1
0, 0, 2, 5, 9, 14, 20, 27, 34, 34, 0, 0, 0, ... row n=2
0, 0, 0, 5, 14, 28, 48, 75, 109, 143, 143, 0, 0, ... row n=3
0, 0, 0, 0, 14, 42, 90, 165, 274, 417, 560, 560, 0, ... row n=4
0, 0, 0, 0, 0, 42, 132, 297, 571, 988, 1548, 2108, 2108, 0, ... row n=5
...

Cf. Similar sequence: A216230, A216228, A216226, A216238, A216054, A217257.

t[0, k_ /; k <= 7] = 1; t[n_, k_] /; k < n || k > n+7 = 0; t[n_, k_] := t[n, k] = t[n-1, k] + t[n, k-1]; Table[t[n-k, k], {n, 0, 13}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Mar 18 2013 *)

T(n,n) = A080938(n).
T(n,n+1) = A080938(n+1).
T(n,n+2) = A094826(n+1).
T(n,n+3) = A094827(n+1).
T(n,n+4) = A094828(n+2).
T(n,n+5) = A094829(n+2).
T(n,n+6) = T(n,n+7) = A094256(n+1).
Sum_{k, 0<=k<=n} T(n-k,k) = A061551(n).

A122881 Triangle read by rows: number of Catalan paths of 2n steps of all values less than or equal to m.

Original entry on oeis.org

1, 1, 2, 1, 2, 5, 1, 2, 5, 13, 1, 2, 5, 14, 34, 1, 2, 5, 14, 42, 89, 1, 2, 5, 14, 42, 131, 233, 1, 2, 5, 14, 42, 132, 417, 610, 1, 2, 5, 14, 42, 132, 429, 1341, 1597, 1, 2, 5, 14, 42, 132, 429, 1429, 4334, 4181

Offset: 1

Gary W. Adamson, Sep 16 2006

Convergents of k-th diagonals relate to (2k+3)-polygons; e.g., right border relates to the pentagon (N=5), next border relates to the heptagon (N=7). Convergents of the diagonals are 2 + 2*cos(2*Pi/N) and are roots to Morgan-Voyce polynomials. k2 diagonal = A080937, number of Catalan paths of 2n steps of all values less than or equal to 5. k3 diagonal = A080938, number of Catalan paths of 2n steps of all values less than or equal to 7.

			For the right border, odd-indexed Fibonacci numbers (1, 2, 5, 13, 34...), we begin with (M2) = [1, 1; 1, 0], then P2 = [1, -1; -1, 2] = 1/(M2)^2. Performing (P2)^n * [1,0] we extract the left vector (1, 2, 5, 13, ...), making it the right border of the triangle, k1 diagonal.
For the next diagonal going to the left, we begin with the Heptagonal matrix M3 = [1, 1, 1; 1, 1, 0; 1, 0, 0], take the inverse square (P3) and then perform the analogous operation getting 1, 2, 5, 14, 42, ...
First few rows of the triangle are:
  1;
  1, 2;
  1, 2, 5;
  1, 2, 5, 13;
  1, 2, 5, 14, 34;
  1, 2, 5, 14, 42, 89;
  1, 2, 5, 14, 42, 131, 233;
  1, 2, 5, 14, 42, 132, 417, 610;
  ...

Cf. A112880, A001519, A000108, A080937, A080938.

Begin with polygonal matrices of the form (exemplified by the Heptagonal matrix M3: [1, 1, 1; 1, 1, 0; 1, 0, 0]). Let matrix P3 = 1 / M3^2; then for n X n matrices P2, P3, P4...perform P^n * [1, 0, 0] letting this vector = k-th diagonal of the triangle.

cp's OEIS Frontend

A080937 Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps with all values <= 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A211216 Expansion of (1-8*x+21*x^2-20*x^3+5*x^4)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A080934 Square array read by antidiagonals of number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2n steps with all values less than or equal to k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A094829 Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A094256 Expansion of x / ( (x-1)*(x^3 - 9*x^2 + 6*x - 1) ).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A332602 Tridiagonal matrix M read by antidiagonals: main diagonal is 1,2,2,2,2,..., two adjacent diagonals are 1,1,1,1,1,...

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A217315 Square array T, read by antidiagonals: T(n,k) = 0 if n-k >= 1 or if k-n >= 8, T(0,k)= 1 if 0<=k<=7, T(n,k) = T(n-1,k) + T(n,k-1).

Views

Author

Keywords

Comments

Examples

A211216 Expansion of (1-8x+21x^2-20x^3+5x^4)/(1-9x+28x^2-35x^3+15x^4-x^5).

A094256 Expansion of x / ( (x-1)(x^3 - 9x^2 + 6*x - 1) ).