A224071 Number of Schroeder paths of semilength n in which there are no (2,0)-steps at level 1.
1, 2, 5, 15, 52, 201, 841, 3726, 17213, 82047, 400600, 1993377, 10071777, 51532938, 266462229, 1390174911, 7308741084, 38682855225, 205940368441, 1102091393574, 5925177392573, 31987877317887, 173337754977904
Offset: 0
Keywords
Examples
a(2) = 5 because we have HH, UDH, HUD, UDUD and UUDD. G.f. = 1 + 2*x + 5*x^2 + 15*x^3 + 52*x^4 + 201*x^5 + 841*x^6 + ...
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..200
- J. Bloom and S. Elizalde, Pattern avoidance in matchings and partitions, arXiv:1211.3442 [math.CO], 2012; Theorem 6.1.
- Paul Barry, A study of Integer Sequences, Riordan Arrays, Pascal-like Arrays and Hankel Transforms, Ph.D Thesis, University College, Cork, Republic of Ireland, 2009.
- Arnauld Mesinga Mwafise, Computational and Combinatorial Enumeration of Poset Matrices, 2024. See p. 8.
Programs
-
Mathematica
CoefficientList[Series[4/(3-5*x+Sqrt[x^2-6*x+1]), {x, 0, 20}], x] (* Vaclav Kotesovec, May 23 2013 *) a[ n_] := SeriesCoefficient[ (3 - 5 x - Sqrt[ 1 - 6 x + x^2]) / (2 - 6 x + 6 x^2), {x, 0, n}]; (* Michael Somos, Mar 28 2014 *) -
Maxima
a(n):=sum((k+1)*((-1)^floor((k+2)/3)+(-1)^floor((k+1)/3))*sum(binomial(n+1,n-k-i)*binomial(n+i,n),i,0,n-k),k,0,n)/(2*(n+1)); /* Vladimir Kruchinin, Mar 08 2016*/
-
PARI
z='z+O('z^66); Vec(4/(3-5*z+sqrt(1-6*z+z^2))) /* Joerg Arndt, Mar 30 2013 */
Formula
G.f.: 4/(3-5*x+sqrt(1-6*x+x^2)).
Recurrence: n*a(n) = 9*(n-1)*a(n-1) - 2*(11*n-15)*a(n-2) + 3*(7*n-12)*a(n-3) - 3*(n-3)*a(n-4). - Vaclav Kotesovec, May 23 2013
a(n) ~ sqrt(884+627*sqrt(2)) * (3+2*sqrt(2))^n / (98*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, May 23 2013
0 = +a(n)*(+9*a(n+1) - 144*a(n+2) + 174*a(n+3) - 81*a(n+4) + 12*a(n+5)) + a(n+1)*(+18*a(n+1) + 399*a(n+2) - 597*a(n+3) + 318*a(n+4) - 57*a(n+5)) + a(n+2)*(-300*a(n+2) + 538*a(n+3) - 255*a(n+4) + 52*a(n+5)) + a(n+3)*(-126*a(n+3) + 73*a(n+4) - 18*a(n+5)) + a(n+4)*(+a(n+5)) if n>=0. - Michael Somos, Mar 28 2014
a(n) = Sum_{k=0..n}((k+1)*((-1)^floor((k+2)/3)+(-1)^floor((k+1)/3))*Sum_{i=0..n-k}(binomial(n+1,n-k-i)*binomial(n+i,n)))/(2*(n+1)). - Vladimir Kruchinin, Mar 08 2016
Comments