0,3

The solution to Schroeder's third problem.

a(n+2) is the number of full Steiner topologies on n points with n-2 Steiner points.

a(n) is also the number of perfect matchings in the complete graph K(2n) - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001

Number of ways to choose n disjoint pairs of items from 2*n items. - Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002

Also rational part of numerator of Gamma(n+1/2). Multiplying this sequence by sqrt(Pi) and dividing by 2^n gives the value of Gamma(n+1/2). - Yuriy Brun, Ewa Dominowska (brun(AT)mit.edu), May 12 2001

For n >= 1 a(n) is the number of permutations in the symmetric group S_(2n) whose cycle decomposition is a product of n disjoint transpositions. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 21 2001

Number of fixed-point-free involutions in symmetric group S_{2n}.

a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters (awalters3(AT)yahoo.com), Jan 17 2004. For example, a(3)=15 because the product of the four variables w, x, y and z can be constructed in exactly 15 ways, assuming commutativity but not associativity: 1. w(x(yz)) 2. w(y(xz)) 3. w(z(xy)) 4. x(w(yz)) 5. x(y(wz)) 6. x(z(wy)) 7. y(w(xz)) 8. y(x(wz)) 9. y(z(wx)) 10. z(w(xy)) 11. z(x(wy)) 12. z(y(wx)) 13. (wx)(yz) 14. (wy)(xz) 15. (wz)(xy)

a(n) = E(X^(2n)), where X is a standard normal random variable (i.e. X is normal with mean = 0, variance = 1). So for instance a(3) = E(X^6) = 15, etc. See Abramowitz and Stegun or Hoel, Port and Stone. - Jerome Coleman, Apr 06 2004

Second Eulerian transform of 1,1,1,1,1,1... The second Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum[E(n,k)s(k), k=0...n], where E(n,k) is a second-order Eulerian number [A008517]. - Ross La Haye (rlahaye(AT)new.rr.com), Feb 13 2005

Integral representation as n-th moment of a positive function on the positive axis, in Maple notation: a(n)=int(x^n*exp(-x/2)/sqrt(2*Pi*x), x=0..infinity), n=0,1... . - Karol A. Penson (penson(AT)lptl.jussieu.fr), Oct 10 2005.

Let PI be the set of all partitions of {1, 2, ..., 2n} into pairs without regard to order. There are (2n-1)!! such partitions. An element alpha in PI can be written as alpha = {(i_1, j_1), (i_2, j_2), ..., (i_n, j_n)} with i_k < j_k. Let pi be the corresponding permutation which maps 1 to i_1, 2 to j_1, 3 to i_2, 4 to j_2, ..., 2n to j_n. Define sgn(alpha) to be the signature of pi, which depends only on the partition alpha and not on the particular choice of pi. Let A = {a_ij} be a 2n x 2n skew-symmetric matrix. Given a partition alpha as above define A_alpha = sgn(alpha) a_(i_1,j_1)a_(i_2,j_2)...a_(i_n,j_n). We can then define the Pfaffian of A to be Pf(A) = SUM[alpha in PI]A_alpha. The Pfaffian of an n x n skew-symmetric matrix for n odd is defined to be zero. - Jonathan Vos Post (jvospost3(AT)gmail.com), Mar 12 2006

a(n) is the number of binary total partitions (each non-singleton block must be partitioned into exactly two blocks) or, equivalently, the number of unordered full binary trees with labeled leaves (Stanley, ex 5.2.6) - Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu), Aug 01 2006

a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is i for i<j. - David Callan (callan(AT)stat.wisc.edu), Sep 25 2006

a(n) is the number of increasing ordered rooted trees on n+1 vertices where "increasing" means the vertices are labeled 0,1,2,...,n so that each path from the root has increasing labels. Increasing unordered rooted trees are counted by the factorial numbers A000142. - David Callan (callan(AT)stat.wisc.edu), Oct 26 2006

Number of perfect multi Skolem-type sequences of order n. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 24 2006

a(n) = total weight of all Dyck n-paths (A000108) when each path is weighted with the product of the heights of the terminal points of its upsteps. For example with n=3, the 5 Dyck 3-paths UUUDDD, UUDUDD, UUDDUD, UDUUDD, UDUDUD have weights 1*2*3=6, 1*2*2=4, 1*2*1=2, 1*1*2=2, 1*1*1=1 respectively and 6+4+2+2+1=15. Counting weights by height of last upstep yields A102625. - David Callan (callan(AT)stat.wisc.edu), Dec 29 2006

