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.

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,3

Comments

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)

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

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.

L. 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).

Formula

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

Example

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

Mathematica

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

Prog

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

Crossrefs

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.

Sequence in context: A036768 A287970 A058094 * A054394 A261590 A036769

Adjacent sequences: A080935 A080936 A080937 * A080939 A080940 A080941

Keyword

nonn,easy

Author

Henry Bottomley, Feb 25 2003

Status

approved