|
|
A166135
|
|
Number of possible paths to each node that lies along the edge of a cut 4-nomial tree, that is rooted one unit from the cut.
|
|
2
|
|
|
1, 1, 3, 7, 22, 65, 213, 693, 2352, 8034, 28014, 98505, 350548, 1256827, 4542395, 16517631, 60417708, 222087320, 820099720, 3040555978, 11314532376, 42243332130, 158196980682, 594075563613, 2236627194858, 8440468925400
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
This is the third member of an infinite series of infinite series, the first two being the Catalan and Motzkin integers. The Catalan numbers lie on the edge of cut 2-nomial trees, Motzkin integers on the edge of cut 3-nomial trees.
a(n) is the number of increasing unary-binary trees with associated permutation that avoids 213. For more information about increasing unary-binary trees with an associated permutation, see A245888. - Manda Riehl, Aug 07 2014
Number of positive walks with n steps {-2,-1,1,2} starting at the origin, ending at altitude 1, and staying strictly above the x-axis. - David Nguyen, Dec 16 2016
|
|
LINKS
|
Rick Jarosh, Illustrates the sequence in context. The above reference gives the first 16 terms of the first 128 sequences in the family, of which this sequence is the third, the first being the Catalan numbers, the second the Motzkin integers, the fourth A104632.
|
|
FORMULA
|
A(x) satisfies A(x)+A(x)^2 = A000108(x)-1, a(n) = (1/n)*Sum_{k=1..n} (-1)^(k+1) * C(2*n,n-k)*C(2*k-2,k-1). - Vladimir Kruchinin, May 12 2012
Conjecture: 2*n*(2*n+1)*a(n) + (17*n^2-53*n+24)*a(n-1) + 6*(-13*n^2+43*n-36)*a(n-2) - 108*(2*n-5)*(n-3)*a(n-3) = 0. - R. J. Mathar, Oct 08 2016
a(n) = (1/n)*Sum_{k=0..n} binomial(n,k)*binomial(n,2*n-3*k-1). - David Nguyen, Dec 31 2016
1 + x*A(x) = 1/C(-x*C(x)^2), where C(x) is the g.f. of A000108.
F(x) = x*(1+x*A(x)) = x/C(-x*C(x)^2) is a pseudo-involution, i.e., the series reversion of x*(1 + x*A(x)) is x*(1 - x*A(-x)).
The B-sequence of F(x) is A069271, i.e., F(x) = x + x*F(x)*A069271(x*F(x)). (End)
|
|
MAPLE
|
seq( add(binomial(n, k)*binomial(n, 2*n-3*k-1), k=0..n)/n, n=1..30); # G. C. Greubel, Dec 12 2019
|
|
MATHEMATICA
|
Rest[CoefficientList[Series[(Sqrt[(2-2Sqrt[1-4x]-3x)/x]-1)/2, {x, 0, 30}], x]] (* Benedict W. J. Irwin, Sep 24 2016 *)
|
|
PROG
|
(PARI) vector(30, n, sum(k=0, n, binomial(n, k)*binomial(n, 2*n-3*k-1))/n ) \\ G. C. Greubel, Dec 12 2019
(Magma) [(&+[Binomial(n, k)*Binomial(n, 2*n-3*k-1): k in [0..n]])/n : n in [1..30]]; // G. C. Greubel, Dec 12 2019
(Sage) [sum(binomial(n, k)*binomial(n, 2*n-3*k-1) for k in (0..n))/n for n in (1..30)] # G. C. Greubel, Dec 12 2019
|
|
CROSSREFS
|
A055113 is the third sequence from the top of the graph illustrated above.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Rick Jarosh (rick(AT)jarosh.net), Oct 08 2009
|
|
STATUS
|
approved
|
|
|
|