login
Number of hill-free Dyck paths of semilength n+3 and having length of first descent equal to 1 (a hill in a Dyck path is a peak at level 1).
(Formerly M2845 N1143)
7

%I M2845 N1143 #66 Jul 05 2022 03:26:25

%S 1,3,10,33,111,379,1312,4596,16266,58082,209010,757259,2760123,

%T 10114131,37239072,137698584,511140558,1904038986,7115422212,

%U 26668376994,100221202998,377570383518,1425706128480,5394898197448,20454676622476

%N Number of hill-free Dyck paths of semilength n+3 and having length of first descent equal to 1 (a hill in a Dyck path is a peak at level 1).

%C a(n) is also the number of even-length descents to ground level in all Dyck paths of semilength n+2. Example: a(1)=3 because in UDUDUD, UDUU(DD), UU(DD)UD, UUDU(DD) and UUUDDD we have 3 even-length descents to ground level (shown between parentheses). - _Emeric Deutsch_, Oct 05 2008

%C Convolution of A000108 with A104629. - _Philippe Deléham_, Nov 11 2009

%C The Kn12 triangle sums of A039599 are given by the terms of this sequence. For the definition of this and other triangle sums see A180662. - _Johannes W. Meijer_, Apr 20 2011

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A001558/b001558.txt">Table of n, a(n) for n = 0..1000</a>

%H E. Deutsch and L. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., 241 (2001), 241-265.

%H T. Fine, <a href="http://dx.doi.org/10.1016/S0019-9958(70)90177-4">Extrapolation when very little is known about the source</a>, Information and Control 16 (1970), 331-359.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="http://arxiv.org/abs/0912.0072">Une méthode pour obtenir la fonction génératrice d'une série</a>. FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

%F a(n) = A000957(n+4) - A000957(n+3) - A000957(n+2) (A000957 are the Fine numbers). - _Emeric Deutsch_, May 08 2006

%F a(n) = A118972(n+3,1). - _Emeric Deutsch_, May 08 2006

%F G.f.: F*C^3, where F = (1-sqrt(1-4z))/(z*(3-sqrt(1-4z))) and C = (1-sqrt(1-4z))/(2z) is the Catalan function. - _Emeric Deutsch_, May 08 2006

%F a(n) = Sum_{k>=0} k*A111301(n+2,k). - _Emeric Deutsch_, Oct 05 2008

%F (n+3)*a(n) = (-(11/2)*n + 21/2)*a(n-3) + ((9/2)*n + 11/2)*a(n-1) + (-(1/2)*n + 9/2)*a(n-2) + (-2n + 5)*a(n-4). - _Simon Plouffe_, Feb 09 2012

%F a(n) ~ 11*2^(2*n+4)/(9*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Mar 20 2014

%e a(1)=3 because we have uu(d)ududd, uuu(d)uddd and uu(d)uuddd, where u=(1,1), d=(1,-1) (the first descents are shown between parentheses).

%e G.f. = 1 + 3*x + 10*x^2 + 33*x^3 + 111*x^4 + 379*x^5 + 1312*x^6 + ...

%p F:=(1-sqrt(1-4*z))/z/(3-sqrt(1-4*z)): C:=(1-sqrt(1-4*z))/2/z: g:=F*C^3: gser:=series(g,z=0,32): seq(coeff(gser,z,n),n=0..27); # _Emeric Deutsch_, May 08 2006

%t CoefficientList[Series[(1-Sqrt[1-4*x])/(x*(3-Sqrt[1-4*x]))*((1-Sqrt[1-4*x])/(2*x))^3, {x, 0, 30}], x] (* _Vaclav Kotesovec_, Mar 20 2014 *)

%o (PARI) my(x='x+O('x^30)); Vec((1-sqrt(1-4*x))/(x*(3-sqrt(1-4*x)))*((1-sqrt(1-4*x))/(2*x))^3) \\ _G. C. Greubel_, Feb 12 2019

%o (Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!( (1-Sqrt(1-4*x))/(x*(3-Sqrt(1-4*x)))*((1-Sqrt(1-4*x))/(2*x))^3 )); // _G. C. Greubel_, Feb 12 2019

%o (Sage) ((1-sqrt(1-4*x))/(x*(3-sqrt(1-4*x)))*((1-sqrt(1-4*x))/(2*x))^3).series(x, 30).coefficients(x, sparse=False) # _G. C. Greubel_, Feb 12 2019

%Y Cf. A000957, A118972, A118973.

%Y Cf. A111301. - _Emeric Deutsch_, Oct 05 2008

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_

%E Edited by _Emeric Deutsch_, May 08 2006