A210735 - OEIS

%I #17 Mar 24 2017 03:48:19

%S 1,0,1,1,1,4,2,10,10,22,46,64,167,245,560,1035,1978,4210,7715,16497,

%T 31929,65216,133295,266244,553750,1116404,2308931,4738660,9742795,

%U 20204902,41622910,86539105,179358694,373018581,777157221,1618773690,3382590684,7065505631

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

%H Alois P. Heinz, <a href="/A210735/b210735.txt">Table of n, a(n) for n = 0..900</a>

%F a(n) ~ c * d^n / n^(3/2), where d = 2.1792514215908330337..., c = 0.4751731999905254789... . - _Vaclav Kotesovec_, Sep 02 2014

%e a(0) = 1: the empty path.

%e a(1) = 0.

%e a(2) = 1: UUDD.

%e a(3) = 1: UUUDDD.

%e a(4) = 1: UUDDUUDD.

%e a(5) = 4: UUDDUUUDDD, UUUDDDUUDD, UUUDDUUDDD, UUUUUDDDDD.

%e a(6) = 2: UUDDUUDDUUDD, UUUDDDUUUDDD.

%e a(7) = 10: UUDDUUDDUUUDDD, UUDDUUUDDDUUDD, UUDDUUUDDUUDDD, UUDDUUUUUDDDDD, UUUDDDUUDDUUDD, UUUDDUUDDDUUDD, UUUDDUUDDUUDDD, UUUUUDDDDDUUDD, UUUUUDDUUDDDDD, UUUUUUUDDDDDDD.

%e a(8) = 10: UUDDUUDDUUDDUUDD, UUDDUUUDDDUUUDDD, UUUDDDUUDDUUUDDD, UUUDDDUUUDDDUUDD, UUUDDDUUUDDUUDDD, UUUDDDUUUUUDDDDD, UUUDDUUDDDUUUDDD, UUUDDUUUDDDUUDDD, UUUUUDDDDDUUUDDD, UUUUUDDDUUUDDDDD.

%p with(numtheory):

%p b:= proc(x, y, u) option remember;

%p       `if`(x<0 or y<x, 0, `if`(x=0 and y=0, 1, `if`(u,

%p        add(b(x-ithprime(t), y, false), t=1..pi(x)),

%p        add(b(x, y-ithprime(t), true ), t=1..pi(y)))))

%p     end:

%p a:= n-> b(n$2, true):

%p seq(a(n), n=0..40);

%t 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]}]]]];

%t a[n_] := b[n, n, True];

%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Mar 24 2017, translated from Maple *)

%Y Cf. A210737.

%K nonn

%O 0,6

%A _Alois P. Heinz_, May 10 2012