|
|
A054499
|
|
Number of pairings on a bracelet; number of chord diagrams that can be turned over and having n chords.
|
|
20
|
|
|
1, 1, 2, 5, 17, 79, 554, 5283, 65346, 966156, 16411700, 312700297, 6589356711, 152041845075, 3811786161002, 103171594789775, 2998419746654530, 93127358763431113, 3078376375601255821, 107905191542909828013, 3997887336845307589431
(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. Allow turning over.
|
|
REFERENCES
|
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n=3, there are 5 bracelets with 3 pairs of beads. They are represented by the words aabbcc, aabcbc, aabccb, abacbc, and abcabc. All of the 6!/(2*2*2) = 90 combinations can be derived from these by some combination of relabeling the pairs, rotation, and reflection. So a(3) = 5. - Michael B. Porter, Jul 27 2016
|
|
MATHEMATICA
|
max = 19;
alpha[p_, q_?EvenQ] := Sum[Binomial[p, 2*k]*q^k*(2*k-1)!!, {k, 0, max}];
alpha[p_, q_?OddQ] := q^(p/2)*(p-1)!!;
a[0] = 1;
a[n_] := 1/4*(Abs[HermiteH[n-1, I/2]] + Abs[HermiteH[n, I/2]] + (2*Sum[Block[{q = (2*n)/p}, alpha[p, q]*EulerPhi[q]], {p, Divisors[ 2*n]}])/(2*n));
|
|
CROSSREFS
|
Cf. A007769, A104256, A279207, A279208, A003437 (loopless chord diagrams), A322176 (marked chords), A362657, A362658, A362659 (three, four, five instances of each color rather than two), A371305 (Multiset Transf.).
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|