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

Comments

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

Links

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

Wikipedia, Counting lattice paths

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

Example

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.

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<y+2, 0, b(x-1, y+1, 0)+`if`(t=2, 0, b(x-1, y+1, 2))))
    end:
a:= n-> 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 *)

Crossrefs

Cf. A000108, A007863, A151403.

Sequence in context: A001246 A202827 A065735 * A381907 A182953 A327074

Adjacent sequences: A212691 A212692 A212693 * A212695 A212696 A212697

Keyword

nonn

Author

Alois P. Heinz, May 23 2012

Status

approved