|
%I #66 Sep 08 2022 08:45:09
%S 1,1,2,5,14,42,132,429,1429,4846,16645,57686,201158,704420,2473785,
%T 8704089,30664890,108126325,381478030,1346396146,4753200932,
%U 16783118309,59266297613,209302921830,739203970773,2610763825782,9221050139566,32568630376132
%N 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.
%C From _Wolfdieter Lang_, Mar 27 2020: (Start)
%C 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.
%C 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.
%C (End)
%H Vincenzo Librandi, <a href="/A080938/b080938.txt">Table of n, a(n) for n = 0..1000</a>
%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, k=4.
%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 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=7, pages 10-11). - From _N. J. A. Sloane_, May 09 2012.
%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 L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a> (slides from a talk, mentions many sequences), 2012.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (7,-15,10,-1).
%F a(n) = A080934(n,7).
%F 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
%F a(n) = 7*a(n-1) - 15*a(n-2) + 10*a(n-3) - a(n-4). - _Herbert Kociemba_, Jun 13 2004
%F G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x))))))). - _Michael Somos_, May 12 2012
%F 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
%e 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + ...
%t 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 *)
%t LinearRecurrence[{7, -15, 10, -1}, {1, 1, 2, 5}, 30] (* _Jean-François Alcover_, Jan 07 2019 *)
%o (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 */
%o (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
%Y Cf. A000007, A000012, A011782, A001519, A007051, A080937, A024175, A033191 which essentially provide the same sequence for different limits and tend to A000108.
%Y Cf. A211216, A094826 (first differences), A094829, A094829, A332602, A332437, A332438.
%K nonn,easy
%O 0,3
%A _Henry Bottomley_, Feb 25 2003
|