a(n) is the number of increasing ternary trees on n vertices. Increasing binary trees are counted by ordinary factorials (A000142) and increasing quaternary trees by triple factorials (A007559). - David Callan (callan(AT)stat.wisc.edu), Mar 30 2007

This sequence is essentially self-reciprocal under the list partition transform and associated operations in A133314. More precisely, A001147 and -A001147 with a leading 1 attached are reciprocal. Therefore their e.g.f.'s are reciprocal. See A132382 for an extension of this result. - Tom Copeland (tcjpn(AT)msn.com), Nov 13 2007

Comments from Ross Drewe (rd(AT)labyrinth.net.au), Mar 16 2008: (Start) This is also the number of ways of arranging the elements of n distinct pairs, assuming the order of elements is significant but the pairs are not distinguishable, i.e. arrangements which are the same after permutations of the labels are equivalent.

If this sequence and A000680 are denoted by a(n) and b(n) respectively, then a(n) = b(n)/n! where n! = the number of ways of permuting the pair labels.

For example, there are 90 ways of arranging the elements of 3 pairs [1 1], [2 2], [3 3] when the pairs are distinguishable: A = { [112233], [112323], .... [332211] }.

By applying the 6 relabeling permutations to A, we can partition A into 90/6 = 15 subsets: B = { {[112233], [113322], [221133], [223311], [331122], [332211]}, {[112323], [113232], [221313], [223131], [331212], [332121]}, ....}

Each subset or equivalence class in B represents a unique pattern of pair relationships. For example, subset B1 above represents {3 disjoint pairs} and subset B2 represents {1 disjoint pair + 2 interleaved pairs}, with the order being significant (contrast A132101). (End)

A139541(n) = a(n) * a(2*n). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Apr 25 2008

a(n+1) = sum(j=0 to n) A074060(n,j) * 2^j [From Tom Copeland (tcjpn(AT)msn.com), Sep 01 2008]

Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 05 2009: (Start)

a(n)=number of adjacent transpositions in all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=3 because in 2143=(12)(34), 3412=(13)(24), and 4321=(14)(23) we have 2 + 0 + 1 adjacent transpositions.

a(n)=Sum(k*A079267(n,k), k>=0).

(End)

Hankel transform is A137592. [From Paul Barry (pbarry(AT)wit.ie), Sep 18 2009]

(1, 3, 15, 105,...) = INVERT transform of A000698 starting (1, 2, 10, 74,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 21 2009]

a(n)=(-1)^(n+1)*H(2*n,0), where H(n,x) is the probabilists' Hermite polynomials. The generating function for the the probabilists' Hermite polynomials is as follows: exp(x*t-t^2/2)=sum(H(i,x)*t^i/i!,i=0,1,...) [From Leonid Bedratyuk (leonid.uk(AT)gmail.com), Oct 31 2009]

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, (26.2.28).

D. Arques and J.-F. Beraud, Rooted maps on orientable surfaces..., Discrete Math., 215 (2000), 1-12.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228, #19.

Thierry Dana-Picard, Sequences of Definite Integrals, Factorials and Double Factorials, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.6.

Ghislain R. Franssens, On a Number Pyramid Related to the Binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.

Hoel, Port and Stone, Introduction to Probability Theory, Section 7.3.

F. K. Hwang, D. S. Richards and P. Winter, The Steiner Tree Problem, North-Holland, 1992, see p. 14.

L. B. W. Jolley, "Summation of Series", Dover Publications, 1961, p. 48

M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.

B. E. Meserve, Double factorials, Amer. Math. Monthly, 55 (1948), 425-426.

T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.

F. Murtagh, "Counting dendrograms: a survey", Discrete Applied Mathematics, 7 (1984), 191-199.

R. Ondrejka, Tables of double factorials, Math. Comp., 24 (1970), 231.

E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.6 and also p. 178.

T. D. Noe, Table of n, a(n) for n=0..101

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

H. Bottomley, Illustration for A000108, A001147, A002694, A067310 and A067311

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 23

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 106

A. Khruzin, Enumeration of chord diagrams

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

G. Nordh, Perfect Skolem sequences

L. Pachter and B. Sturmfels, The mathematics of phylogenomics

