|
| |
|
|
A001147
|
|
Double factorial of odd numbers: (2*n-1)!! = 1*3*5*...*(2*n-1).
(Formerly M3002 N1217)
|
|
322
|
|
|
|
1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, 654729075, 13749310575, 316234143225, 7905853580625, 213458046676875, 6190283353629375, 191898783962510625, 6332659870762850625, 221643095476699771875, 8200794532637891559375
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
The solution to Schroeder's third problem.
Number of fixed-point-free involutions in symmetric group S_{2n} (cf. A000085).
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
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
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
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, 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, 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, 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, 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, Oct 26 2006
Number of perfect multi Skolem-type sequences of order n. - Emeric Deutsch, 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, 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, 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, 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, Apr 25 2008
a(n+1) = sum(j=0 to n) A074060(n,j) * 2^j. [Tom Copeland, Sep 01 2008]
Contribution from Emeric Deutsch, 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. [Paul Barry, Sep 18 2009]
(1, 3, 15, 105,...) = INVERT transform of A000698 starting (1, 2, 10, 74,...). [Gary W. Adamson, 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 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]
The Hankel transform of a(n+1) is A168467. [Paul Barry, Dec 04 2009]
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]
Partial products of odd numbers. [Juri-Stepan Gerasimov, Oct 17 2010]
See A094638 for connections to differential operators. - Tom Copeland, Sep 20 2011
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]
a(n) is the leading coefficient of the Bessel polynomial y_n(x) (cf. A001498). [Leonid Bedratyuk, Jun 01 2012]
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
|
|
|
REFERENCES
|
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.
Filippo Disanto and Thomas Wiehe, Some combinatorial problems on binary rooted trees occurring in population genetics, Arxiv preprint arXiv:1112.1295, 2011
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.
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
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. Kauers and S.-L. Ko, Problem 11545, Amer. Math. Monthly, 118 (2100), p. 84.
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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.6 and also p. 178.
|
|
|
LINKS
|
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].Jonathan Burns, Assembly Graph Words - Single Transverse Component (Counts).
H. Bottomley, Illustration for A000108, A001147, A002694, A067310 and A067311
Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination, May 23, 2011.
David Callan, A combinatorial survey of identities for the double factorial.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Guo-Niu Han, Enumeration of Standard Puzzles
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.
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.
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.
Andrew Vince and Miklos Bona, The Number of Ways to Assemble a Graph, Arxiv preprint arXiv:1204.3842, 2012.
Eric Weisstein's World of Mathematics, Double Factorial, Normal Distribution Function, Erf
Wikipedia, Pfaffian
Wikipedia, Hermite polynomials
Index to divisibility sequences
Index entries for related partition-counting sequences
Index entries for sequences related to factorial numbers
Index entries for sequences related to parenthesizing
|
|
|
FORMULA
|
E.g.f.: 1 / sqrt(1 - 2*x).
a(n) = a(n-1)*(2*n-1) = (2*n)!/(n!*2^n) = A010050(n)/A000165(n).
a(n) ~ sqrt(2) * 2^n * (n/e)^n.
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
With interpolated zeros, the sequence has e.g.f. exp(x^2/2). - Paul Barry, Jun 27 2003
The Ramanujan polynomial psi(n+1, n) has value a(n). - Ralf Stephan, Apr 16 2004
a(n) = Sum_{k=0..n} (-2)^(n-k)*A048994(n, k) .- Philippe DELEHAM, 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, Jun 20 2006
1/3 + 2/15 + 3/105 +...= 1/2. [Jolley eq. 216]
sum{j=1..n} j/a(j+1) = (1-1/a(n+1))/2. [Jolley eq. 216]
1/1 + 1/3 + 2/15 + 6/105 + 24/945 +...= Pi/2 - Gary W. Adamson, Dec 21 2006
a(n) = (1/sqrt(2*pi))*int(x^n*exp(-x/2)/sqrt(x),x,0,infty); - Paul Barry, Jan 28 2008
a(n) = A006882(2n-1). [R. J. Mathar, 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). [Paul Barry, 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)!). [Leonid Bedratyuk, Oct 31 2009]
a(n) = 2^n*gamma(n+1/2)/gamma(1/2). [Jaume Oliver Lafont, Nov 09 2009]
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]
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]
a(n) = sum(i=1..n) C(n,i)*a(i-1)*a(n-i). [Vladimir Shevelev, Sep 30 2010]
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]
a(n) = A123023(2*n + 1). - Michael Somos, Jul 24 2011
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]
a(n) = sum((-1)^k*binomial(2*n,n+k)*Stirling_1(n+k,k),k=0..n) [Kauers and Ko]
a(n) = A035342(n, 1), n >= 1 (first column of triangle).
a(n) = A001497(n, 0) = A001498(n, n), first column, resp. main diagonal, of Bessel triangle.
Contribution from Gary W. Adamson, Jul 19 2011: (Start)
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:
1, 2, 0, 0, 0,...
1, 3, 2, 0, 0,...
1, 4, 5, 2, 0,...
1, 5, 9, 7, 2,...
... (end)
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
a(n) = sum{i=1,...,n} C(n,i-1)*a(i-1)*a(n-i). [_Dennis Walsh_, Dec 02 2011]
a(n) = A009445(n) / A014481(n). [Reinhard Zumkeller, Dec 03 2011]
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]
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
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
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
|
|
|
EXAMPLE
|
a(3) = 1*3*5 = 15.
a(3) = 15 = left term in top row of M^3: (15, 46, 36, 8). a(4) = 105 = (15 + 46 + 36 + 8).
|
|
|
MAPLE
|
f := n->(2*n)!/(n!*2^n);
A001147 := proc(n) doublefactorial(2*n-1); end: # R. J. Mathar, Jul 04 2009
A001147 := n -> 2^n*pochhammer(1/2, n); # Peter Luschny, Aug 09 2009
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
series(hypergeom([1, 1/2], [], 2*x), x=0, 20); # Mark van Hoeij, Apr 07 2013
|
|
|
MATHEMATICA
|
Table[(2n - 1)!!, {n, 0, 19}] (* Robert G. Wilson v, Oct 12 2005 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, (2*n)! / n! / 2^n)} /* Michael Somos, Nov 16 2002 */
(Pari) x='x+O('x^33); Vec(serlaplace((1-2*x)^(-1/2))) /* Joerg Arndt, Apr 24 2011 */
(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
(Haskell)
a001147 n = product [1, 3..2*n-1] -- Reinhard Zumkeller, Dec 03 2011
(Sage) [rising_factorial(n+1, n)/2^n for n in (0..15)] # Peter Luschny, Jun 26 2012
|
|
|
CROSSREFS
|
Cf. A000085, A006882, A000165 ((2n)!!), A001818, A009445, A039683, A102992, A001190 (no labels), A000680, A132101.
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. A079267, A000698, A029635, A161198, A076795, A123023.
Cf. A161124, A051125, A181983.
Sequence in context: A067546 A015682 A189919 * A000268 A207818 A118750
Adjacent sequences: A001144 A001145 A001146 * A001148 A001149 A001150
|
|
|
KEYWORD
|
nonn,easy,nice,core,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms from Reinhard Zumkeller, Apr 25 2008
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
Maple program from Zerinvary Lajos aligned with offset. - Johannes W. Meijer, Aug 11 2009
|
|
|
STATUS
|
approved
|
| |
|
|
