|
|
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)
|
|
68
|
|
|
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
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 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
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.
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.
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.
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.
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.
Then Sf = 1/(1-Sigmaf) and S = 1/(1-Sigma). (End)
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
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
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
|
|
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
|
|
|
FORMULA
|
G.f.: 2 - 1/(1 + Sum_{n>=1} (2*n-1)!! * x^n ).
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/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. (End)
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)
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
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)):
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(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))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Formula corrected by Ignacio D. Peixoto, Jun 23 2006
|
|
STATUS
|
approved
|
|
|
|