A116914 Number of UUDD's, where U=(1,1) and D=(1,-1), in all hill-free Dyck paths of semilength n (a hill in a Dyck path is a peak at level 1).
1, 1, 5, 16, 58, 211, 781, 2920, 11006, 41746, 159154, 609324, 2341060, 9021559, 34855741, 134972368, 523689718, 2035462990, 7923732118, 30889008112, 120566373676, 471134916286, 1842964183570, 7216096752496, 28279240308268, 110913181145716, 435333520075796, 1709861650762900
Offset: 2
Keywords
Examples
a(4)=5 because in the 6 (=A000957(5)) hill-free Dyck paths of semilength 4, namely UU(UUDD)DD, UUUDUDDD, UUD(UUDD)D, UUDUDUDD, U(UUDD)UDD and (UUDD)(UUDD) (U=(1,1), D=(1,-1)) we have altogether 5 UUDD's (shown between parentheses).
Links
- G. C. Greubel, Table of n, a(n) for n = 2..1000
- David Anderson, E. S. Egge, M. Riehl, L. Ryan, R. Steinke, Y. Vaughan, Pattern Avoiding Linear Extensions of Rectangular Posets, arXiv:1605.06825 [math.CO], 2016.
- Colin Defant, Proofs of Conjectures about Pattern-Avoiding Linear Extensions, arXiv:1905.02309 [math.CO], 2019.
- E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Crossrefs
Cf. A105640.
Programs
-
Magma
R
:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( x*(1 + 5*x-(1-x)*Sqrt(1-4*x))/(2*(2+x)^2*Sqrt(1-4*x)) )); // G. C. Greubel, May 08 2019 -
Maple
G:=z*(1+5*z-(1-z)*sqrt(1-4*z))/2/(2+z)^2/sqrt(1-4*z): Gser:=series(G,z=0,31): seq(coeff(Gser,z^n),n=2..28);
-
Mathematica
Rest[Rest[CoefficientList[Series[x*(1+5*x-(1-x)*Sqrt[1-4*x])/2/(2+x)^2/Sqrt[1-4*x], {x, 0, 40}], x]]] (* Vaclav Kotesovec, Mar 20 2014 *) -
PARI
my(x='x+O('x^40)); Vec(x*(1+5*x-(1-x)*sqrt(1-4*x))/(2*(2+x)^2 *sqrt(1-4*x))) \\ G. C. Greubel, Feb 08 2017 -
Sage
a=(x*(1+5*x-(1-x)*sqrt(1-4*x))/(2*(2+x)^2*sqrt(1-4*x))).series(x, 40).coefficients(x, sparse=False); a[2:] # G. C. Greubel, May 08 2019
Formula
a(n) = Sum_{k=0..floor(n/2)} k*A105640(n,k).
G.f.: x*(1 + 5*x - (1-x)*sqrt(1-4*x))/(2*(2+x)^2*sqrt(1-4*x)).
a(n+2) = A126258(2*n,n). - Philippe Deléham, Mar 13 2007
a(n) ~ 2^(2*n-1)/(9*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 20 2014
D-finite with recurrence +2*(-n+1)*a(n) +3*(-n+6)*a(n-1) +3*(13*n-44)*a(n-2) +10*(2*n-5)*a(n-3)=0. - R. J. Mathar, Jul 26 2022
Comments