|
|
A007769
|
|
Number of chord diagrams with n chords; number of pairings on a necklace.
|
|
14
|
|
|
1, 1, 2, 5, 18, 105, 902, 9749, 127072, 1915951, 32743182, 624999093, 13176573910, 304072048265, 7623505722158, 206342800616597, 5996837126024824, 186254702826289089, 6156752656678674792, 215810382466145354405, 7995774669504366055054
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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
|
|
|
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.
|
|
MAPLE
|
with(numtheory):
alpha:=proc(p, q):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) fi end:
a:=n->add(alpha(2*n/p, p)*phi(p), p=divisors(2*n))/2/n:
|
|
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
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Jean.Betrema(AT)labri.u-bordeaux.fr
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|