|
| |
|
|
A109081
|
|
Reversion of x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6) = x*(1-x)^2/(1-x+x^2).
|
|
25
|
|
|
|
1, 1, 3, 10, 37, 146, 602, 2563, 11181, 49720, 224540, 1027038, 4748042, 22150519, 104146733, 493012682, 2347796965, 11239697816, 54061835288, 261130778516, 1266125122956, 6160158505040, 30065608532008, 147161532388934
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
a(n) is the number of vertex-labeled ordered trees (A000108) on n vertices, in which each non-leaf vertex is labeled with a positive integer <= its outdegree. Example. a(3)=3 counts the trees on 3 vertices with labels as shown (the 2 edges in each tree are shown, you have to visualize the vertices).
.
1 2 1
/ \ / \ |1
|
.
Proof. Let F(x) = x + x^2 + 3x^3 + ... denote the g.f. for these trees, with x marking number of vertices. Counting these trees by degree of the root leads to F = x + Sum_{k>=1} k*x*F^k, or F = x + x*F/(1-F)^2. This is the same equation as that satisfied by the reversion of x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6) = x*(1-x)^2/(1-x+x^2). (End)
(1 + 3x + 10x^2 + ...) = (1 + 2x + 6x^2 + ...)*(1 + x + 2x^2 + 6x^3 + ...), where A106228 = (1, 1, 2, 6, 21, ...). - Gary W. Adamson, Nov 15 2011
a(n) is the number of Motzkin paths of length 2n-3 with no downsteps in even position (n>=2). Example: a(3)=3 counts FFF, FUD, UFD, where U denotes an upstep (1,1), F a flatstep (1,0), and D a downstep (1,-1). - David Callan, May 20 2015
a(n) is the number of peakless Motzkin paths of length 2n-2 where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on 2n-2 vertices where only vertices of the same parity can be matched. - Alexander Burstein, May 17 2021
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f. A(x) satisfies 0 = f(x, A(x)) where f(x, y) = x*(1 - y + y^2) - y*(1 - y)^2.
G.f. A(x) satisfies 0 = f(x, A(x)) where f(x, y) = y*(1 - y)*((1 - y) / x + 1) - 1.
G.f. satisfies: A(x) = x/(1 - x/(1 - A(x))^2).
a(n) = Sum_{k=0..n} C(n,k)/(n-k+1) * C(n+k-1,n-k). (End)
a(n) is the upper left term in M^(n-1), M = an infinite square matrix as follows:
1, 1, 0, 0, 0, ...
2, 1, 1, 0, 0, ...
3, 2, 1, 1, 0, ...
4, 3, 2, 1, 1, ...
5, 4, 3, 2, 1, ...
... (End)
With different signs, g.f. = 2/(3-sqrt(1-4xC(x))) where C = g.f. for A000108 [He-Shapiro]. - N. J. A. Sloane, Apr 28 2017
Recurrence: 2*n*(2*n - 1)*(19*n^2 - 85*n + 90)*a(n) = 2*(190*n^4 - 1230*n^3 + 2783*n^2 - 2595*n + 828)*a(n-1) + 2*(n-3)*(38*n^3 - 189*n^2 + 289*n - 132)*a(n-2) + 3*(n-4)*(n-3)*(19*n^2 - 47*n + 24)*a(n-3).
a(n) ~ (1 - (1-s)*s)^(n + 1/2) / (2*sqrt(Pi*(3 - 6*s + s^2)) * n^(3/2) * s^n * (1-s)^(2*n-2)), where s = 0.3611030805286473776346465621590281395264149... is the real root of the equation (s^2 - s + 3)*s = 1. (End)
|
|
|
EXAMPLE
|
a(5) = 37 = the upper left term of M^4: (37, 26, 12, 4, 1); where (37 + 26 + 12 + 4 + 1) = 80 = A106228(5). - Gary W. Adamson, Nov 15 2011
G.f. = x + x^2 + 3*x^3 + 10*x^4 + 37*x^5 + 146*x^6 + 602*x^7 + 2563*x^8 + ...
|
|
|
MAPLE
|
S:= series(RootOf(-x*z^2+z^3+x*z-2*z^2-x+z, z), x, 101):
|
|
|
MATHEMATICA
|
a[ n_] := If[ n < 2, Boole[n == 1], (n - 1) HypergeometricPFQ[ {n, 1 - n, 2 - n}, {3/2, 2}, 1/4]]; (* Michael Somos, May 28 2014 *)
Join[{1}, Table[Sum[ Binomial[n, k] / (n-k+1) Binomial[n+k-1, n-k], {k, n}], {n, 25}]] (* Vincenzo Librandi, Sep 23 2015 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<1, 0, polcoeff( serreverse( x * (1 - x) * (1 - x^2) * (1 - x^3) / (1 - x^6) + x * O(x^n)), n))};
(PARI) {a(n)=sum(k=0, n, binomial(n, k)/(n-k+1)*binomial(n+k-1, n-k))} \\ Paul D. Hanna, Jun 19 2009
(Sage)
return (n-1)*hypergeometric([n, 1-n, 2-n], [3/2, 2], 1/4) if n > 1 else 1
(Magma) [&+[Binomial(n, k)/(n-k+1)*Binomial(n+k-1, n-k): k in [0..n]]: n in [0..25]]; // Vincenzo Librandi, Sep 23 2015
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
