A033191 -id:A033191 - 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)

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

Original entry on oeis.org

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

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.

A033192 a(n) = binomial(Fibonacci(n) + 1, 2).

Original entry on oeis.org

0, 1, 1, 3, 6, 15, 36, 91, 231, 595, 1540, 4005, 10440, 27261, 71253, 186355, 487578, 1276003, 3339820, 8742471, 22885995, 59912931, 156848616, 410626153, 1075018896, 2814412825, 7368190921, 19290113571, 50502074766, 132215989335, 346145696820, 906220783315

Offset: 0

Simon P. Norton

a(n) is the sum of n-th row in Wythoff array A003603. [Reinhard Zumkeller, Jan 26 2012]

A subsequence of the triangular numbers A000217. In fact, binomial(F(n)+1,2) = A000217(F(n)). - M. F. Hasler, Jan 27 2012

Alois P. Heinz, Table of n, a(n) for n = 0..2394
James P. Jones and Péter Kiss, Representation of integers as terms of a linear recurrence with maximal index, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae, 25. (1998) pp. 21-37. See Theorem 3.7 p. 33.
Kálmán Liptai and László Szalay, Random inhomogeneous binary recurrences, Annales Univ. Sci. Budapest, Sect. Comp. 54 (2023) 253-263. See p. 262.
Index entries for linear recurrences with constant coefficients, signature (3,1,-5,-1,1).

Cf. A000045, A000217, A033191, A081667.

a:= n-> (f-> f*(f+1)/2)((<<0|1>, <1|1>>^n)[1, 2]):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 06 2008

Table[Binomial[Fibonacci[n] + 1, 2], {n, 0, 50}] (* Alonso del Arte, Jan 26 2012 *)
LinearRecurrence[{3,1,-5,-1,1},{0,1,1,3,6},40] (* Harvey P. Dale, Apr 04 2020 *)

a(n)=binomial(fibonacci(n)+1,2) \\ Charles R Greathouse IV, Jan 26 2012

G.f.: x(x^3-x^2-2x+1)/[(1+x)(1-3x+x^2)(1-x-x^2)].
a(n) = ((Fibonacci(n)+Fibonacci(n)^2)/2). - Gary Detlefs, Dec 24 2010
Equals A000217 o A000045. - M. F. Hasler, Jan 27 2012
a(n) = A032441(n) - 1. - Filip Zaludek, Oct 30 2016

A080938 Number of Catalan paths (nonnegative, starting and ending at 0, step +-1) of 2*n steps with all values less than or equal to 7.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1429, 4846, 16645, 57686, 201158, 704420, 2473785, 8704089, 30664890, 108126325, 381478030, 1346396146, 4753200932, 16783118309, 59266297613, 209302921830, 739203970773, 2610763825782, 9221050139566, 32568630376132

Offset: 0

Henry Bottomley, Feb 25 2003

From Wolfdieter Lang, Mar 27 2020: (Start)
a(n) also gives the upper left entry of the n-th power of the 4 X 4 tridiagonal matrix M_4, given in A332602: M_4 = Matrix([1,1,0,0], [1,2,1,0], [0,1,2,1], [0,0,1,2]): a(n) = (M_4)^n[1,1]. Proof from the formula for (M_4)^n, given in a comment in A094256, derived from the Cayley-Hamilton theorem, which leads to the recurrence. The formula for a(n) in terms of A094256 is given below.
For A094256(n+1)/A094256(n), like for A094829(n+1)/A094829(n), the limit for n -> infinity is rho(9)^2 = A332438 = 3.53208888..., with rho(9) = 2*cos(Pi/9) = A332437. Therefore the formula of a(n) in terms of A094256 shows that the same limit is reached for a(n+1)/a(n). See this conjecture by Gary W. Adamson in A332602.
(End)

			1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
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.
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, k=4.
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.
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=7, pages 10-11). - From _N. J. A. Sloane_, May 09 2012.
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.
Index entries for linear recurrences with constant coefficients, signature (7,-15,10,-1).

Cf. A000007, A000012, A011782, A001519, A007051, A080937, A024175, A033191 which essentially provide the same sequence for different limits and tend to A000108.

