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

Author

Henry Bottomley, Feb 25 2003

Keywords

• nonn
• easy

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)

Examples

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

Links

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

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.

Programs

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

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

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

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