A193215 Number of Dyck paths of semilength n having the property that the heights of the first and the last peaks coincide.

1, 2, 3, 6, 14, 38, 113, 356, 1164, 3906, 13364, 46426, 163294, 580316, 2080475, 7515038, 27324014, 99920756, 367264130, 1356043388, 5027345564, 18706888196, 69841532210, 261545298848, 982175296016, 3697785571820, 13954630170720, 52776659865348, 200006396351216, 759386612309146, 2888310863702017

Offset

1,2

Comments

a(n+1) - a(n) = A000958(n) (this reduces to David Callan's comment on A000958(n) from Aug 23 2011).

The sequence gives the trace of the matrix describing the statistics of Dyck paths of semilength n with respect to the heights of the first and the last peaks, see the paper of Baur and Mazorchuk.

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

K. Baur and V. Mazorchuk, Combinatorial analogues of ad-nilpotent ideals for untwisted affine Lie algebras, arXiv:1108.3659 [math.RA], 2011.

Formula

a(n) = 1 + Sum_{i=1..n-1} A000958(i).

Recurrence: 2*n*(5*n-11)*a(n) = 3*(15*n^2 - 53*n + 40)*a(n-1) - 3*(5*n^2 - 21*n + 20)*a(n-2) - 2*(2*n-5)*(5*n-6)*a(n-3). - Vaclav Kotesovec, Mar 21 2014

a(n) ~ 5*4^n/(27*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 21 2014

Maple

for n from 1 by 1 to 100 do 1+sum(binomial(2*n-2-2*k, n-1-k)-binomial(2*n-2-2*k, n-1-2*k), k = 1 .. n-1) end do

Mathematica

Table[1+Sum[Binomial[2*n-2-2*k, n-1-k]-Binomial[2*n-2-2*k, n-1-2*k], {k, 1, n-1}], {n, 1, 20}] (* Vaclav Kotesovec, Mar 21 2014 *)

Prog

(PARI) a(n)=1+sum(k=1, n-1, binomial(2*n-2-2*k, n-1-k)-binomial(2*n-2-2*k, n-1-2*k));

Crossrefs

Sequence in context: A049339 A157100 A081293 * A007611 A098641 A188775

Adjacent sequences: A193212 A193213 A193214 * A193216 A193217 A193218

Keyword

nonn,easy

Author

Volodymyr Mazorchuk, Aug 26 2011

Status

approved