Cf. A211216, A094826 (first differences), A094829, A094829, A332602, A332437, A332438.

I:=[1,1,2,5]; [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, Nov 30 2018

CoefficientList[Series[(1 - 2 x) (2 x^2 - 4 x + 1) / ((x - 1) (x^3 - 9 x^2 + 6 x - 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 30 2018 *)
LinearRecurrence[{7, -15, 10, -1}, {1, 1, 2, 5}, 30] (* Jean-François Alcover, Jan 07 2019 *)

{a(n) = local(A); A = 1; for( i=1, 7, A = 1 / (1 - x*A)); polcoeff( A + x * O(x^n), n)} /* Michael Somos, May 12 2012 */

a(n) = A080934(n,7).
G.f.: -(2*x - 1)*(2*x^2 - 4*x + 1) / ( (x - 1)*(x^3 - 9*x^2 + 6*x - 1) ). - Ralf Stephan, May 13 2003
a(n) = 7*a(n-1) - 15*a(n-2) + 10*a(n-3) - a(n-4). - Herbert Kociemba, Jun 13 2004
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x))))))). - Michael Somos, May 12 2012
a(n) = 5*b(n-2) - 21*b(n-3) + 19*b(n-4) - 2*b(n-5), for n >= 0, with b(n) = A094256(n), for n >= -5. See a comment in A094256 for this offset, and the above comment. - Wolfdieter Lang, Mar 28 2020

A217593 Square array T, read by antidiagonals: T(n,k) = 0 if n-k >=1 or if k-n >= 9, T(0,k) = 1 for k = 0..8, 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, 1, 7, 20, 28, 14, 0, 0, 0, 0, 0, 8, 27, 48, 42, 0, 0, 0, 0, 0, 0, 8, 35, 75, 90, 42, 0, 0, 0, 0, 0, 0, 0, 43, 110, 165, 132, 0, 0, 0, 0, 0, 0, 0, 0, 43, 153, 275, 297, 132, 0, 0, 0, 0, 0, 0, 0, 0, 0, 196, 428, 572, 429, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Philippe Deléham, Mar 18 2013

			Square array begins :
1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, ...
0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 0, 0, ...
0, 0, 2, 5, 9, 14, 20, 27, 35, 43, 43, 0, 0, ...
0, 0, 0, 5, 14, 28, 75, 110, 153, 196, 196, 0, 0, ....
0, 0, 0, 0, 14, 42, 90, 165, 275, 428, 624, 820, 820, 0, 0, ...
...
Square array, read by rows, with 0 omitted:
1, 1, 1, 1, 1, 1, 1, 1, 1
1, 2, 3, 4, 5, 6, 7, 8, 8
2, 5, 9, 14, 20, 27, 35, 43, 43
5, 14, 28, 48, 75, 110, 153, 196, 196
14, 42, 90, 165, 275, 428, 624, 820, 820
42, 132, 297, 572, 1000, 1624, 2444, 3264, 3264
132, 429, 1001, 2001, 3625, 6069, 9333, 12597, 12597
429, 1430, 3431, 7056, 13125, 22458, 35055, 47652, 47652
...

A hexagon arithmetic of E. Lucas.

T(n,n)   = A033191(n).
T(n,n+1) = A033191(n+1).
T(n,n+2) = A033190(n+1).
T(n,n+3) = A094667(n+1).
T(n,n+4) = A093131(n+1) = A030191(n).
T(n,n+5) = A094788(n+2).
T(n,n+6) = A094825(n+3).
T(n,n+7) = T(n,n+8) = A094865(n+3).
Sum_{k, 0<=k<=n} T(n-k,k) = A178381(n).

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

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

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

A033192 a(n) = binomial(Fibonacci(n) + 1, 2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A080938 Number of Catalan paths (nonnegative, starting and ending at 0, step +-1) of 2*n steps with all values less than or equal to 7.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

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

A336602 a(n) = 8a(n-1) - 21a(n-2) + 20a(n-3) - 5a(n-4), with initial terms a(0)=1, a(1)=7, a(2)=35, a(3)=154.