login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A080937 Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps with all values <= 5. 20
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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 A322602: 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)

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..600

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.

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

S. Felsner and D. 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.

M. Hyatt and J. 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.

T. Mansour and M. Shattuck, Some enumerative results related to ascent sequences, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - From N. J. A. Sloane, Dec 22 2012

S. Morier-Genoud, V. Ovsienko and S. 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

S. Morier-Genoud, V. Ovsienko and S. 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

D. Necas and I. Ohlidal, 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.

L. Pudwell, Pattern avoidance in trees, slides from a talk, mentions many sequences, 2012. - From N. J. A. Sloane, Jan 03 2013

L. Pudwell and A. Baxter, Ascent sequences avoiding pairs of patterns, 2014

Index entries for linear recurrences with constant coefficients, signature (5,-6,1).

FORMULA

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 A322602, and b(n) = A005021(n) (with offset n >= -4). (End)

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

PROG

(PARI) 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

(PARI) {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 */

(MAGMA) 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

CROSSREFS

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.

Sequence in context: A344571 A148328 A290134 * A196417 A054392 A261588

Adjacent sequences:  A080934 A080935 A080936 * A080938 A080939 A080940

KEYWORD

nonn,easy,changed

AUTHOR

Henry Bottomley, Feb 25 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 28 23:12 EST 2022. Contains 350670 sequences. (Running on oeis4.)