|
%I M1974 N0783 #278 Nov 19 2023 14:33:55
%S 1,1,2,10,74,706,8162,110410,1708394,29752066,576037442,12277827850,
%T 285764591114,7213364729026,196316804255522,5731249477826890,
%U 178676789473121834,5925085744543837186,208256802758892355202,7734158085942678174730
%N 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!.
%C 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]
%C 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
%C Starting (1, 2, 10, 74, ...) = INVERTi transform of A001147: (1, 3, 15, 105, ...). - _Gary W. Adamson_, Oct 21 2009
%C The Cvitanovic et al. paper relates this sequence to A005411 and A005413. - _Robert Munafo_, Jan 24 2010
%C Hankel transform of a(n+1) is A168467. - _Paul Barry_, Nov 26 2009
%C 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
%C 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 k<n; otherwise it is indecomposable. For example, the perfect matching 1-2,3-4 is decomposable, and a(2) = 2 counts 1-3,2-4 and 1-4,2-3. - _David Callan_, Nov 29 2012
%C From _Robert Coquereaux_, Sep 12 2014: (Start)
%C QED diagrams are graphs with two kinds of edges (lines): a (non-oriented), f (oriented), and only one kind of (internal) vertex: aff. They may have internal and external (i.e., pendant) lines. The order is the number of (internal) vertices. Vanishing diagrams: QED diagrams containing loops of type f with an odd number of vertices are set to 0 (Furry theorem). Proper diagrams: connected QED diagrams that remain connected when an arbitrary internal line is cut.
%C The number of Feynman diagrams of order 2n for the electron propagator (2-point function of QED), vanishing or not, proper or not, of order 2n, starting from n = 0, is given by 1, 2, 10, 74, 706, 8162, ..., i.e., this sequence A000698, with the first term (equal to 1) dropped. Call Sf the associated g.f.
%C The number of non-vanishing Feynman diagrams, for the same 2-point function, is given by 1, 1, 4, 25, 208, 2146, ..., i.e., by the sequence A005411, with a first term of order 0, equal to 1, added. Call S the associated g.f.
%C If one does not remove the vanishing diagram, but, at the same time, considers only those graphs that are proper, one obtains the Feynman diagrams (vanishing and non-vanishing) for the self-energy function of QED, 0, 1, 3, 21, 207, 2529, ..., i.e., the sequence A115974 with a first term of order 0, equal to 0, added. A115974 is twice A167872. Call Sigmaf the associated g.f.
%C If one removes the vanishing diagrams and, at the same time, considers only those graphs that are proper, one obtains the Feynman diagrams for the self-energy function of QED given by 0, 1, 3, 18, 153, 1638, ..., i.e., by the sequence A005412, with a first term of order 0, equal to 0, added. Call Sigma the associated g.f.
%C Then Sf = 1/(1-Sigmaf) and S = 1/(1-Sigma). (End)
%C For n>0 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
%C Also, counts certain isomorphism classes of closed normal linear lambda terms. [N. Zeilberger, 2015]. - _N. J. A. Sloane_, Sep 18 2016
%C 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
%C For n >= 2, a(n) is the number of coalescent histories for a pair consisting of a matching lodgepole gene tree and species tree with 2n-1 leaves. - _Noah A Rosenberg_, Jun 21 2022
%D 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.
%D R. W. Robinson, Counting irreducible Feynman diagrams exactly and asymptotically, Abstracts Amer. Math. Soc., 2002, #975-05-270.
%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).
%H Vincenzo Librandi, <a href="/A000698/b000698.txt">Table of n, a(n) for n = 0..200</a>
%H D. Arques and J.-F. Beraud, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00197-1">Rooted maps on orientable surfaces, Riccati's equation and continued fractions</a>, Discrete Math., 215 (2000), 1-12.
%H F. Battaglia and T. F. George, <a href="http://dx.doi.org/10.1007/BF01167204">A Pascal type triangle for the number of topologically distinct many-electron Feynman diagrams</a>, J. Math. Chem. 2 (1988) 241-247.
%H S. Birdsong and G. Hetyei, <a href="http://arxiv.org/abs/1111.4710">A Gray Code for the Shelling Types of the Boundary of a Hypercube</a>, arXiv preprint arXiv:1111.4710 [math.CO], 2011.
%H S. Birdsong and G. Hetyei, <a href="https://doi.org/10.1016/j.disc.2012.10.011">A Gray Code for the Shelling Types of the Boundary of a Hypercube</a>, Discrete Math. 313 (2013), no. 3, 258-268. MR2995390.
%H Jonathan Burns, <a href="http://shell.cas.usf.edu/~saito/DNAweb/SimpleAssemblyTable.txt">Assembly Graph Words - Single Transverse Component (Counts)</a>
%H Jonathan Burns and Tilahun Muche, <a href="http://arxiv.org/abs/1105.2926">Counting Irreducible Double Occurrence Words</a>, arXiv preprint arXiv:1105.2926 [math.CO], 2011, Lemma 3.2.
%H Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, <a href="http://dx.doi.org/10.1016/j.dam.2013.01.003">Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination</a>, Disc. Appl. Math. 161 (2013) 1378-1394
%H J. Courtiel, K. Yeats, and N. Zeilberger, <a href="https://arxiv.org/abs/1611.04611">Connected chord diagrams and bridgeless maps</a>, arXiv:1661.04611, Proposition 13.
%H P. Cvitanovic, B. Lautrup and R. B. Pearson, <a href="https://cns.gatech.edu/~predrag/papers/PRD18-78.pdf">The number and weights of Feynman diagrams</a>, Phys. Rev. D18, (1978), 1939-1949, (eq 3.34 and fig 2b). <a href="https://doi.org/10.1103/PhysRevD.18.1939">DOI:10.1103/PhysRevD.18.1939</a>
%H M. A. Deryagina and A. D. Mednykh, <a href="http://dx.doi.org/10.1134/S0037446613040058">On the enumeration of circular maps with given number of edges</a>, Siberian Mathematical Journal, 54, No. 6, 2013, 624-639.
%H F. Disanto and N. A. Rosenberg, <a href="https://doi.org/10.1089/cmb.2015.0015">Coalescent histories for lodgepole species trees</a>, J. Comput. Biol. 22 (2015), 918-929.
%H S. Dulucq, <a href="/A005819/a005819.pdf">Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots</a>, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy)
%H Trinh Khanh Duy and Tomoyuki Shirai, <a href="http://arxiv.org/abs/1504.06904">The mean spectral measures of random Jacobi matrices related to Gaussian beta ensembles</a>, arXiv:1504.06904 [math.SP], 2015.
%H G. Edgar, <a href="http://arxiv.org/abs/0801.4877">Transseries for beginners</a>, arXiv:0801.4877v5 [math.RA], 2008-2009.
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H Ali Assem Mahmoud, <a href="https://uwaterloo.ca/scholar/a39mahmo/publications/aymptotics-connected-chord-diagrams">On the Asymptotics of Connected Chord Diagrams</a>, University of Waterloo (Ontario, Canada 2019).
%H Ali Assem Mahmoud and Karen Yeats, <a href="https://arxiv.org/abs/2010.06550">Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions</a>, arXiv:2010.06550 [math.CO], 2020.
%H R. J. Martin and M. J. Kearney, <a href="http://arXiv.org/abs/1103.4936">An exactly solvable self-convolutive recurrence</a>, arXiv:1103.4936 [math.CO], 2011.
%H R. J. Martin and M. J. Kearney, <a href="http://dx.doi.org/10.1007/s00010-010-0051-0">An exactly solvable self-convolutive recurrence</a>, Aequat. Math., 80 (2010), 291-318. see p. 292.
%H R. J. Mathar, <a href="http://dx.doi.org/10.1002/qua.21334">Table of Feynman Diagrams of the Interacting Fermion Green's Function</a>, Int. J. Quant. Chem. 107 (2007) 1975. Also on <a href="http://arxiv.org/abs/physics/0512022">arXiv</a>, arXiv:physics/0512022 [physics.atom-ph], 2015-2016.
%H R. J. Mathar, <a href="http://vixra.org/abs/1901.0148">Feynman diagrams of the QED vacuum polarization</a>, vixra:1901.0148 (2019), Section VII.
%H L. G. Molinari, <a href="http://dx.doi.org/10.1103/PhysRevB.71.113102">Hedin's equations and enumeration of Feynman diagrams</a>, Phys. Rev. B, 71 (2005), 113102.
%H A. Prunotto, W. M. Alberico, and P. Czerski, <a href="https://doi.org/10.1515/phys-2018-0023">Feynman diagrams and rooted maps</a>, Open Phys. 16 (2018) 149-167.
%H J. Touchard, <a href="http://dx.doi.org/10.4153/CJM-1952-001-8">Sur un problème de configurations et sur les fractions continues</a>, Canad. J. Math., 4 (1952), 2-25.
%H J. Touchard, <a href="/A000698/a000698.pdf">Sur un problème de configurations et sur les fractions continues</a>, Canad. J. Math., 4 (1952), 2-25. [Annotated, corrected, scanned copy]
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Feynman_diagram">Feynman diagram</a>
%H Noam Zeilberger, <a href="http://arxiv.org/abs/1509.07596">Counting isomorphism classes of beta-normal linear lambda terms</a>, arXiv:1509.07596 [cs.LO], 2015.
%H Noam Zeilberger, <a href="https://arxiv.org/abs/1804.10540">A theory of linear typings as flows on 3-valent graphs</a>, arXiv:1804.10540 [cs.LO], 2018.
%H Noam Zeilberger, <a href="https://arxiv.org/abs/1803.10080">A Sequent Calculus for a Semi-Associative Law</a>, arXiv preprint 1803.10030, March 2018 (A revised version of a 2017 conference paper)
%H Noam Zeilberger, <a href="https://vimeo.com/289907363">A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video)</a>, Rutgers Experimental Math Seminar, Sep 13 2018. Part 2 is vimeo.com/289910554.
%H P. Zinn-Justin and J.-B. Zuber, <a href="http://arXiv.org/abs/math-ph/0303049">Matrix integrals and the generation and counting of virtual tangles and links</a>, arXiv:math-ph/0303049, 2003.
%F G.f.: 2 - 1/(1 + Sum_{n>=1} (2*n-1)!! * x^n ).
%F a(n+1) = Sum_{k=0..n} A089949(n, k)*2^k. - _Philippe Deléham_, Aug 15 2005
%F a(n+1) = Sum_{k=0..n} A053979(n,k). - _Philippe Deléham_, Mar 24 2007
%F From _Paul Barry_, Nov 26 2009: (Start)
%F G.f.: 1+x/(1-2x/(1-3x/(1-4x/(1-5x/(1-6x/(1-... (continued fraction).
%F 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)
%F 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
%F 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
%F From _Peter Bala_, Dec 22 2011: (Start)
%F 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.
%F 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. (End)
%F 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)
%F Continued fractions:
%F G.f.: 2 - G(0) where G(k) = 1 - (k+1)*x/G(k+1).
%F G.f.: 2 - U(0) where U(k) = 1 - (2*k+1)*x/(1 - (2*k+2)*x/U(k+1)).
%F G.f.: 2 - U(0) where U(k) = 1 - (4*k+1)*x - (2*k+1)*(2*k+2)*x^2/U(k+1)).
%F G.f.: 1/Q(0) where Q(k) = 1 - x*(2*k+2)/(1 - x*(2*k+3)/Q(k+1)).
%F G.f.: 1 + x/Q(0) where Q(k) = 1 - x*(k+2)/Q(k+1)).
%F 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))).
%F G.f.: 1 + x*G(0) where G(k) = 1 - x*(k+2)/(x*(k+2) - 1/G(k+1)).
%F G.f.: 2 - 1/B(x) where B(x) is the g.f. of A001147.
%F G.f.: 1 + x/(1-2*x*B(x)) where B(x) is the g.f. of A167872. (End)
%F a(n) ~ 2^(n+1/2) * n^n / exp(n). - _Vaclav Kotesovec_, Mar 10 2014
%F G.f.: 1 + x*(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
%F From _Peter Bala_, May 23 2017: (Start)
%F G.f. A(x) = 1 + x/(1 + x - 3*x/(1 + 3*x - 5*x/(1 + 5*x - 7*x/(1 + 7*x - ...)))).
%F 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)
%e G.f. = 1 + x + 2*x^2 + 10*x^3 + 74*x^4 + 706*x^5 + 8162*x^6 + 110410*x^7 + ...
%p A006882 := proc(n) option remember; if n <= 1 then 1 else n*procname(n-2); fi; end;
%p 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;
%p 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
%p # alternative Maple program:
%p b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
%p `if`(x=0, 1, b(x-1, y-1, false)*`if`(t, (x+y)/y, 1) +
%p b(x-1, y+1, true) ))
%p end:
%p a:= n-> `if`(n=0, 1, b(2*n-2, 0, false)):
%p seq(a(n), n=0..25); # _Alois P. Heinz_, May 23 2015
%p 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
%t 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 *)
%t 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 *)
%t a[n_]:= SeriesCoefficient[1+x(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 *)
%t 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_ *)
%o (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 */
%o (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 */
%o (Python)
%o from sympy import factorial2, cacheit
%o @cacheit
%o 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))
%o [a(n) for n in range(51)] # _Indranil Ghosh_, Jul 18 2017
%Y Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
%Y Cf. A004208, A000165, A001147, A005412, row sums of A053979, A005411, A115974, A167872.
%Y Column k=1 of A258219, A258222.
%Y Row sums of A322398.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_, _Richard Ehrenborg_, _Gabor Hetyei_
%E Formula corrected by Ignacio D. Peixoto, Jun 23 2006
%E More terms from _Sean A. Irvine_, Feb 27 2011
|
