login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A135307 Number of Dyck paths of semilength n that do not contain the string UDDU. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Eric S. Egge, 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.

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.

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,...

- Gary W. Adamson, Jan 30 2012

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

EXAMPLE

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

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 *)

CROSSREFS

Leading column of A135306.

Cf. A102403.

Column k=9 of A243753.

Sequence in context: A127384 A058585 A001573 * A000083 A092668 A164039

Adjacent sequences:  A135304 A135305 A135306 * A135308 A135309 A135310

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Dec 07 2007

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 01:06 EST 2018. Contains 299357 sequences. (Running on oeis4.)