A166290 Number of UDUD's in all Dyck paths of semilength n with no UUU's and no DDD's (U=(1,1), D=(1,-1)).

0, 0, 1, 3, 9, 24, 63, 164, 423, 1088, 2794, 7168, 18385, 47158, 120991, 310537, 797381, 2048456, 5265059, 13539331, 34834238, 89665630, 230913976, 594938458, 1533501169, 3954384384, 10201142803, 26326101399, 67964928779, 175524139820

Offset

0,4

Links

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

Formula

a(n) = Sum_{k>=0} k*A166288(n,k).

G.f. = (z-1)*(z+2)/(2*z^2) + (2-3*z-2*z^2-2*z^3+z^4) / [2*z^2*sqrt((1+z+z^2)*(1-3z+z^2))].

a(n) ~ sqrt(4 + 9/sqrt(5)) * (3+sqrt(5))^n / (sqrt(Pi*n) * 2^(n+1)). - Vaclav Kotesovec, Mar 20 2014. Equivalently, a(n) ~ phi^(2*n + 3) / (2 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021

Conjecture: -(n+2)*(60283*n-319055)*a(n) +(-60283*n^2-13090*n+236862)*a(n-1) +(588710*n^2-2858167*n+437486)*a(n-2) +(-32043*n^2+2024290*n-2826488)*a(n-3) +(134686*n^2+585099*n-3417942)*a(n-4) +(-514307*n^2+4366464*n-8945002)*a(n-5) +(166729*n-863288)*(n-6)*a(n-6)=0. - R. J. Mathar, Jun 14 2016

Example

a(3)=3 because UDUDUD, UDUUDD, UUDDUD, and UUDUDD have 2+0+0+1=3 UDUD's.

Maple

g := (1/2)*(z-1)*(z+2)/z^2+((2-3*z-2*z^2-2*z^3+z^4)*1/2)/(z^2*sqrt((1+z+z^2)*(1-3*z+z^2))): gser := series(g, z = 0, 35): seq(coeff(gser, z, n), n = 0 .. 30);

Mathematica

CoefficientList[Series[(1/2)*(x-1)*(x+2)/x^2+((2-3*x-2*x^2-2*x^3+x^4)*1/2) /(x^2*Sqrt[(1+x+x^2)*(1-3*x+x^2)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)

Prog

(PARI) x='x+O('x^50); concat([0, 0], Vec((1/2)*(x-1)*(x+2)/x^2+((2-3*x-2*x^2-2*x^3+x^4)) /(2*x^2*sqrt((1+x+x^2)*(1-3*x+x^2))))) \\ G. C. Greubel, Mar 22 2017

Crossrefs

Cf. A166288.

Sequence in context: A268938 A090400 A123888 * A097134 A123892 A269531

Adjacent sequences: A166287 A166288 A166289 * A166291 A166292 A166293

Keyword

nonn

Author

Emeric Deutsch, Oct 12 2009

Status

approved