cp's OEIS Frontend

A217539 Number of Dyck paths of semilength n which satisfy the condition: number of returns + number of hills < number of peaks.

%I A217539 #25 May 06 2021 08:11:29
%S A217539 0,0,0,1,4,17,66,252,946,3523,13054,48248,178146,657813,2430962,
%T A217539 8995521,33342588,123822171,460772982,1718304786,6421729878,
%U A217539 24051429321,90272123682,339522804129,1279556832780,4831639423695,18278491474726,69272752632502,262981858878706
%N A217539 Number of Dyck paths of semilength n which satisfy the condition: number of returns + number of hills < number of peaks.
%C A217539 _David Scambler_ observed that [1, 0, A113682(n-2)] for n>=2 count the Dyck paths of semilength n which satisfy the condition "number of peaks = number of returns + number of hills" and [1, A189912(n-1)] for n>=1 count the paths which satisfy the condition "number of peaks <= number of returns + number of hills".
%F A217539 a(n) = Sum_{k < 0} A217540(n, k).
%F A217539 a(n) = A000108(n) - A189912(n-1) for n > 0.
%F A217539 a(n) = C(n)-(n-1)*M(n-2)-M(n-1) for n > 0; C(n) Catalan, M(n) Motzkin numbers.
%F A217539 Conjecture: 2*(n+1)*(n-3)*a(n) +(-15*n^2+53*n-12)*a(n-1) +(28*n^2-157*n+165)*a(n-2) + 3*(3*n^2+2*n-26)*a(n-3) -18*(2*n-7)*(n-4)*a(n-4)=0. - _R. J. Mathar_, Nov 11 2012
%e A217539 a(4) = 4 count the Dyck words
%e A217539 [11010100] (()()()) [11011000] (()(()))
%e A217539 [11100100] ((())()) [11101000] ((()())) .
%p A217539 A217539 := proc(n) local k; if n = 0 then 0 else (2*n)!/(n!^2*(n+1)) - add((n-1)!/(((n-1-k)!*iquo(k,2)!^2)*(iquo(k,2)+1)), k=0..n-1) fi end: seq(A217539(i), i=0..28);
%t A217539 MotzkinNumber[n_] := Sum[ Binomial[n+1, k]*Binomial[n+1-k, k-1], {k, 0, Ceiling[(n+1)/2]}]/(n+1); a[0] = a[1] = 0; a[n_] := CatalanNumber[n] - (n-1)*MotzkinNumber[n-2] - MotzkinNumber[n-1]; Table[a[n], {n, 0, 28}] (* _Jean-François Alcover_, Jun 27 2013, from 3rd formula *)
%o A217539 (Sage)
%o A217539 def A217539(n):
%o A217539     @CachedFunction
%o A217539     def M(n): return (3*(n-1)*M(n-2)+(2*n+1)*M(n-1))/(n+2) if n>1 else 1
%o A217539     @CachedFunction
%o A217539     def catalan(n): return ((4*n-2)*catalan(n-1))/(n+1) if n>0 else 1
%o A217539     return catalan(n) - (n-1)*M(n-2) - M(n-1) if n!=0 else 0
%o A217539 [A217539(i) for i in (0..28)]
%Y A217539 Cf. A217540.
%K A217539 nonn
%O A217539 0,5
%A A217539 _Peter Luschny_, Oct 22 2012