|
| |
|
|
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; 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 (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), 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 (kolotoko(AT)wanadoo.fr), 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 (callan(AT)stat.wisc.edu), Jul 22 2008
The sequence 1,1,2,5,15,51,188,... has Hankel transform A001519. [From Paul Barry (pbarry(AT)wit.ie), Jan 13 2009]
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), May 17 2009: (Start)
Equals INVERT transform of A033321: (1, 1, 2, 6, 21, 79, 311,...).
and INVERTi transform of A002212: (1, 3, 10, 36, 137,...). Convolved with A026378, (1, 4, 17, 75, 339,...) = A026376: (1, 6, 30, 144,...)
(End)
Contribution from Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009: (Start)
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. (End)
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
|
|
|
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.
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.
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.
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).
|
|
|
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 (penson(AT)lptl.jussieu.fr), Sep 24 2001
a(1)=1, a(n)=1+sum(i=1, n-1, a(i)*a(n-i)). - Benoit Cloitre (benoit7848c(AT)orange.fr), 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 (pbarry(AT)wit.ie), 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 (deutsch(AT)duke.poly.edu), 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). [From Paul Barry (pbarry(AT)wit.ie), Apr 19 2009]
a(n)= Sum_{k, 0<=k<=n} A091965(n,k)*(-1)^k. [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), 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
Contribution 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. [From Paul D. Hanna, Nov 07 2011]
|
|
|
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 (deutsch(AT)duke.poly.edu), 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 *)
|
|
|
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 [from Paul D. Hanna]: */
{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)}
|
|
|
CROSSREFS
| Cf. A000108, A055879. Row sums of absolute values of A091699.
First column of triangle A104259.
A033321, A026376, A026378 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), 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
Sequence in context: A007581 A124303 A073525 * A181768 A153197 A108307
Adjacent sequences: A007314 A007315 A007316 * A007318 A007319 A007320
|
|
|
KEYWORD
| easy,nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Mira Bernstein (mira(AT)math.berkeley.edu)
|
| |
|
|
