The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000698 A problem of configurations: a(0) = 1; for n>0, a(n) = (2n-1)!! - Sum_{k=1..n-1} (2k-1)!! a(n-k). Also the number of shellings of an n-cube, divided by 2^n n!. (Formerly M1974 N0783) 57
 1, 1, 2, 10, 74, 706, 8162, 110410, 1708394, 29752066, 576037442, 12277827850, 285764591114, 7213364729026, 196316804255522, 5731249477826890, 178676789473121834, 5925085744543837186, 208256802758892355202, 7734158085942678174730 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS Also number of nonisomorphic unlabeled connected Feynman diagrams of order 2n-2 for the electron propagator of quantum electrodynamics (QED), including vanishing diagrams. [Corrected by Charles R Greathouse IV, Jan 24 2014][Clarified by Robert Coquereaux, Sep 14 2014] a(n+1) is the moment of order 2*n for the probability density function rho(x) = (1/sqrt(2*Pi))*exp(x^2/2)/[(u(x))^2+Pi/2], with u(x) = Integral_{t=0..x} exp(t*t/2) dt, on the real interval -infinity..infinity. - Groux Roland, Jan 13 2009 Starting (1, 2, 10, 74, ...) = INVERTi transform of A001147: (1, 3, 15, 105, ...). - Gary W. Adamson, Oct 21 2009 The Cvitanovic et al. paper relates this sequence to A005411 and A005413. - Robert Munafo, Jan 24 2010 Hankel transform of a(n+1) is A168467. - Paul Barry, Nov 26 2009 a(n) = number of labeled Dyck (n-1)-paths (A000108) in which each vertex that terminates an upstep is labeled with an integer i in [0,h], where h is the height of the vertex . For example UDUD contributes 4 labeled paths--0D0D, 0D1D, 1D0D, 1D1D where upsteps are replaced by their labels--and UUDD contributes 6 labeled paths to a(3)=10. The Deléham (Mar 24 2007) formula below counts these labeled paths by number of "0" labels. - David Callan, Aug 23 2011 a(n) is the number of indecomposable perfect matchings on [2n]. A perfect matching on [2n] is decomposable if a nonempty subset of the edges forms a perfect matching on [2k] for some k0 sum over all Dyck paths of semilength n-1 of products over all peaks p of (x_p+y_p)/y_p, where x_p and y_p are the coordinates of peak p. - Alois P. Heinz, May 22 2015 Also, counts certain isomorphism classes of closed normal linear lambda terms. [N. Zeilberger, 2015]. - N. J. A. Sloane, Sep 18 2016 The September 2018 talk by Noam Zeilberger (see link to video) connects three topics (planar maps, Tamari lattices, lambda calculus) and eight sequences: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. - N. J. A. Sloane, Sep 17 2018 REFERENCES Dubois C., Giorgetti A., Genestier R. (2016) Tests and Proofs for Enumerative Combinatorics. In: Aichernig B., Furia C. (eds) Tests and Proofs. TAP 2016. Lecture Notes in Computer Science, vol 9762. Springer. R. W. Robinson, Counting irreducible Feynman diagrams exactly and asymptotically, Abstracts Amer. Math. Soc., 2002, #975-05-270. 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). LINKS Vincenzo Librandi, Table of n, a(n) for n = 0..200 D. Arques and J.-F. Beraud, Rooted maps on orientable surfaces, Riccati's equation and continued fractions, Discrete Math., 215 (2000), 1-12. F. Battaglia, T. F. George, A Pascal type triangle for the number of topologically distinct many-electron Feynman diagrams, J. Math. Chem. 2 (1988) 241-247. S. Birdsong and G. Hetyei, A Gray Code for the Shelling Types of the Boundary of a Hypercube, arXiv preprint arXiv:1111.4710 [math.CO], 2011. S. Birdsong and G. Hetyei, A Gray Code for the Shelling Types of the Boundary of a Hypercube, Discrete Math. 313 (2013), no. 3, 258-268. MR2995390. Jonathan Burns, Assembly Graph Words - Single Transverse Component (Counts) Jonathan Burns and Tilahun Muche, Counting Irreducible Double Occurrence Words, arXiv preprint arXiv:1105.2926 [math.CO], 2011, Lemma 3.2. Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination, May 23, 2011. J. Courtiel, K. Yeats, N. Zeilberger, Connected chord diagrams and bridgeless maps, arXiv:1661.04611, Proposition 13. P. Cvitanovic, B. Lautrup and R. B. Pearson, The number and weights of Feynman diagrams, Phys. Rev. D18, (1978), 1939-1949, (eq 3.34 and fig 2b). M. A. Deryagina and A. D. Mednykh, On the enumeration of circular maps with given number of edges, Siberian Mathematical Journal, 54, No. 6, 2013, 624-639. S. Dulucq, Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy) Trinh Khanh Duy and Tomoyuki Shirai, The mean spectral measures of random Jacobi matrices related to Gaussian beta ensembles, arXiv:1504.06904 [math.SP], 2015. G. Edgar, Transseries for beginners,  arXiv:0801.4877v5 [math.RA], 2008-2009. 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. Ali Assem Mahmoud, On the Asymptotics of Connected Chord Diagrams, University of Waterloo (Ontario, Canada 2019). Ali Assem Mahmoud and Karen Yeats, Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions, arXiv:2010.06550 [math.CO], 2020. R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, arXiv:1103.4936 [math.CO], 2011. R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 292. R. J. Mathar, Table of Feynman Diagrams of the Interacting Fermion Green's Function, Int. J. Quant. Chem. 107 (2007) 1975. Also on arXiv, arXiv:physics/0512022 [physics.atom-ph], 2015-2016. R. J. Mathar, Feynman diagrams of the QED vacuum polarization, vixra:1901.0148 (2019), Section VII. L. G. Molinari, Hedin's equations and enumeration of Feynman diagrams, Phys. Rev. B, 71 (2005), 113102. A. Prunotto, W. M. Alberico, P. Czerski, Feynman diagrams and rooted maps, Open Phys. 16 (2018) 149-167. J. Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math., 4 (1952), 2-25. J. Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math., 4 (1952), 2-25. [Annotated, corrected, scanned copy] Wikipedia, Feynman diagram Noam Zeilberger, Counting isomorphism classes of beta-normal linear lambda terms, arXiv:1509.07596 [cs.LO], 2015. Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018. Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv preprint 1803.10030, March 2018 (A revised version of a 2017 conference paper) Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Rutgers Experimental Math Seminar, Sep 13 2018. Part 2 is vimeo.com/289910554. P. Zinn-Justin and J.-B. Zuber, Matrix integrals and the generation and counting of virtual tangles and links, arXiv:math-ph/0303049, 2003. FORMULA G.f.: 2 - 1/(1 + Sum_{n>=1} (2*n-1)!! * x^n ). a(n+1) = Sum_{k=0..n} A089949(n, k)*2^k. - Philippe Deléham, Aug 15 2005 a(n+1) = Sum_{k=0..n} A053979(n,k). - Philippe Deléham, Mar 24 2007 From Paul Barry, Nov 26 2009: (Start) G.f.: 1+x/(1-2x/(1-3x/(1-4x/(1-5x/(1-6x/(1-... (continued fraction). G.f.: 1+x/(1-2x-6x^2/(1-7x-20x^2/(1-11x-42x^2/(1-15x-72x^2/(1-19x-110x^2/(1-... (continued fraction). (End) G.f.: 1 + x * B(x) * C(x) where B(x) is the g.f. for A001147 and C(x) is the g.f. for A005416. - Michael Somos, Feb 08 2011 G.f.: 1+x/W(0); where W(k)=1+x+x*2k-x*(2k+3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011 Recurrence relation: a(n+1) = (2*n-1)*a(n) + Sum_{k = 1..n} a(k)*a(n+1-k) for n >= 0 and a(1) = 1. The o.g.f. B(x) = Sum_{n>=1} a(n)*x^(2*n-1) = x + 2*x^3 + 10*x^5 + 74*x^7 + ... satisfies the Riccati differential equation y'(x) = -1/x^2 + 1/x^3*y(x) - 1/x^2*y(x)^2 with initial condition y(0) = 0 (Cf. A005412). The solution is B(x) = 1/z(x) + 1/x , where z(x) = - Sum{n>=0} A001147(n) * x^(2*n+1) = -(x + x^3 + 3*x^5 + 15*x^7 +...). The function b(x) = - B(1/x) satisfies b'(x) = -1 - (x + b(x))*b(x). Hence the differential operator (D^2 + x*D + 1), where D = d/dx, factorizes as (D - a(x))*(D - b(x)), where a(x) = -(x + b(x)), as conjectured by [Edgar, Problem 4.32]. For a refinement of this sequence see A053979. - Peter Bala, Dec 22 2011 From Sergei N. Gladkovskii, Aug 19 2012, Oct 24 2012, Mar 19 2013, May 20 2013, May 29 2013, Aug 04 2013, Aug 05 2013: (Start) Continued Fractions: G.f.: 2-G(0) where G(k)= 1 -(k+1)*x/G(k+1). G.f.: 2 - U(0) where U(k)= 1 - (2*k+1)*x/(1 - (2*k+2)*x/U(k+1)). G.f.: 2 - U(0) where U(k)= 1 - (4*k+1)*x - (2*k+1)*(2*k+2)*x^2/U(k+1)). G.f.: 1/Q(0) where Q(k) = 1 - x*(2*k+2)/(1 - x*(2*k+3)/Q(k+1)). G.f.: 1 + x/Q(0) where Q(k)= 1 - x*(k+2)/Q(k+1)). G.f.: 2 - G(0)/2 where G(k)= 1 + 1/(1 - 2*x*(2*k+1)/(2*x*(2*k+1) - 1 + 2*x*(2*k+2)/ G(k+1))). G.f.: 1 + x*G(0) where G(k)= 1 - x*(k+2)/(x*(k+2) - 1/G(k+1)). G.f.: 2 - 1/B(x) where B(x) is the g.f. of A001147. G.f.: 1 + x/(1-2*x*B(x)) where B(x) is the g.f. of A167872. (End) a(n) ~ 2^(n+1/2) * n^n / exp(n). - Vaclav Kotesovec, Mar 10 2014 G.f.: 1/x + (sqrt(2/Pi) * exp(1/(2*x)) * sqrt[-1/x])/Erfc(sqrt(-1/x)/sqrt(2)) where Erfc(z) = 1 - Erf(z) is the complementary error function, and Erf(z) is the integral of the Gaussian distribution. This generating function is obtained from the generating functional of (4-dimensional) QED, evaluated in dimension 0 for the 2-point function, without the modification implementing Furry theorem. - Robert Coquereaux, Sep 14 2014 From Peter Bala, May 23 2017: (Start) G.f. A(x) = 1 + x/(1 + x - 3*x/(1 + 3*x - 5*x/(1 + 5*x - 7*x/(1 + 7*x - ... )))). A(x) = 1 + x/(1 + x - 3*x/(1 - 2*x/(1 - 5*x/(1 - 4*x/(1 - 7*x/(1 - 6*x/(1 - ... ))))))). (End) EXAMPLE G.f. = 1 + x + 2*x^2 + 10*x^3 + 74*x^4 + 706*x^5 + 8162*x^6 + 110410*x^7 + ... MAPLE A006882 := proc(n) option remember; if n <= 1 then 1 else n*procname(n-2); fi; end; A000698:=proc(n) option remember; global df; local k; if n=0 then RETURN(1); fi; A006882(2*n-1) - add(A006882(2*k-1)*A000698(n-k), k=1..n-1); end; A000698 := proc(n::integer) local resul, fac, pows, c, c1, p, i ; if n = 0 then RETURN(1) ; else pows := combinat[partition](n) ; resul := 0 ; for p from 1 to nops(pows) do c := combinat[permute](op(p, pows)) ; c1 := op(1, c) ; fac := nops(c) ; for i from 1 to nops(c1) do fac := fac*doublefactorial(2*op(i, c1)-1) ; od ; resul := resul-(-1)^nops(c1)*fac ; od : fi ; RETURN(resul) ; end; # R. J. Mathar, Apr 24 2006 # alternative Maple program: b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,       `if`(x=0, 1, b(x-1, y-1, false)*`if`(t, (x+y)/y, 1) +                    b(x-1, y+1, true)  ))     end: a:= n-> `if`(n=0, 1, b(2*n-2, 0, false)): seq(a(n), n=0..25);  # Alois P. Heinz, May 23 2015 a_list := proc(len) local n, A; if len=1 then return [1] fi: A := Array(-1..len-2); A[-1] := 1; A[0] := 1; for n to len-2 do A[n] := (2*n-1)*A[n-1]+add(A[j]*A[n-j-1], j=0..n-1) od: convert(A, list) end: a_list(20); # Peter Luschny, Jul 18 2017 MATHEMATICA a[n_] := a[n] = (2n - 1)!! - Sum[ a[n - k](2k - 1)!!, {k, n-1}]; Array[a, 18, 0] (* Ignacio D. Peixoto, Jun 23 2006 *) a[ n_] := If[ n < 0, 0, SeriesCoefficient[ 2 - 1 / Sum[ (2 k - 1)!! x^k, {k, 0, n}], {x, 0, n}]]; (* Michael Somos, Nov 16 2011 *) a[n_]:= SeriesCoefficient[1/x+(E^((1/2)/x) Sqrt[2/\[Pi]] Sqrt[-(1/x)])/Erfc[Sqrt[-(1/x)]/Sqrt[2]], {x, 0, n}, Assumptions -> x >0](* Robert Coquereaux, Sep 14 2014 *) max = 20; g = t/Fold[1 - ((t + #2)*z)/#1 &, 1, Range[max, 1, -1]]; T[n_, k_] := SeriesCoefficient[g, {z, 0, n}, {t, 0, k}]; a[0] = 1; a[n_] := Sum[T[n-1, k], {k, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jan 31 2016, after Philippe Deléham *) PROG (PARI) {a(n) = if( n<0, 0, polcoeff( 2 - 1 / sum( k=0, n, x^k * (2*k)! /(2^k * k!), x * O(x^n)), n))}; /* Michael Somos, Feb 08 2011 */ (PARI) {a(n) = my(A); if( n<1, n==0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = (2*k - 3) * A[k-1] + sum( j=1, k-1, A[j] * A[k-j])); A[n])}; /* Michael Somos, Jul 24 2011 */ (Python) from sympy import factorial2, cacheit @cacheit def a(n): return 1 if n == 0 else factorial2(2*n - 1) - sum(factorial2(2*k - 1)*a(n - k) for k in range(1, n)) [a(n) for n in range(51)]  # Indranil Ghosh, Jul 18 2017 CROSSREFS Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. Cf. A004208, A000165, A001147, A005412, A053979, A005411, A115974, A167872. Column k=1 of A258219, A258222. Row sums of A322398. Sequence in context: A152408 A046863 A185971 * A301932 A289313 A092881 Adjacent sequences:  A000695 A000696 A000697 * A000699 A000700 A000701 KEYWORD nonn,easy,nice AUTHOR EXTENSIONS Formula corrected by Ignacio D. Peixoto, Jun 23 2006 More terms from Sean A. Irvine, Feb 27 2011 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 16 05:26 EDT 2021. Contains 343030 sequences. (Running on oeis4.)