0,4

Formula may be derived using the Lagrange Inversion theorem (cf. A049124).

a(n) = number of Dyck n-paths (A000108) all of whose descents have odd length. For example, a(3) counts UUUDDD, UDUDUD. - David Callan (callan(AT)stat.wisc.edu), Jul 25 2005

The number of noncrossing partitions of [n] with all blocks of odd size. E.g.: a(4)=5 with the five partitions being 123/4, 124/3, 134/2,1/234 and 1/2/3/4. - Lou Shapiro (lshapiro(AT)howard.edu), Jan 07 2006

Number of ordered trees with n edges in which every non-leaf vertex has an odd number of children. - David Callan (callan(AT)stat.wisc.edu), Mar 30 2007

a(n) = Sum_{k=0..[(n-1)/2]} C(n-k-1, k)*C(n, 2*k)/(2*k+1) for n>0, with a(0)=1. G.f.: A(x) = [ series reversion of x*(1-x^2)/(1+x-x^2) ]/x.

Generated from Fibonacci polynomials (A011973) and

coefficients of odd powers of 1/(1-x):

a(1) = 1*1/1

a(2) = 1*1/1 + 0*1/3

a(3) = 1*1/1 + 1*3/3

a(4) = 1*1/1 + 2*6/3 + 0*1/5

a(5) = 1*1/1 + 3*10/3 + 1*5/5

a(6) = 1*1/1 + 4*15/3 + 3*15/5 + 0*1/7

a(7) = 1*1/1 + 5*21/3 + 6*35/5 + 1*7/7

a(8) = 1*1/1 + 6*28/3 + 10*70/5 + 4*28/7 + 0*1/9

This process is equivalent to the formula:

a(n) = Sum_{k=0..[(n-1)/2]} C(n-k-1,k)*C(n,2*k)/(2*k+1).

(PARI) {a(n)=if(n==0, 1, sum(k=0, (n-1)\2, binomial(n-k-1, k)*binomial(n, 2*k)/(2*k+1)))}

Cf. A011973, A049124.

Sequence in context: A103287 A136704 A120895 this_sequence A003089 A112412 A125023

Adjacent sequences: A101782 A101783 A101784 this_sequence A101786 A101787 A101788

nonn

Paul D. Hanna (pauldhanna(AT)juno.com), Dec 16 2004