A007769 Number of chord diagrams with n chords; number of pairings on a necklace.

1, 1, 2, 5, 18, 105, 902, 9749, 127072, 1915951, 32743182, 624999093, 13176573910, 304072048265, 7623505722158, 206342800616597, 5996837126024824, 186254702826289089, 6156752656678674792, 215810382466145354405, 7995774669504366055054

Offset: 0

Author

Jean.Betrema(AT)labri.u-bordeaux.fr

Keywords

• nonn
• easy
• nice

Comments

Place 2n points equally spaced on a circle. Draw lines to pair up all the points so that each point has exactly one partner.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• D. Bar-Natan, On the Vassiliev Knot Invariants, Topology 34 (1995) 423-472.
• D. Bar-Natan, Bibliography of Vassiliev Invariants.
• W. Y.-C. Chen, D. C. Torney, Equivalence classes of matchings and lattice-square designs, Discr. Appl. Math. 145 (3) (2005) 349-357., table of C_2n.
• Combinatorial Object Server, Information on Chord Diagrams
• Étienne Ghys, A Singular Mathematical Promenade, arXiv:1612.06373 [math.GT], 2016. See p. 252.
• A. Khruzin, Enumeration of chord diagrams, arXiv:math/0008209 [math.CO], 2000.
• R. J. Mathar, Feynman diagrams of the QED vacuum polarization, vixra:1901.0148 (2019), Section V.
• Joe Sawada, A fast algorithm for generating nonisomorphic chord diagrams, SIAM J. Discrete Math, Vol. 15, No. 4, 2002, pp. 546-561.
• Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233.
• Index entries for sequences related to necklaces

Crossrefs

Cf. A054499, A104255, A279207, A279208.

Programs

Maple

alpha:=proc(p, q)
    local k;
    if is(q, even) then
        add(binomial(p, 2*k)*q^k*doublefactorial(2*k-1), k=0..p/2)
    else
        q^(p/2)*doublefactorial(p-1)
    end if
end proc:
A007769 := proc(n)
    local p;
    if n = 0 then
        1;
    else
        add(alpha(2*n/p, p)*numtheory[phi](p), p=numtheory[divisors](2*n))/2/n
    end if;
end proc:
seq(A007769(n),n=0..10) ; # Robert FERREOL, Oct 10 2018

Mathematica

max = 20; alpha[p_, q_?EvenQ] := Sum[Binomial[p, 2k]*q^k*(2k-1)!!, {k, 0, max}]; alpha[p_, q_?OddQ] := q^(p/2)*(p-1)!!; a[0] = 1; a[n_] := Sum[q = 2n/p; alpha[p, q]*EulerPhi[q], {p, Divisors[2n]}]/(2n); Table[a[n], {n, 0, max}] (* Jean-François Alcover, May 07 2012, after R. J. Mathar *)
Stoimenow states that a Mma package is available from his website. - N. J. A. Sloane, Jul 26 2018

PARI

doublefactorial(n)={ local(resul) ; resul=1 ; forstep(i=n,2,-2, resul *= i ;) ; return(resul) ; }
alpha(n,q)={ if(q %2, return( q^(p/2)*doublefactorial(p-1)), return( sum(k=0,p/2,binomial(p,2*k)*q^k*doublefactorial(2*k-1)) ) ;) ; }
A007769(n)={ local(resul,q) ; if(n==0, return(1), resul=0 ; fordiv(2*n,p, q=2*n/p ; resul += alpha(p,q)*eulerphi(q) ;); return(resul/(2*n)) ;) ; } { for(n=0,20, print(n," ",A007769(n)) ;) ; } \\ R. J. Mathar, Oct 26 2006

Formula

2n a_n = Sum_{2n=pq} alpha(p, q)phi(q), phi = Euler function, alpha(p, q) = Sum_{k >= 0} binomial(p, 2k) q^k (2k-1)!! if q even, = q^{p/2} (p-1)!! if q odd.

Extensions

More terms from Christian G. Bower, Apr 06 2000

Corrected and extended by R. J. Mathar, Oct 26 2006