|
%I M3002 N1217
%S 1,1,3,15,105,945,10395,135135,2027025,34459425,654729075,13749310575,
%T 316234143225,7905853580625,213458046676875,6190283353629375,
%U 191898783962510625,6332659870762850625,221643095476699771875,8200794532637891559375
%N Double factorial of odd numbers: (2*n-1)!! = 1*3*5*...*(2*n-1).
%C The solution to Schroeder's third problem.
%C Number of fixed-point-free involutions in symmetric group S_{2n} (cf. A000085).
%C a(n+2) is the number of full Steiner topologies on n points with n-2 Steiner points.
%C 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
%C Number of ways to choose n disjoint pairs of items from 2*n items. - Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002
%C Number of ways to choose n-1 disjoint pairs of items from 2*n-1 items (one item remains unpaired) - _Bartosz Zoltak_, Oct 16 2012
%C 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
%C 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)
%C 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
%C 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
%C 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_, Oct 10 2005.
%C 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_, Mar 12 2006
%C 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_, Aug 01 2006
%C a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is i for i<j. - _David Callan_, Sep 25 2006
%C 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_, Oct 26 2006
%C Number of perfect multi Skolem-type sequences of order n. - _Emeric Deutsch_, Nov 24 2006
%C 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_, Dec 29 2006
%C 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_, Mar 30 2007
%C 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_, Nov 13 2007
%C Comments from Ross Drewe (rd(AT)labyrinth.net.au), Mar 16 2008: (Start)
%C 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.
%C 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.
%C 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] }.
%C 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]}, ....}
%C 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)
%C A139541(n) = a(n) * a(2*n). - _Reinhard Zumkeller_, Apr 25 2008
%C a(n+1) = sum(j=0 to n) A074060(n,j) * 2^j. [_Tom Copeland_, Sep 01 2008]
%C Contribution from _Emeric Deutsch_, Jun 05 2009: (Start)
%C 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.
%C a(n)=Sum(k*A079267(n,k), k>=0).
%C (End)
%C Hankel transform is A137592. [_Paul Barry_, Sep 18 2009]
%C (1, 3, 15, 105,...) = INVERT transform of A000698 starting (1, 2, 10, 74,...). [_Gary W. Adamson_, Oct 21 2009]
%C a(n)=(-1)^(n+1)*H(2*n,0), where H(n,x) is the probabilists' Hermite polynomials. The generating function for the probabilists' Hermite polynomials is as follows: exp(x*t-t^2/2)=sum(H(i,x)*t^i/i!,i=0,1,...). [_Leonid Bedratyuk_, Oct 31 2009]
%C The Hankel transform of a(n+1) is A168467. [_Paul Barry_, Dec 04 2009]
%C a(n+1) is the number of ways to form n pairs from 2n people. [Andrew (andrewkirk_17(AT)yahoo.co.uk), Sep 07 2010]
%C Partial products of odd numbers. [_Juri-Stepan Gerasimov_, Oct 17 2010]
%C See A094638 for connections to differential operators. - _Tom Copeland_, Sep 20 2011
%C a(n) is the number of subsets of {1,...,n^2} that contain exactly k elements from {1,...,k^2} for k=1,...,n. For example, a(3)=15 since there are 15 subsets of {1,2,...,9} that satisfy the conditions, namely, {1,2,5}, {1,2,6}, {1,2,7}, {1,2,8}, {1,2,9}, {1,3,5}, {1,3,6}, {1,3,7}, {1,3,8}, {1,3,9}, {1,4,5}, {1,4,6}, {1,4,7}, {1,4,8}, and {1,4,9}. [_Dennis P. Walsh_, Dec 02 2011]
%C a(n) is the leading coefficient of the Bessel polynomial y_n(x) (cf. A001498). [_Leonid Bedratyuk_, Jun 01 2012]
%C For n>0: a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = min(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013
%D 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 D. Arques and J.-F. Beraud, Rooted maps on orientable surfaces..., Discrete Math., 215 (2000), 1-12.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228, #19.
%D Thierry Dana-Picard, Sequences of Definite Integrals, Factorials and Double Factorials, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.6.
%D Filippo Disanto and Thomas Wiehe, Some combinatorial problems on binary rooted trees occurring in population genetics, Arxiv preprint arXiv:1112.1295, 2011
%D 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.
%D 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
%D Hoel, Port and Stone, Introduction to Probability Theory, Section 7.3.
%D F. K. Hwang, D. S. Richards and P. Winter, The Steiner Tree Problem, North-Holland, 1992, see p. 14.
%D L. B. W. Jolley, "Summation of Series", Dover Publications, 1961, p. 48.
%D M. Kauers and S.-L. Ko, Problem 11545, Amer. Math. Monthly, 118 (2100), p. 84.
%D M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
%D B. E. Meserve, Double factorials, Amer. Math. Monthly, 55 (1948), 425-426.
%D T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
%D F. Murtagh, "Counting dendrograms: a survey", Discrete Applied Mathematics, 7 (1984), 191-199.
%D R. Ondrejka, Tables of double factorials, Math. Comp., 24 (1970), 231.
%D E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.6 and also p. 178.
%H T. D. Noe, <a href="/A001147/b001147.txt">Table of n, a(n) for n = 0..101</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.nrbook.com/abramowitz_and_stegun/">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].Jonathan Burns, <a href="http://shell.cas.usf.edu/~saito/DNAweb/SimpleAssemblyTable.txt">Assembly Graph Words - Single Transverse Component (Counts)</a>.
%H H. Bottomley, <a href="/A002694/a002694.gif">Illustration for A000108, A001147, A002694, A067310 and A067311</a>
%H Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, <a href="http://jtburns.myweb.usf.edu/assembly/papers/Graphs_and_DNA_Recomb_2011.pdf">Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination</a>, May 23, 2011.
%H David Callan, <a href="http://arxiv.org/abs/0906.1317">A combinatorial survey of identities for the double factorial</a>.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H Guo-Niu Han, <a href="http://www-irma.u-strasbg.fr/~guoniu/papers/p77puzzle.pdf">Enumeration of Standard Puzzles</a>
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=23">Encyclopedia of Combinatorial Structures 23</a>
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=106">Encyclopedia of Combinatorial Structures 106</a>
%H A. Khruzin, <a href="http://arXiv.org/abs/math.CO/0008209">Enumeration of chord diagrams</a>
%H W. Lang, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">On generalizations of Stirling number triangles</a>, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
%H Larrion, F.; Pizana, M. A.; and Villarroel-Flores, R.; The clique operator on matching and chessboard graphs. Discrete Math. 309 (2009), no. 1, 85-93.
%H G. Nordh, <a href="http://arXiv.org/abs/math.NT/0506155">Perfect Skolem sequences</a>
%H L. Pachter and B. Sturmfels, <a href="http://arXiv.org/abs/math.ST/0409132">The mathematics of phylogenomics</a>
%H Helmut Prodinger, <a href="http://www.combinatorics.org/Volume_3/volume3.html#R29">Descendants in heap ordered trees or a triumph of computer algebra </a>
%H S. Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/question/q541.htm">Question 541</a>, J. Ind. Math. Soc.
%H Andrew Vince and Miklos Bona, <a href="http://arxiv.org/abs/1204.3842">The Number of Ways to Assemble a Graph</a>, Arxiv preprint arXiv:1204.3842, 2012.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DoubleFactorial.html">Double Factorial</a>, <a href="http://mathworld.wolfram.com/NormalDistributionFunction.html">Normal Distribution Function</a>, <a href="http://mathworld.wolfram.com/Erf.html">Erf</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pfaffian">Pfaffian</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Hermite_polynomials">Hermite polynomials</a>
%H <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>
%H <a href="/index/Fa#factorial">Index entries for sequences related to factorial numbers</a>
%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%F E.g.f.: 1 / sqrt(1 - 2*x).
%F a(n) = a(n-1)*(2*n-1) = (2*n)!/(n!*2^n) = A010050(n)/A000165(n).
%F a(n) ~ sqrt(2) * 2^n * (n/e)^n.
%F Rational part of numerator of Gamma(n+1/2): a(n) * sqrt(Pi) / 2^n = Gamma(n+1/2). - Yuriy Brun, Ewa Dominowska (brun(AT)mit.edu), May 12 2001
%F With interpolated zeros, the sequence has e.g.f. exp(x^2/2). - _Paul Barry_, Jun 27 2003
%F The Ramanujan polynomial psi(n+1, n) has value a(n). - _Ralf Stephan_, Apr 16 2004
%F a(n) = Sum_{k=0..n} (-2)^(n-k)*A048994(n, k) .- _Philippe DELEHAM_, Oct 29 2005
%F 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_, Jun 20 2006
%F 1/3 + 2/15 + 3/105 +...= 1/2. [Jolley eq. 216]
%F sum{j=1..n} j/a(j+1) = (1-1/a(n+1))/2. [Jolley eq. 216]
%F 1/1 + 1/3 + 2/15 + 6/105 + 24/945 +...= Pi/2 - _Gary W. Adamson_, Dec 21 2006
%F a(n) = (1/sqrt(2*pi))*int(x^n*exp(-x/2)/sqrt(x),x,0,infty); - _Paul Barry_, Jan 28 2008
%F a(n) = A006882(2n-1). [_R. J. Mathar_, Jul 04 2009]
%F G.f.: 1/(1-x-2x^2/(1-5x-12x^2/(1-9x-30x^2/(1-13x-56x^2/(1- ... (continued fraction). [_Paul Barry_, Sep 18 2009]
%F 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)!). [_Leonid Bedratyuk_, Oct 31 2009]
%F a(n) = 2^n*gamma(n+1/2)/gamma(1/2). [_Jaume Oliver Lafont_, Nov 09 2009]
%F G.f.: 1/(1-x/(1-2x/(1-3x/(1-4x/(1-5x/(1- ...(continued fraction). [Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009]
%F The g.f. of a(n+1) is 1/(1-3x/(1-2x/(1-5x/(1-4x/(1-7x/(1-6x/(1-.... (continued fraction). [_Paul Barry_, Dec 04 2009]
%F a(n) = sum(i=1..n) C(n,i)*a(i-1)*a(n-i). [_Vladimir Shevelev_, Sep 30 2010]
%F E.g.f.: A(x)=1-sqrt(1-2*x) satisfies the differential equation A'(x)-A'(x)*A(x)-1=0. [_Vladimir Kruchinin_, Jan 17 2011]
%F a(n) = A123023(2*n + 1). - _Michael Somos_, Jul 24 2011
%F a(n) = (1/2)*Sum{i=1,...,n} C(n+1,i)*a(i-1)*a(n-i). See link above. [_Dennis Walsh_, Dec 02 2011]
%F a(n) = sum((-1)^k*binomial(2*n,n+k)*Stirling_1(n+k,k),k=0..n) [Kauers and Ko]
%F a(n) = A035342(n, 1), n >= 1 (first column of triangle).
%F a(n) = A001497(n, 0) = A001498(n, n), first column, resp. main diagonal, of Bessel triangle.
%F Contribution from _Gary W. Adamson_, Jul 19 2011: (Start)
%F a(n) = upper left term of M^n and sum of top row terms of M^(n-1), where M = a variant of the (1,2) Pascal triangle (Cf. A029635) as the following production matrix:
%F 1, 2, 0, 0, 0,...
%F 1, 3, 2, 0, 0,...
%F 1, 4, 5, 2, 0,...
%F 1, 5, 9, 7, 2,...
%F ... (end)
%F G.f.: A(x)=1+x/(W(0)-x); W(k)=1+x+x*2k-x*(2k+3)/W(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Nov 17 2011
%F a(n) = sum{i=1,...,n} C(n,i-1)*a(i-1)*a(n-i). [_Dennis Walsh_, Dec 02 2011]
%F a(n) = A009445(n) / A014481(n). [_Reinhard Zumkeller_, Dec 03 2011]
%F a(n) = (-1)^n*sum_{k=0..n} 2^(n-k)*s(n+1,k+1), where s(n,k) are the Stirling numbers of the first kind, A048994. [_Mircea Merca_, May 03 2012]
%F a(n) = (2*n)_4! = Gauss_factorial(2*n,4) = product_{1<=j<=2*n, GCD(j,4)=1} j. - _Peter Luschny_, Oct 01 2012
%F G.f.: (1 - 1/Q(0))/x where Q(k) = 1 - x*(2*k-1)/(1 - x*(2*k+2)/Q(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Mar 19 2013
%F G.f.: 1 + x/Q(0), where Q(k)= 1 + (2*k-1)*x - 2*x*(k+1)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 01 2013
%e a(3) = 1*3*5 = 15.
%e a(3) = 15 = left term in top row of M^3: (15, 46, 36, 8). a(4) = 105 = (15 + 46 + 36 + 8).
%p f := n->(2*n)!/(n!*2^n);
%p A001147 := proc(n) doublefactorial(2*n-1); end: # _R. J. Mathar_, Jul 04 2009
%p A001147 := n -> 2^n*pochhammer(1/2, n); # _Peter Luschny_, Aug 09 2009
%p 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); # Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 03 2009
%p series(hypergeom([1,1/2],[],2*x),x=0,20); # _Mark van Hoeij_, Apr 07 2013
%t Table[(2n - 1)!!, {n, 0, 19}] (* Robert G. Wilson v, Oct 12 2005 *)
%o (PARI) {a(n) = if( n<0, 0, (2*n)! / n! / 2^n)} /* _Michael Somos_, Nov 16 2002 */
%o (Pari) x='x+O('x^33); Vec(serlaplace((1-2*x)^(-1/2))) /* _Joerg Arndt_, Apr 24 2011 */
%o (MAGMA) A001147:=func< n | n eq 0 select 1 else &*[ k: k in [1..2*n-1 by 2] ] >; [ A001147(n): n in [0..20] ]; // _Klaus Brockhaus_, Jun 22 2011
%o (Haskell)
%o a001147 n = product [1,3..2*n-1] -- _Reinhard Zumkeller_, Dec 03 2011
%o (Sage) [rising_factorial(n+1,n)/2^n for n in (0..15)] # _Peter Luschny_, Jun 26 2012
%Y Cf. A000085, A006882, A000165 ((2n)!!), A001818, A009445, A039683, A102992, A001190 (no labels), A000680, A132101.
%Y 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).
%Y Constant terms of polynomials in A098503. First row of array A099020.
%Y Cf. A079267, A000698, A029635, A161198, A076795, A123023.
%Y Cf. A161124, A051125, A181983.
%K nonn,easy,nice,core,changed
%O 0,3
%A _N. J. A. Sloane_.
%E More terms from _Reinhard Zumkeller_, Apr 25 2008
%E Removed erroneous comments: 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_, Jun 02 2009
%E Maple program from Zerinvary Lajos aligned with offset. - _Johannes W. Meijer_, Aug 11 2009
|
