A080937 - OEIS

%I #149 Aug 06 2024 16:53:48

%S 1,1,2,5,14,42,131,417,1341,4334,14041,45542,147798,479779,1557649,

%T 5057369,16420730,53317085,173118414,562110290,1825158051,5926246929,

%U 19242396629,62479659622,202870165265,658715265222,2138834994142,6944753544643,22549473023585

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

%C 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

%C 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

%C From _Wolfdieter Lang_, Mar 30 2020: (Start)

%C 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].

%C 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_.

%C 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_.

%C (End)

%H Alois P. Heinz, <a href="/A080937/b080937.txt">Table of n, a(n) for n = 0..600</a>

%H Jean-Luc Baril, Toufik Mansour, José L. Ramírez, and Mark Shattuck, <a href="http://jl.baril.u-bourgogne.fr/bmrs.pdf">Catalan words avoiding a pattern of length four</a>, Univ. de Bourgogne (France, 2024). See p. 3.

%H Jean-Luc Baril and Helmut Prodinger, <a href="https://arxiv.org/abs/2205.01383">Enumeration of partial Lukasiewicz paths</a>, arXiv:2205.01383 [math.CO], 2022.

%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.

%H Giulio Cerbai, Anders Claesson, and Luca Ferrari, <a href="https://arxiv.org/abs/1907.08142">Stack sorting with restricted stacks</a>, arXiv:1907.08142 [cs.DS], 2019.

%H Wei Chen, <a href="http://summit.sfu.ca/item/14626">Enumeration of Set Partitions Refined by Crossing and Nesting Numbers</a>, MS Thesis, Department of Mathematics. Simon Fraser University, Fall 2014. Table 4.1, line k=2.

%H Johann Cigler, <a href="https://mathoverflow.net/questions/372642/number-of-bounded-dyck-paths-with-negative-length">Number of bounded Dyck paths with "negative length"</a>, MathOverflow question, Sep 26 2020.

%H Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p22">Non-contiguous pattern avoidance in binary trees</a>, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.

%H Nachum Dershowitz, <a href="https://arxiv.org/abs/2006.06516">Between Broadway and the Hudson: A Bijection of Corridor Paths</a>, arXiv:2006.06516 [math.CO], 2020.

%H Paul Duncan and Einar Steingrimsson, <a href="http://arxiv.org/abs/1109.3641">Pattern avoidance in ascent sequences</a>, arXiv preprint arXiv:1109.3641 [math.CO], 2011.

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020.

%H Stefan Felsner and Daniel Heldt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Felsner/felsner2.html">Lattice Path Enumeration and Toeplitz Matrices</a>, J. Int. Seq. 18 (2015) # 15.1.3.

%H Daniel Heldt, <a href="http://dx.doi.org/10.14279/depositonce-5182">On the mixing time of the face flip-and up/down Markov chain for some families of graphs</a>, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.

%H Matthew Hyatt and Jeffrey Remmel, <a href="http://arxiv.org/abs/1208.1052">The classification of 231-avoiding permutations by descents and maximum drop</a>, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012

%H Aleksandar Ilic and Andreja Ilic, <a href="http://dx.doi.org/10.2298/FIL1103191I">On the number of restricted Dyck paths</a>, Filomat 25:3 (2011), 191-201; DOI: 10.2298/FIL1103191I.

%H Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I,</a> arXiv:1201.6243v1 [math.CO], 2012 (Corollary 3, case k=5, pages 10-11). - From _N. J. A. Sloane_, May 09 2012

%H Erkko Lehtonen and Tamás Waldhauser, <a href="https://arxiv.org/abs/2011.07621">Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs</a>, arXiv:2011.07621 [math.CO], 2020. See also <a href="https://doi.org/10.1007/s10801-020-01010-w">J. of Algebraic Combinatorics</a> (2021) Vol. 53, 613-638.

%H Toufik Mansour and Mark Shattuck, <a href="http://arxiv.org/abs/1207.3755">Some enumerative results related to ascent sequences</a>, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 22 2012

%H Sophie Morier-Genoud, Valentin Ovsienko, and Serge Tabachnikov, <a href="http://arxiv.org/abs/1008.3359">2-frieze patterns and the cluster structure of the space of polygons</a>, arXiv:1008.3359 [math.AG], 2010-2011. - From _N. J. A. Sloane_, Dec 26 2012

%H Sophie Morier-Genoud, Valentin Ovsienko, and Serge Tabachnikov, <a href="http://dx.doi.org/10.5802/aif.2713">2-frieze patterns and the cluster structure of the space of polygons</a>, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987. - From _N. J. A. Sloane_, Dec 26 2012

%H David Nečas and Ivan Ohlídal, <a href="http://dx.doi.org/10.1364/OE.22.004499">Consolidated series for efficient calculation of the reflection and transmission in rough multilayers</a>, Optics Express, Vol. 22, 2014, No. 4; DOI:10.1364/OE.22.004499.

%H László Németh and László Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Nemeth/nemeth8.html">Sequences Involving Square Zig-Zag Shapes</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.

%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a>, slides from a talk, mentions many sequences, 2012. - From _N. J. A. Sloane_, Jan 03 2013

%H Lara Pudwell and Andrew Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014.

%H Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, <a href="https://arxiv.org/abs/2310.12366">Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation</a>, arXiv:2310.12366 [quant-ph], 2023. See p. 12.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-6,1).

%F a(n) = A080934(n,5).

%F G.f.: (1-4*x+3*x^2)/(1-5*x+6*x^2-x^3). - _Ralf Stephan_, May 13 2003

%F a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3). - _Herbert Kociemba_, Jun 11 2004

%F a(n) = A096976(2*n). - _Floor van Lamoen_, Nov 02 2005

%F 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

%F G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x))))). - _Michael Somos_, May 04 2012

%F 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

%F From _Wolfdieter Lang_, Mar 30 2020: (Start)

%F 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.

%F 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)

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

%p a:= n-> (<<0|1|0>, <0|0|1>, <1|-6|5>>^n. <<1, 1, 2>>)[1, 1]:

%p seq(a(n), n=0..35);  # _Alois P. Heinz_, Nov 09 2012

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

%t LinearRecurrence[{5,-6,1},{1,1,2},30] (* _Jean-François Alcover_, Jan 09 2016 *)

%o (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

%o (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 */

%o (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

%Y Cf. A000007, A000012, A001519, A007051, A011782, A024175, A080937, A080938.

%Y Cf. A033191 which essentially provide the same sequence for different limits and tend to A000108.

%Y Cf. A005021, A094790, A094789.

%Y Cf. A211216, A005021, A160389, A116425, A332602.

%K nonn,easy

%O 0,3

%A _Henry Bottomley_, Feb 25 2003