A135307 Number of Dyck paths of semilength n that do not contain the string UDDU.

1, 1, 2, 4, 9, 23, 63, 178, 514, 1515, 4545, 13827, 42540, 132124, 413741, 1304891, 4141198, 13214815, 42375461, 136478383, 441285890, 1431925180, 4661485203, 15219836738, 49827678840, 163535624722, 537962562453, 1773437280323

Offset: 0

Author

N. J. A. Sloane, Dec 07 2007

Keywords

• nonn
• easy

Comments

Top left terms of powers of the production matrix M generates sequence A102403. - Gary W. Adamson, Jan 30 2012

Examples

			a(6) = 63 since the top row of M^5 = (17, 17, 13, 10, 5, 1), sum of terms = 63.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Eric S. Egge and Kailee Rubin, Snow Leopard Permutations and Their Even and Odd Threads, arXiv:1508.05310 [math.CO], 2015
• A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Crossrefs

Leading column of A135306.

Cf. A102403.

Column k=9 of A243753.

Programs

Maple

A135306 := proc(n,k) if n =0 then 1 ; else add((-1)^(j-k)*binomial(n-k,j-k)*binomial(2*n-3*j,n-j+1),j=k..floor((n-1)/2)) ; %*binomial(n,k)/n ; fi ; end: A135307 := proc(n) A135306(n,0) ; end: for n from 0 to 30 do printf("%a, ",A135307(n)) ; od: # R. J. Mathar, Dec 08 2007
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [1$2, 2, 4][n+1],
      (2*n*(n-1)*(28*n^2-56*n-3)*a(n-1)
       +(140*n^4-630*n^3+1063*n^2-699*n+144)*a(n-2)
       -12*(n-3)*(14*n^3-42*n^2+16*n+21)*a(n-3)
       +23*(n-3)*(n-4)*(28*n^2-14*n-3)*a(n-4))/
       (n*(n+1)*(28*n^2-70*n+39)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 13 2014

Mathematica

a[n_] := Sum[(-1)^j*Binomial[n, j]*Binomial[2*n-3*j, n-j+1], {j, 0, (n-1)/2}]/n; a[0] = 1; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Nov 27 2014, after R. J. Mathar *)

Formula

G.f.: f(x) satisfies x*f(x)^3 - (x+1)*f(x)^2 + (2*x+1)*f(x) - x = 0 . - Eric Rowland, Mar 29 2013

The Sapounakis et al. reference gives an explicit formula.

From Gary W. Adamson, Jan 30 2012: (Start)

a(n) is the sum of top row terms in M^(n-1), where M = the following infinite square production matrix:

1, 1, 0, 0, 0, 0, ...

0, 1, 1, 0, 0, 0, ...

1, 0, 1, 1, 0, 0, ...

1, 1, 0, 1, 1, 0, ...

1, 1, 1, 0, 1, 1, ... (End)

a(n) ~ sqrt(8 + 5*sqrt(2) + sqrt(2*(11 + 8*sqrt(2))/7))/4 * ((1 + sqrt(13 + 16*sqrt(2)))/2)^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jan 27 2015

Extensions

More terms from R. J. Mathar, Dec 08 2007