A216435 Number of Dyck n-paths with equally spaced returns.

1, 1, 2, 3, 7, 15, 48, 133, 456, 1439, 5060, 16797, 60693, 208013, 760326, 2677217, 9879513, 35357671, 131763844, 477638701, 1790943777, 6566420517, 24748372638, 91482563641, 346597488614, 1289904685149, 4905215393598, 18370277279665, 70085754999907, 263747951750361

Offset

0,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Formula

a(0)=1, a(n) = Sum_{d|n} (binomial(2*d-2, d-1)/d)^(n/d) = Sum_{d|n} A000108(d-1)^(n/d) for n>=1.

Example

The 3 Dyck 3-paths are UUUDDD*, UUDUDD* and UD*UD*UD* where * marks the returns; the paths UD*UUDD* and UUDD*UD* do not have equally spaced returns.

Maple

with(numtheory):
a:= n->`if`(n=0, 1, add((binomial(2*d-2, d-1)/d)^(n/d), d=divisors(n))):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 10 2012

Mathematica

a={1}; For[n=1, n<=29, ++n, t=0; d=Divisors[n]; For[i=1, i<=Length[d], ++i, t+= (Binomial[2*d[[i]]-2, d[[i]]-1]/d[[i]])^(n/d[[i]])]; a=Append[a, t]; ]; a

Prog

(PARI)
C(n)=binomial(2*n, n)/(n+1);
a(n)=if(n==0, 1, sumdiv(n, d, C(d-1)^(n/d) ) );
/* Joerg Arndt, Sep 30 2012 */

Crossrefs

Cf. A000108.

Sequence in context: A213385 A045629 A034731 * A110888 A133736 A058698

Adjacent sequences: A216432 A216433 A216434 * A216436 A216437 A216438

Keyword

nonn

Author

David Scambler, Sep 10 2012

Status

approved