OFFSET
1,2
COMMENTS
a(n) is the number of Dyck paths of semilength n for which all non-terminal descents are of odd length. For example, a(3) = 4 counts all 5 Dyck paths of semilength 3 except UUDDUD and a(4) = 9 counts, among others, UUUDUDDD and UUDUDUDD but not UUDDUUDD. - David Callan, Nov 13 2021
LINKS
S. Elizalde, Generating trees for permutations avoiding generalized patterns, arXiv:0707.4633 [math.CO], 2007; Annals of Combinatorics 11 (2007), 435-458.
Helmut Prodinger, Partial Dyck path interpretation for three sequences in the Encyclopedia of Integer Sequences, arXiv:2408.01290 [math.CO], 2024.
FORMULA
a(n) = (1/n)*Sum_{k=0..floor(n/2)} 2*binomial(n,2k)*binomial(n-k,k-1) + n*binomial(n,2k+1)*binomial(n-k,k)/(n-k).
G.f. G(x) satisfies x*G^3 + (4x-2)*G^2 + (4x-1)*G + x = 0.
Conjecture: -8*n*(n+1)*a(n) + 4*n*(2*n+5)*a(n-1) + 4*n*(n+7)*a(n-2) + 2*(70*n^2-395*n+564)*a(n-3) + 2*(25*n^2-143*n+222)*a(n-4) + 4*(49*n-228)*(n-5)*a(n-5) - 45*(n-5)*(n-6)*a(n-6) = 0. - R. J. Mathar, Mar 14 2014
Recurrence (of order 4): 4*n*(n+1)*(91*n^2 - 217*n + 102)*a(n) = 6*n*(182*n^3 - 525*n^2 + 365*n - 78)*a(n-1) - 4*(91*n^4 - 399*n^3 - 136*n^2 + 990*n - 450)*a(n-2) + 12*(n-3)*(182*n^3 - 525*n^2 + 92*n + 140)*a(n-3) - 5*(n-4)*(n-3)*(91*n^2 - 35*n - 24)*a(n-4). - Vaclav Kotesovec, Mar 20 2014
MAPLE
a:=proc(n) options operator, arrow: (sum(2*binomial(n, 2*k)*binomial(n-k, k-1)+n*binomial(n, 2*k+1)*binomial(n-k, k)/(n-k), k=0..floor((1/2)*n)))/n end proc: seq(a(n), n=1..27);
MATHEMATICA
Table[1/n*Sum[2*Binomial[n, 2k]*Binomial[n-k, k-1]+ n*Binomial[n, 2k+1] *Binomial[n-k, k]/(n-k), {k, 0, n-1}], {n, 1, 20}] (* Vaclav Kotesovec, Mar 20 2014 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jul 17 2008
STATUS
approved