OFFSET
0,4
COMMENTS
Formula may be derived using the Lagrange Inversion theorem (cf. A049124).
a(n) is the 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
a(n) is the number of Schröder paths S of semilength n such that S has an odd number of horizontal (H) steps; and between each up step (that goes from y=i to y=i+1) and its matching down step (i.e., the next down step that goes from y=i+1 to y=i), there is an odd number of H steps. E.g., the a(5) = 12 such paths are UUUUHDDDD, UUHHHDD, UUHDHHD, UUHDDHH, UHUHDHD, UHHDHDD, UHDUHDH, UHDHUHD, HUUHDDH, HUHDUHD, HHUUHDD, and HHHHH. - Yu Hin Au, Jan 24 2026
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Yu Hin Au and Murray R. Bremner, A new generalization of the Narayana numbers inspired by linear operators on associative d-ary algebras, arXiv:2511.13671 [math.CO], 2025.
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.
Alyssa G. Henke, Kyle R. Hoffman, Derek H. Stephens, Yongwei Yuan, and Yan Zhuang, Restricted Jacobi permutations, arXiv:2509.11494 [math.CO], 2025. See pp. 5, 36, 38.
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
(SageMath) [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