OFFSET
0,4
COMMENTS
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, 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. - _Louis_ Shapiro, Jan 07 2006
Number of ordered trees with n edges in which every non-leaf vertex has an odd number of children. - David Callan, Mar 30 2007
Number of valid hook configurations of permutations of [n] that avoid the patterns 312 and 321. - Colin Defant, Apr 28 2019
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Colin Defant, Motzkin intervals and valid hook configurations, arXiv preprint arXiv:1904.10451 [math.CO], 2019.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Vaclav Kotesovec, Asymptotic of subsequences of A212382
Helmut Prodinger, Partial Dyck path interpretation for three sequences in the Encyclopedia of Integer Sequences, arXiv:2408.01290 [math.CO], 2024.
FORMULA
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.: (1/x) * Series_Reversion( x*(1-x^2)/(1+x-x^2) ).
Recurrence: 4*n*(n+1)*(91*n^2 - 379*n + 360)*a(n) = 6*n*(182*n^3 - 849*n^2 + 1075*n - 264)*a(n-1) - 2*(182*n^4 - 1122*n^3 + 2011*n^2 - 603*n - 648)*a(n-2) + 6*(n-3)*(364*n^3 - 1698*n^2 + 2267*n - 696)*a(n-3) - 5*(n-4)*(n-3)*(91*n^2 - 197*n + 72)*a(n-4). - Vaclav Kotesovec, Sep 17 2013
a(n) ~ c*d^n/(sqrt(Pi)*n^(3/2)), where d = 3/4 + 1/(4*sqrt(3/(19 - 304/(4103 + 273*sqrt(273))^(1/3) + 2*(4103 + 273*sqrt(273))^(1/3)))) + 1/2*sqrt(19/6 + 76/(3*(4103 + 273*sqrt(273))^(1/3)) - 1/6*(4103 + 273*sqrt(273))^(1/3) + 63/2*sqrt(3/(19 - 304/(4103 + 273*sqrt(273))^(1/3) + 2*(4103 + 273*sqrt(273))^(1/3)))) = 3.228704951094501729... is the root of the equation 5 - 24*d + 4*d^2 - 12*d^3 + 4*d^4 = 0 and c = 0.82499074317860885542266460957609663272... is the root of the equation -125 - 3376*c^2 - 22080*c^4 - 23296*c^6 + 93184*c^8 = 0. - Vaclav Kotesovec, added Sep 17 2013, updated Jan 04 2014
G.f.: 1/(9*(3-3*x+x^2))*(x^2+27- x^2*(2*x+3)^3*(x-6)^3/(9*(3-3*x+x^2)^3*S(0) - x^2*(2*x+3)^2*(x-6)^2 )), where S(k) = 4*k+3 - x^2*(2*x^2-9*x-18)^2*(3*k+4)*(6*k+5)/( 18*(4*k+5)*(3-3*x+x^2)^3 - x^2*(2*x^2-9*x-18)^2*(3*k+5)*(6*k+7)/S(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 26 2013
EXAMPLE
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).
MATHEMATICA
Flatten[{1, Table[Sum[Binomial[n-k-1, k]*Binomial[n, 2*k]/(2*k+1), {k, 0, Floor[(n-1)/2]}], {n, 1, 20}]}] (* Vaclav Kotesovec, Sep 17 2013 *)
CoefficientList[InverseSeries[Series[x*(1-x^2)/(1+x-x^2), {x, 0, 30}], x]/x, x] (* G. C. Greubel, May 03 2019 *)
PROG
(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)))}
for(n=1, 40, print1(a(n), ", "))
(PARI) N=66; Vec(serreverse(x/(1+sum(k=1, N, x^(2*k-1)))+O(x^N))/x) /* Joerg Arndt, Aug 19 2012 */
(Magma) [n eq 0 select 1 else (&+[Binomial(n-k-1, k)*Binomial(n, 2*k)/(2*k+1): k in [0..Floor((n-1)/2)]]): n in [0..30]]; // G. C. Greubel, May 03 2019
(Sage) [1]+[sum(binomial(n-k-1, k)*binomial(n, 2*k)/(2*k+1) for k in (0..floor((n-1)/2))) for n in (1..30)] # G. C. Greubel, May 03 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Dec 16 2004
STATUS
approved