Helmut Prodinger, Descendants in heap ordered trees or a triumph of computer algebra

S. Ramanujan, Question 541, J. Ind. Math. Soc.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Erf

Wikipedia, Pfaffian

Index entries for related partition-counting sequences

Index entries for sequences related to factorial numbers

Index entries for sequences related to parenthesizing

Hermite_polynomials [From Leonid Bedratyuk (leonid.uk(AT)gmail.com), Oct 31 2009]

E.g.f.: 1/sqrt(1-2x). a(n) = a(n-1)*(2n-1) = (2n)!/(n!*2^n) = A010050(n)/A000165(n). a(n) ~ sqrt(2) * 2^n * (n/e)^n.

With interpolated zeros, the sequence has e.g.f. exp(x^2/2). - Paul Barry (pbarry(AT)wit.ie), Jun 27 2003

The Ramanujan polynomial psi(n+1, n) has value a(n). - R. Stephan, Apr 16 2004

a(n) = Sum_{k=0..n} (-2)^(n-k)*A048994(n, k) .- Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 29 2005

log(1+x+3*x^2+15*x^3+105*x^4+945*x^5+10395*x^6+...)=x+5/2*x^2+37/3*x^3+353/4*x^4+4081/5*x^5+55205/6*x^6+..., where [1, 5, 37, 353, 4081, 55205,...] = A004208 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jun 20 2006

1/3 + 2/15 + 3/105 +...= 1/2 1/1 + 1/3 + 2/15 + 6/105 + 24/945 +...= Pi/2 - Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 21 2006

a(n)=(1/sqrt(2*pi))*int(x^n*exp(-x/2)/sqrt(x),x,0,infty); - Paul Barry (pbarry(AT)wit.ie), Jan 28 2008

a(n)=A006882(2n-1). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jul 04 2009]

G.f.: 1/(1-x-2x^2/(1-5x-12x^2/(1-9x-30x^2/(1-13x-56x^2/(1- ... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), Sep 18 2009]

a(n)=(-1)^n*subs({ln(e)=1,x=0},coeff(simplify(series(e^(x*t-t^2/2),t,2*n+1)),t^(2*n))*(2*n)!) [From Leonid Bedratyuk (leonid.uk(AT)gmail.com), Oct 31 2009]

a(3)=1*3*5=15.

f := n->(2*n)!/(n!*2^n);

A001147 := proc(n) doublefactorial(2*n-1); end: [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jul 04 2009]

A001147 := n -> 2^n*pochhammer(1/2, n); (From Peter Luschny, Aug 09 2009)

with(finance):seq(mul(cashflows([k, k, 1], 0), k=0..n-1), n=0..19); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 22 2008]

restart: G(x):=(1-2*x)^(-1/2): f[0]:=G(x): for n from 1 to 29 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n], n=0..19); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 03 2009]

Table[(2n - 1)!!, {n, 0, 19}] (from Robert G. Wilson v (rgwv(at)rgwv.com), Oct 12 2005)

(PARI) a(n)=if(n<0, 0, (2*n)!/n!/2^n)

Cf. A006882, A076795, A000165 ((2n)!!), A001818, A009445, A039683. a(n)= A035342(n, 1), n >= 1 (first column of triangle).

Cf. A086677; A055142 (for this sequence, |a(n+1)| + 1 is the number of distinct products which can be formed using commutative, nonassociative multiplication and a nonempty subset of n given variables).

Constant terms of polynomials in A098503. First row of array A099020.

Cf. A102992, A001190 (no labels).

a(n)=A001497(n, 0) = A001498(n, n), first column, resp. main diagonal, of Bessel triangle.

Cf. A000680, A132101.

A079267 [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 05 2009]

Cf. A000698 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 21 2009]

Adjacent sequences: A001144 A001145 A001146 this_sequence A001148 A001149 A001150

Sequence in context: A001801 A067546 A015682 this_sequence A000268 A118750 A070826

nonn,easy,nice,core,new

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Apr 25 2008

Removed erroneous entries; neither the number of n x n binary matrices A such that A^2 = 0 nor the number of simple directed graphs on n vertices with no directed path of length two are counted by this sequence (for n = 3, both are 13) Dan Drake (ddrake(AT)member.ams.org), Jun 02 2009

Maple program Zerinvary Lajos aligned with offset Johannes W. Meijer (meijgia(AT)hotmail.com), Aug 11 2009