cp's OEIS Frontend

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

%I A007769 #73 Jul 11 2025 10:43:17
%S A007769 1,1,2,5,18,105,902,9749,127072,1915951,32743182,624999093,
%T A007769 13176573910,304072048265,7623505722158,206342800616597,
%U A007769 5996837126024824,186254702826289089,6156752656678674792,215810382466145354405,7995774669504366055054
%N A007769 Number of chord diagrams with n chords; number of pairings on a necklace.
%C A007769 Place 2n points equally spaced on a circle. Draw lines to pair up all the points so that each point has exactly one partner.
%H A007769 Vincenzo Librandi, <a href="/A007769/b007769.txt">Table of n, a(n) for n = 0..200</a>
%H A007769 D. Bar-Natan, <a href="http://dx.doi.org/10.1016/0040-9383(95)93237-2">On the Vassiliev Knot Invariants</a>, Topology 34 (1995) 423-472.
%H A007769 D. Bar-Natan, <a href="http://www.pdmi.ras.ru/~duzhin/VasBib/">Bibliography of Vassiliev Invariants</a>.
%H A007769 W. Y.-C. Chen, D. C. Torney, <a href="http://dx.doi.org/10.1016/j.dam.2004.02.013">Equivalence classes of matchings and lattice-square designs</a>, Discr. Appl. Math. 145 (3) (2005) 349-357., table of C_2n.
%H A007769 Combinatorial Object Server, <a href="http://combos.org/necklace">Information on Chord Diagrams</a>
%H A007769 Étienne Ghys, <a href="http://arxiv.org/abs/1612.06373">A Singular Mathematical Promenade</a>, arXiv:1612.06373 [math.GT], 2016. See p. 252.
%H A007769 A. Khruzin, <a href="https://arxiv.org/abs/math/0008209">Enumeration of chord diagrams</a>, arXiv:math/0008209 [math.CO], 2000.
%H A007769 R. J. Mathar, <a href="http://vixra.org/abs/1901.0148">Feynman diagrams of the QED vacuum polarization</a>, vixra:1901.0148 (2019), Section V.
%H A007769 Joe Sawada, <a href="https://doi.org/10.1137/S0895480100377970">A fast algorithm for generating nonisomorphic chord diagrams</a>, SIAM J. Discrete Math, Vol. 15, No. 4, 2002, pp. 546-561.
%H A007769 Alexander Stoimenow, <a href="https://doi.org/10.1016/S0012-365X(99)00347-7">On the number of chord diagrams</a>, Discr. Math. 218 (2000), 209-233.
%H A007769 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A007769 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.
%p A007769 alpha:=proc(p, q)
%p A007769     local k;
%p A007769     if is(q, even) then
%p A007769         add(binomial(p, 2*k)*q^k*doublefactorial(2*k-1), k=0..p/2)
%p A007769     else
%p A007769         q^(p/2)*doublefactorial(p-1)
%p A007769     end if
%p A007769 end proc:
%p A007769 A007769 := proc(n)
%p A007769     local p;
%p A007769     if n = 0 then
%p A007769         1;
%p A007769     else
%p A007769         add(alpha(2*n/p, p)*numtheory[phi](p), p=numtheory[divisors](2*n))/2/n
%p A007769     end if;
%p A007769 end proc:
%p A007769 seq(A007769(n),n=0..10) ; # _Robert FERREOL_, Oct 10 2018
%t A007769 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_ *)
%t A007769 Stoimenow states that a Mma package is available from his website. - _N. J. A. Sloane_, Jul 26 2018
%o A007769 (PARI) doublefactorial(n)={ local(resul) ; resul=1 ; forstep(i=n,2,-2, resul *= i ;) ; return(resul) ; }
%o A007769 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)) ) ;) ; }
%o A007769 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
%Y A007769 Cf. A054499, A104255, A279207, A279208.
%K A007769 nonn,easy,nice
%O A007769 0,3
%A A007769 Jean.Betrema(AT)labri.u-bordeaux.fr
%E A007769 More terms from _Christian G. Bower_, Apr 06 2000
%E A007769 Corrected and extended by _R. J. Mathar_, Oct 26 2006