A210735 Number of Dyck n-paths all of whose ascents and descents have prime lengths.

1, 0, 1, 1, 1, 4, 2, 10, 10, 22, 46, 64, 167, 245, 560, 1035, 1978, 4210, 7715, 16497, 31929, 65216, 133295, 266244, 553750, 1116404, 2308931, 4738660, 9742795, 20204902, 41622910, 86539105, 179358694, 373018581, 777157221, 1618773690, 3382590684, 7065505631

Offset

0,6

Links

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

Formula

a(n) ~ c * d^n / n^(3/2), where d = 2.1792514215908330337..., c = 0.4751731999905254789... . - Vaclav Kotesovec, Sep 02 2014

Example

a(0) = 1: the empty path.
a(1) = 0.
a(2) = 1: UUDD.
a(3) = 1: UUUDDD.
a(4) = 1: UUDDUUDD.
a(5) = 4: UUDDUUUDDD, UUUDDDUUDD, UUUDDUUDDD, UUUUUDDDDD.
a(6) = 2: UUDDUUDDUUDD, UUUDDDUUUDDD.
a(7) = 10: UUDDUUDDUUUDDD, UUDDUUUDDDUUDD, UUDDUUUDDUUDDD, UUDDUUUUUDDDDD, UUUDDDUUDDUUDD, UUUDDUUDDDUUDD, UUUDDUUDDUUDDD, UUUUUDDDDDUUDD, UUUUUDDUUDDDDD, UUUUUUUDDDDDDD.
a(8) = 10: UUDDUUDDUUDDUUDD, UUDDUUUDDDUUUDDD, UUUDDDUUDDUUUDDD, UUUDDDUUUDDDUUDD, UUUDDDUUUDDUUDDD, UUUDDDUUUUUDDDDD, UUUDDUUDDDUUUDDD, UUUDDUUUDDDUUDDD, UUUUUDDDDDUUUDDD, UUUUUDDDUUUDDDDD.

Maple

with(numtheory):
b:= proc(x, y, u) option remember;
      `if`(x<0 or y<x, 0, `if`(x=0 and y=0, 1, `if`(u,
       add(b(x-ithprime(t), y, false), t=1..pi(x)),
       add(b(x, y-ithprime(t), true ), t=1..pi(y)))))
    end:
a:= n-> b(n$2, true):
seq(a(n), n=0..40);

Mathematica

b[x_, y_, u_] := b[x, y, u] = If[x<0 || y<x, 0, If[x==0 && y==0, 1, If[u, Sum[b[x-Prime[t], y, False], {t, 1, PrimePi[x]}], Sum[b[x, y-Prime[t], True], {t, 1, PrimePi[y]}]]]];
a[n_] := b[n, n, True];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 24 2017, translated from Maple *)

Crossrefs

Cf. A210737.

Sequence in context: A185732 A121794 A250108 * A075086 A284782 A128781

Adjacent sequences: A210732 A210733 A210734 * A210736 A210737 A210738

Keyword

nonn

Author

Alois P. Heinz, May 10 2012

Status

approved