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

Author

David Scambler, Sep 10 2012

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A000108.

Programs

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

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 */

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.