|
| |
|
|
A007317
|
|
Binomial transform of Catalan numbers.
(Formerly M1480)
|
|
48
|
|
|
|
1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, 223191, 974427, 4302645, 19181100, 86211885, 390248055, 1777495635, 8140539950, 37463689775, 173164232965, 803539474345, 3741930523740, 17481709707825, 81912506777200, 384847173838501, 1812610804416698
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Partial sums of A002212 (the restricted hexagonal polyominoes with n cells). Number of Schroeder paths (i.e. consisting of steps U=(1,1),D=(1,-1),H=(2,0) and never going below the x-axis) from (0,0) to (2n-2,0), with no peaks at even level. Example: a(3)=5 because among the six Schroeder paths from (0,0) to (4,0) only UUDD has a peak at an even level. - Emeric Deutsch, Dec 06 2003
Number of binary trees of weight n where leaves have positive integer weights. Non-commutative Non-associative version of partitions of n. - Michael Somos, May 23 2005
Appears also as the number of Euler trees with total weight n (associated with even switching class of matrices of order 2n). - David Garber (garber(AT)hait.ac.il), Sep 19 2005
Number of symmetric hex trees with 2n-1 edges; also number of symmetric hex trees with 2n-2 edges. A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read reference). A hex tree is symmetric if it is identical with its reflection in a bisector through the root. - Emeric Deutsch, Dec 19 2006
The Hankel transform of [1, 2, 5, 15, 51, 188, ...] is [1, 1, 1, 1, 1, ...], see A000012 ; the Hankel transform of [2, 5, 15, 51, 188, 731, ...] is [2, 5, 13, 34, 89, ...], see A001519 . - Philippe DELEHAM, Dec 19 2006
a(n) = number of 321-avoiding partitions of [n]. A partition is 321-avoiding if the permutation obtained from its canonical form (entries in each block listed in increasing order and blocks listed in increasing order of their first entries) is 321-avoiding. For example, the only partition of [5] that fails to be 321-avoiding is 15/24/3 because the entries 5,4,3 in the permutation 15243 form a 321 pattern. - David Callan, Jul 22 2008
The sequence 1,1,2,5,15,51,188,... has Hankel transform A001519. [Paul Barry, Jan 13 2009]
From Gary W. Adamson, May 17 2009: (Start)
Equals INVERT transform of A033321: (1, 1, 2, 6, 21, 79, 311,...).
Equals INVERTi transform of A002212: (1, 3, 10, 36, 137,...).
Convolved with A026378, (1, 4, 17, 75, 339,...) = A026376: (1, 6, 30, 144,...)
(End)
a(n) is the number of vertices of the composihedron CK(n). The composihedra are a sequence of convex polytopes used to define maps of certain homotopy H-spaces. They are cellular quotients of the multiplihedra and cellular covers of the cubes. - Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009
a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps at level 0 come in 2 colors and those at a higher level come in 3 colors. Example: a(4)=15 because we have 2^3 = 8 paths of shape UHD, 2 paths of shape HUD, 2 paths of shape UDH, and 3 paths of shape UHD; here U=(1,1), H=(1,0), and D=(1,-1). - Emeric Deutsch, May 02 2011
REVERT transform of (1, 2, -3, 5, -8, 13, -21, 34, ... ) where the entries are Fibonacci numbers, A000045. Equivalently, coefficients in the series reversion of x(1-x)/(1+x-x^2). This means that the substitution of the gf (1-x-(1-6x+5x^2)^(1/2))/(2(1-x)) for x in x(1-x)/(1+x-x^2) will simplify to x. [David Callan, Nov 11 2012]
|
|
|
REFERENCES
|
R. Bacher and D. Garber, Spindle-configurations of skew lines, submitted
J. Brunvoll et al., Studies of some chemically relevant polygonal systems: mono-q-polyhexes, ACH Models in Chem., 133 (3) (1996), 277-298, Eq 15.
S. J. Cyvin et al., Enumeration and classification of benzenoid systems. 32. Normal perifusenes with two internal vertices, J. Chem. Inform. Comput. Sci., 32 (1992), 532-540.
S. J. Cyvin et al., Graph-theoretical studies on fluoranthenoids and fluorenoids..., J. Molec. Struct. (Theochem), 285 (1993), 179-185.
S. J. Cyvin et al., Enumeration and classification of certain polygonal systems...: annelated catafusenes, J. Chem. Inform. Comput. Sci., 34 (1994), 1174-1180.
D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From N. J. A. Sloane, May 11 2012
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, Arxiv preprint arXiv:1109.3641, 2011
Francesc Fite, Kiran S. Kedlaya, Victor Rotger and Andrew V. Sutherland, Sato-Tate distributions and Galois endomorphism modules in genus 2, Arxiv preprint arXiv:1110.6638, 2011
N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
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; http://repository.wit.ie/1693/1/AoifeThesis.pdf
J. S. Kim, Bijections on two variations of noncrossing partitions, Discrete Math., 311 (2011), 1057-1063.
Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.
T. Mansour and M. Shattuck, Some enumerative results related to ascent sequences, Arxiv preprint arXiv:1207.3755, 2012. - From N. J. A. Sloane, Dec 22 2012
I. Pak, Partition identities and geometric bijections. Proc. Amer. Math. Soc. 132 (2004), 3457-3462.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Thitsa and W. S. Gray, On the Radius of Convergence of Interconnected Analytic Nonlinear Input-Output Systems, SIAM J. CONTROL OPTIM, Vol. 50, No. 5, pp. 2786-2813. - From N. J. A. Sloane, Dec 26 2012
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..200
David Callan, Pattern avoidance in "flattened" partitions .
S. Forcey, Quotients of the multiplihedron as categorified associahedra,Homotopy, Homology and Applications, vol. 10(2), 227-256, 2008. [From Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009]
U. Grude, Java ist eine Sprache: Rekursive Unterprogramme. See page 4.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 124
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
N. J. A. Sloane, Transforms
|
|
|
FORMULA
|
(n+2)*a(n+2) = (6n+4)*a(n+1) - 5n*a(n).
G.f. for sequence doubled: (1/(2*x))*(1+x-(1-x)^(-1)*(1-x^2)^(1/2)*(1-5*x^2)^(1/2)).
a(n) = hypergeom([1/2, -n], [2], -4), n=0, 1, 2...; Integral representation as n-th moment of a positive function on a finite interval of the positive half-axis: a(n)=int(x^n*sqrt((5-x)/(x-1))/(2*Pi), x=1..5), n=0, 1, 2... This representation is unique. - Karol A. Penson, Sep 24 2001
a(1)=1, a(n)=1+sum(i=1, n-1, a(i)*a(n-i)). - Benoit Cloitre, Mar 16 2004
a(n) = sum{k=0..n, (-1)^k*3^(n-k)*binomial(n, k)*binomial(k, floor(k/2))} [offset 0]. - Paul Barry, Jan 27 2005
G.f. A(x) satisfies 0=f(x, A(x)) where f(x, y)=x-(1-x)(y-y^2). - Michael Somos, May 23 2005
G.f. A(x) satisfies 0=f(x, A(x), A(A(x))) where f(x, y, z)=x(z-z^2)+(x-1)y^2 . - Michael Somos, May 23 2005
G.f.: (-1+x+(1-6*x+5*x^2)^(1/2))/(2*(-x+x^2)).
G.f. =z*c(z/(1-z))/(1-z) = 1/2 - (1/2)sqrt(1-4z/(1-z)), where c(z)=(1-sqrt(1-4z))/(2z) is the Catalan function (follows from Michael Somos' first comment). - Emeric Deutsch, Aug 12 2007
G.f.: 1/(1-2x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-.... (continued fraction). [Paul Barry, Apr 19 2009]
a(n) = Sum_{k, 0<=k<=n} A091965(n,k)*(-1)^k. [Philippe DELEHAM, Nov 28 2009]
E.g.f.: exp(3x)*(I_0(2x)-I_1(2x)), where I_k(x) is a modified Bessel function of the first kind. [Emanuele Munarini, Apr 15 2011]
If we prefix sequence with an additional term a(0)=1, g.f. is (3-3*x-sqrt(1-6*x+5*x^2))/(2*(1-x)). [See Kim, 2011] - N. J. A. Sloane, May 13 2011
From Gary W. Adamson, Jul 21 2011: (Start)
a(n) = upper left term in M^(n-1), M = an infinite square production matrix as follows:
2, 1, 0, 0, 0, 0,...
1, 2, 1, 0, 0, 0,...
1, 1, 2, 1, 0, 0,...
1, 1, 1, 2, 1, 0,...
1, 1, 1, 1, 2, 1,...
1, 1, 1, 1, 1, 2,...
... (end)
G.f. satisfies: A(x) = Sum_{n>=0} x^n * (1 - A(x)^(n+1))/(1 - A(x)); offset=0. [Paul D. Hanna, Nov 07 2011]
G.f.: 1/x - 1/x/Q(0), where Q(k)= 1 + (4*k+1)*x/((1-x)*(k+1) - x*(1-x)*(2*k+2)*(4*k+3)/(x*(8*k+6)+(2*k+3)*(1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
|
|
|
EXAMPLE
|
a(3)=5 since {3, (1+2), (1+(1+1)), (2+1), ((1+1)+1)} are the five weighted binary trees of weight 3.
|
|
|
MAPLE
|
G := (1-sqrt(1-4*z/(1-z)))*1/2: Gser := series(G, z = 0, 30): seq(coeff(Gser, z, n), n = 1 .. 26); - Emeric Deutsch, Aug 12 2007
|
|
|
MATHEMATICA
|
Rest@ CoefficientList[ InverseSeries[ Series[(y - y^2)/(1 + y - y^2), {y, 0, 26}], x], x] (* then A(x)=y(x); note that InverseSeries[Series[y-y^2, {y, 0, 24}], x] produces A000108(x) *) (* Len Smiley Apr 10 2000 *)
Range[0, 25]! CoefficientList[ Series[ Exp[ 3x] (BesselI[0, 2x] - BesselI[1, 2x]), {x, 0, 25}], x] (* Robert G. Wilson v, Apr 15 2011 *)
a[n_] := Sum[ Binomial[n, k]*CatalanNumber[k], {k, 0, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 07 2012 *)
|
|
|
PROG
|
(PARI) {a(n)=local(A); if(n<2, n>0, A=vector(n); for(j=1, n, A[j]=1+sum(k=1, j-1, A[k]*A[j-k])); A[n])} /* Michael Somos, May 23 2005 */
(PARI) {a(n)=if(n<1, 0, polcoeff(serreverse((x-x^2)/(1+x-x^2)+x*O(x^n)), n))} /* Michael Somos, May 23 2005 */
(PARI) /* Offset = 0: */ {a(n)=local(A=1+x); for(i=1, n, A=sum(m=0, n, x^m*sum(k=0, m, A^k)+x*O(x^n))); polcoeff(A, n)} \\ Paul D. Hanna
|
|
|
CROSSREFS
|
Cf. A000108, A055879. Row sums of absolute values of A091699.
First column of triangle A104259.
A033321, A026376, A026378 [From Gary W. Adamson, May 17 2009]
Cf. A121988, number of vertices of multiplihedron. [From Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009]
See A181878 for another version. - N. J. A. Sloane, Nov 12 2010
Cf. A059346.
Sequence in context: A007581 A124303 A073525 * A181768 A153197 A108307
Adjacent sequences: A007314 A007315 A007316 * A007318 A007319 A007320
|
|
|
KEYWORD
|
easy,nonn,nice,changed
|
|
|
AUTHOR
|
N. J. A. Sloane, Mira Bernstein (mira(AT)math.berkeley.edu)
|
|
|
STATUS
|
approved
|
| |
|
|
