login
A000699
Number of irreducible chord diagrams with 2n nodes.
(Formerly M3618 N1468)
79
1, 1, 1, 4, 27, 248, 2830, 38232, 593859, 10401712, 202601898, 4342263000, 101551822350, 2573779506192, 70282204726396, 2057490936366320, 64291032462761955, 2136017303903513184, 75197869250518812754, 2796475872605709079512, 109549714522464120960474, 4509302910783496963256400, 194584224274515194731540740
OFFSET
0,4
COMMENTS
Perturbation expansion in quantum field theory: spinor case in 4 spacetime dimensions.
a(n)*2^(-n) is the coefficient of the x^(2*n-1) term in the series reversal of the asymptotic expansion of 2*DawsonF(x) = sqrt(Pi)*exp(-x^2)*erfi(x) for x -> inf. - Vladimir Reshetnikov, Apr 23 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
A set partition is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...},{...z...t...}} for some x < z < y < t or z < x < t < y. Then a(n) is the number of topologically connected 2-uniform set partitions of {1...2n}. See my links for examples. - Gus Wiseman, Feb 23 2019
REFERENCES
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
Alois P. Heinz, Table of n, a(n) for n = 0..404 (terms up to n=100 from T. D. Noe)
S. Belinschi, M. Bozejko, F. Lehner, and R. Speicher, The normal distribution is "boxplus"-infinitely divisible, arXiv:0910.4263 [math.OA], 2009-2010.
Daniel J. Bernstein, S. Engels, T. Lange, R. Niederhagen, et al., Faster elliptic-curve discrete logarithms on FPGAs, Preprint, 2016.
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.
Michael Borinsky, Generating asymptotics for factorially divergent sequences, El. J. Combin. 25 (2018) P4.1, Sect 7.1.
Michael Borinsky, Gerald V. Dunne, and Karen Yeats, Tree-tubings and the combinatorics of resurgent Dyson-Schwinger equations, arXiv:2408.15883 [math-ph], 2024. See p. 9.
D. J. Broadhurst and D. Kreimer, Combinatoric explosion of renormalization ..., arXiv:hep-th/9912093, 1999, 2000.
D. J. Broadhurst and D. Kreimer, Combinatoric explosion of renormalization tamed by Hopf algebra: 30-loop Pad-Borel resummation, Phys. Lett. B 475 (2000), 63-70.
C. Brouder, On the trees of quantum fields, arXiv:hep-th/9906111, 1999, p. 6.
Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination, May 23, 2011.
Jonathan Burns and Tilahun Muche, Counting Irreducible Double Occurrence Words, arXiv preprint arXiv:1105.2926 [math.CO], 2011.
Julien Courtiel, Karen Yeats, and Noam Zeilberger, Connected chord diagrams and bridgeless maps, arXiv:1611.04611 [math.CO], 2016.
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)
P. Flajolet and M. Noy, Analytic Combinatorics of Chord Diagrams, in: Formal power series and algebraic combinatorics (FPSAC '00) Moscow, 2000, pp. 191-201.
M. Klazar, Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings, Advances in Appl. Math., Vol. 30 (2003), pp. 126-136.
M. Klazar, Counting even and odd partitions, Amer. Math. Monthly, 110 (No. 6, 2003), 527-532.
Ali Assem Mahmoud, On the Asymptotics of Connected Chord Diagrams, University of Waterloo (Ontario, Canada 2019).
Ali Assem Mahmoud, An Asymptotic Expansion for the Number of 2-Connected Chord Diagrams, arXiv:2009.12688 [math.CO], 2020.
Ali Assem Mahmoud, Chord Diagrams and the Asymptotic Analysis of QED-type Theories, arXiv:2011.04291 [hep-th], 2020.
Ali Assem Mahmoud, An asymptotic expansion for the number of two-connected chord diagrams, J. Math. Phys. (2023) Vol. 64, 122301. See Example 2.1.
Ali Assem Mahmoud and Karen Yeats, Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions, arXiv:2010.06550 [math.CO], 2020.
N. Marie, K. Yeats, A chord diagram expansion coming from some Dyson-Schwinger equations, arXiv:1210.5457, Section 4.1.
Albert Nijenhuis and Herbert S. Wilf, The enumeration of connected graphs and linked diagrams, J. Combin. Theory Ser. A 27 (1979), no. 3, 356--359. MR0555804 (82b:05074).
V. Pilaud and J. Rué, Analytic combinatorics of chord and hyperchord diagrams with k crossings, arXiv preprint arXiv:1307.6440 [math.CO], 2013.
E. A. Rødland, Pseudoknots in RNA Secondary Structures: Representation, Enumeration, and Prevalence, J. Comput. Biology, Vol 13, No 6 (2006), 1197-1213. (see equation 10)
R. R. Stein, On a class of linked diagrams, I. Enumeration, J. Combin. Theory, A 24 (1978), 357-366.
R. R. Stein and C. J. Everett, On a class of linked diagrams, II. Asymptotics, Discrete Math., 21 (1978), 309-318.
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]
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259 (nonseparable integer systems on n pairs). (Give an incorrect a(6)=2720.)
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:1803.10080 [math.LO], 2018-2019 (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.
FORMULA
a(n) = (n-1)*Sum_{i=1..n-1} a(i)*a(n-i) for n > 1, with a(1) = a(0) = 1. [Modified to include a(0) = 1. - Paul D. Hanna, Nov 06 2020]
A212273(n) = n * a(n). - Michael Somos, May 12 2012
G.f. satisfies: A(x) = 1 + x + x^2*[d/dx (A(x) - 1)^2/x]. - Paul D. Hanna, Dec 31 2010 [Modified to include a(0) = 1. - Paul D. Hanna, Nov 06 2020]
a(n) ~ n^n * 2^(n+1/2) / exp(n+1) * (1 - 31/(24*n) - 2207/(1152*n^2) - 3085547/(414720*n^3) - 1842851707/(39813120*n^4) - ...). - Vaclav Kotesovec, Feb 22 2014, extended Oct 23 2017
G.f. A(x) satisfies: 1 = A(x) - x/(A(x) - 2*x/(A(x) - 3*x/(A(x) - 4*x/(A(x) - 5*x/(A(x) - ...))))), a continued fraction relation. - Paul D. Hanna, Nov 04 2020
EXAMPLE
a(31)=627625976637472254550352492162870816129760 was computed using Kreimer's Hopf algebra of rooted trees. It subsumes 2.6*10^21 terms in quantum field theory.
G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 27*x^4 + 248*x^5 + 2830*x^6 +...
where d/dx (A(x) - 1)^2/x = 1 + 4*x + 27*x^2 + 248*x^3 + 2830*x^4 +...
MAPLE
A000699 := proc(n)
option remember;
if n <= 1 then
1;
else
add((2*i-1)*procname(i)*procname(n-i), i=1..n-1) ;
end if;
end proc:
seq(A000699(n), n=0..30) ; # R. J. Mathar, Jun 12 2018
MATHEMATICA
terms = 22; A[_] = 0; Do[A[x_] = x + x^2 * D[A[x]^2/x, x] + O[x]^(terms+1) // Normal, terms]; CoefficientList[A[x], x] // Rest (* Jean-François Alcover, Apr 06 2012, after Paul D. Hanna, updated Jan 11 2018 *)
a = ConstantArray[0, 20]; a[[1]]=1; Do[a[[n]] = (n-1)*Sum[a[[i]]*a[[n-i]], {i, 1, n-1}], {n, 2, 20}]; a (* Vaclav Kotesovec, Feb 22 2014 *)
Module[{max = 20, s}, s = InverseSeries[ComplexExpand[Re[Series[2 DawsonF[x], {x, Infinity, 2 max + 1}]]]]; Table[SeriesCoefficient[s, 2 n - 1] 2^n, {n, 1, max}]] (* Vladimir Reshetnikov, Apr 23 2016 *)
PROG
(PARI) {a(n)=local(A=1+x*O(x^n)); for(i=1, n, A=1+x+x^2*deriv((A-1)^2/x)+x*O(x^n)); polcoeff(A, n)} \\ Paul D. Hanna, Dec 31 2010 [Modified to include a(0) = 1. - Paul D. Hanna, Nov 06 2020]
(PARI) {a(n) = my(A); A = 1+O(x) ; for( i=0, n, A = 1+x + (A-1)*(2*x*A' - A + 1)); polcoeff(A, n)}; /* Michael Somos, May 12 2012 [Modified to include a(0) = 1. - Paul D. Hanna, Nov 06 2020] */
(PARI)
seq(N) = {
my(a = vector(N)); a[1] = 1;
for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;
};
seq(22) \\ Gheorghe Coserea, Jan 22 2017
(Python)
def A000699_list(n):
list = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
list[i] = (i - 1) * sum(list[j] * list[i - j] for j in range(1, i))
return list
print(A000699_list(22)) # M. Eren Kesim, Jun 23 2021
CROSSREFS
Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
Cf. A004300, A051862, A212273. Column sums of A232223. First column of A322402.
Sequence in context: A121063 A229619 A051863 * A138423 A239372 A239375
KEYWORD
nonn,easy,nice
EXTENSIONS
More terms from David Broadhurst, Dec 14 1999
Inserted "chord" in definition. - N. J. A. Sloane, Jan 19 2017
Added a(0)=1. - N. J. A. Sloane, Nov 05 2020
Modified formulas slightly to include a(0) = 1. - Paul D. Hanna, Nov 06 2020
STATUS
approved