|
| |
|
|
A003436
|
|
Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.
(Formerly M3638)
|
|
4
| |
|
|
0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897, 4704612119, 108897613826, 2737023412199, 74236203425281, 2161288643251828, 67228358271588991, 2225173863019549229, 78087247031912850686, 2896042595237791161749
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Also called the relaxed menage problem (cf. A000179).
a(n) can be seen as a subset of the unordered pairings of the first 2n integers (A001147) with forbidden pairs (1,2n) and (i,i+1) for all i in [1,2n-1] (all adjacent integers modulo 2n). The linear version of this constraint is A000806. [From Olivier Gérard, Feb 8 2011]
|
|
|
REFERENCES
| Bogart, Kenneth P. and Doyle, Peter G., Nonsexist solution of the menage problem, Amer. Math. Monthly 93 (1986), no. 7, 514-519.
M. Hazewinkel and V. V. Kalashnikov, Counting Interlacing Pairs on the Circle, preprint.
D. Singmaster, Hamiltonian circuits on the n-dimensional octahedron. J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
FORMULA
| a(n)=2n*a(n-1)-2(n-1)*a(n-2)-a(n-3) for n>4 [Corrected by Vasu Tewari, Apr 11 2010]
G.f.: x+(1-x)/(1+x)* Sum_{n>=0} A001147(n)*(x/(1+x)^2)^n. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jun 27 2007
|
|
|
CROSSREFS
| Equals A003435(n)/(n!*2^n). A003437 gives unlabeled case.
First differences of A000806.
Sequence in context: A081054 A192407 A000858 * A199683 A114475 A076280
Adjacent sequences: A003433 A003434 A003435 * A003437 A003438 A003439
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
