|
| |
|
|
A101785
|
|
G.f. satisfies: A(x) = 1 + x*A(x)/(1 - x^2*A(x)^2).
|
|
10
|
|
|
|
1, 1, 1, 2, 5, 12, 30, 79, 213, 584, 1628, 4600, 13138, 37871, 110043, 321978, 947813, 2805104, 8341608, 24912004, 74686460, 224694128, 678143656, 2052640752, 6229616730, 18952875247, 57792705415, 176596786934, 540679385663
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
