|
|
A003436
|
|
Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.
(Formerly M3638)
|
|
29
|
|
|
1, 0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897, 4704612119, 108897613826, 2737023412199, 74236203425281, 2161288643251828, 67228358271588991, 2225173863019549229, 78087247031912850686, 2896042595237791161749, 113184512236563589997407
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Also called the relaxed ménage 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. - Olivier Gérard, Feb 08 2011
Number of perfect matchings in the complement of C_{2n} where C_{2n} is the cycle graph on 2n vertices. - Andrew Howroyd, Mar 15 2016
Also the number of 2-uniform set partitions of {1...2n} containing no two cyclically successive vertices in the same block. - Gus Wiseman, Feb 27 2019
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2*n*a(n-1)-2*(n-3)*a(n-2)-a(n-3) for n>4. [Corrected by Vasu Tewari, Apr 11 2010, and by R. J. Mathar, Oct 02 2013]
a(n) = (-1)^n*2*hypergeom([n, -n], [], 1/2) for n >= 2. - Peter Luschny, Nov 10 2016
|
|
MAPLE
|
if n = 0 then 1
elif n = 1 then 0
else add( (-1)^k*binomial(n, k)*2*n/(2*n-k)*2^k*(2*n-k)!/2^n/n!, k=0..n) ;
end if;
A003436 := n-> `if`(n<2, 1-n, (-1)^n*2*hypergeom([n, -n], [], 1/2)):
|
|
MATHEMATICA
|
a[n_] := (2*n-1)!! * Hypergeometric1F1[-n, 1-2*n, -2]; a[1] = 0;
twounifll[{}]:={{}}; twounifll[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@twounifll[Complement[set, s]]]/@Table[{i, j}, {j, If[i==1, Select[set, 2<#<Last[set]&], Select[set, #>i+1&]]}];
Table[Length[twounifll[Range[n]]], {n, 0, 14, 2}] (* Gus Wiseman, Feb 27 2019 *)
|
|
CROSSREFS
|
Cf. A000179, A000296, A000699, A001147, A005493, A170941, A190823, A278990, A306386, A306419, A322402, A324011, A324172, A324173.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|