A212694 Number of 2-colored Dyck n-paths with up steps (U, u), down steps (D, d), and avoiding UU and DD.

1, 4, 25, 197, 1745, 16580, 165115, 1700809, 17971466, 193710087, 2121585340, 23543198588, 264138223362, 2991130956918, 34143543312267, 392458689992396, 4538574332686469, 52768896995910303, 616471818881678085, 7232838546289017796, 85188401983572928395

Offset: 0

Author

Alois P. Heinz, May 23 2012

Keywords

• nonn

Comments

Upper case letters denote one color and lower case letters the other.

Examples

			a(1) = 4: ud, Ud, uD, UD.
a(2) = 25: uudd, Uudd, uUdd, uuDd, UuDd, uUDd, udud, Udud, uDud, UDud, udUd, UdUd, uDUd, UDUd, uudD, UudD, uUdD, uduD, UduD, uDuD, UDuD, udUD, UdUD, uDUD, UDUD.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..910
• Wikipedia, Counting lattice paths

Crossrefs

Cf. A000108, A007863, A151403.

Programs

Maple

b:= proc(x, y, t) option remember; `if`(x=0, 1,
      `if`(y<1  , 0, b(x-1, y-1, 0)+`if`(t=1, 0, b(x-1, y-1, 1)))+
      `if`(x b(2*n, 0$2):
seq(a(n), n=0..30);

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[x == 0, 1, If[y < 1, 0, b[x - 1, y - 1, 0] + If[t == 1, 0, b[x - 1, y - 1, 1]]] + If[x < y + 2, 0, b[x - 1, y + 1, 0] + If[t == 2, 0, b[x - 1, y + 1, 2]]]];
a[n_] := b[2n, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 02 2018, from Maple *)

Formula

Recurrence: 5*n*(n+1)*(n+2)*(11856*n^6 - 462048*n^5 + 6376819*n^4 - 42412433*n^3 + 147659510*n^2 - 260432089*n + 184927095)*a(n) = n*(n+1)*(1683552*n^7 - 66428880*n^6 + 937628962*n^5 - 6466755025*n^4 + 23922419618*n^3 - 47274340850*n^2 + 44490285903*n - 13108829940)*a(n-1) - n*(14310192*n^8 - 585624672*n^7 + 8802419365*n^6 - 66744441981*n^5 + 284660409448*n^4 - 703230360993*n^3 + 976943147665*n^2 - 682900257024*n + 175305383460)*a(n-2) + 2*(17238624*n^9 - 746332752*n^8 + 12295273466*n^7 - 105941663163*n^6 + 537013083761*n^5 - 1677467513328*n^4 + 3243096592679*n^3 - 3743377415442*n^2 + 2332897216785*n - 592736810400)*a(n-3) - (37974768*n^9 - 1728832752*n^8 + 30714335273*n^7 - 291055104422*n^6 + 1652510618897*n^5 - 5890634883203*n^4 + 13267453974662*n^3 - 18291224811263*n^2 + 14073816074160*n - 4638445144200)*a(n-4) + (23308896*n^9 - 1108835760*n^8 + 20950004098*n^7 - 213362099351*n^6 + 1311302140489*n^5 - 5085585201440*n^4 + 12508042515937*n^3 - 18889708965719*n^2 + 15984167161110*n - 5834960787600)*a(n-5) - (8927568*n^9 - 442319616*n^8 + 8817227331*n^7 - 95321285525*n^6 + 623567997102*n^5 - 2575734547859*n^4 + 6742249614729*n^3 - 10822975984520*n^2 + 9730758446550*n - 3782772932400)*a(n-6) + 4*(2*n - 13)*(248976*n^8 - 11244288*n^7 + 197289135*n^6 - 1812121625*n^5 + 9661474889*n^4 - 30841990357*n^3 + 57959845045*n^2 - 59304520365*n + 25796647800)*a(n-7) - 4*(n-7)*(2*n - 15)*(2*n - 13)*(11856*n^6 - 390912*n^5 + 4244419*n^4 - 21288517*n^3 + 54240485*n^2 - 69082196*n + 35668710)*a(n-8). - Vaclav Kotesovec, Jul 16 2014

Limit n->infinity a(n)^(1/n) = (13+3*sqrt(17))/2 = 12.68465843842649... . - Vaclav Kotesovec, Jul 16 2014