A129348 -id:A129348 - cp's OEIS frontend

A003436 Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.

1, 0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897, 4704612119, 108897613826, 2737023412199, 74236203425281, 2161288643251828, 67228358271588991, 2225173863019549229, 78087247031912850686, 2896042595237791161749, 113184512236563589997407

Offset: 0

N. J. A. Sloane

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

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93:7 (1986), 514-519.
Robert Cori and G. Hetyei, Counting partitions of a fixed genus, arXiv preprint arXiv:1710.09992 [math.CO], 2017.
M. Hazewinkel and V. V. Kalashnikov, Counting Interlacing Pairs on the Circle, CWI report AM-R9508 (1995)
Evgeniy Krasko, Igor Labutin, and Alexander Omelchenko, Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete k-partite Graphs, arXiv:1709.03218 [math.CO], 2017.
E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, arXiv preprint arXiv:1601.05073 [math.CO], 2016.
E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, The Electronic Journal of Combinatorics, 24(3) (2017), #P3.43.
D. Singmaster, Hamiltonian circuits on the n-dimensional octahedron, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.
Gus Wiseman, The a(5) = 293 interlacing chord diagrams.

Cf. A003435, A129348. A003437 gives unlabeled case.
First differences of A000806.
Column k=2 of A324428.
Cf. A000179, A000296, A000699, A001147, A005493, A170941, A190823, A278990, A306386, A306419, A322402, A324011, A324172, A324173.

A003436 := proc(n) local k;
      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;
end proc: # R. J. Mathar, Dec 11 2013
A003436 := n-> `if`(n<2, 1-n, (-1)^n*2*hypergeom([n, -n], [], 1/2)):
seq(simplify(A003436(n)), n=0..18); # Peter Luschny, Nov 10 2016

a[n_] := (2*n-1)!! * Hypergeometric1F1[-n, 1-2*n, -2]; a[1] = 0;
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Apr 05 2013 *)
twounifll[{}]:={{}};twounifll[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@twounifll[Complement[set,s]]]/@Table[{i,j},{j,If[i==1,Select[set,2<#i+1&]]}];
Table[Length[twounifll[Range[n]]],{n,0,14,2}] (* Gus Wiseman, Feb 27 2019 *)

a(n) = A003435(n)/(n!*2^n).
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]
G.f.: x + ((1-x)/(1+x)) * Sum_{n>=0} A001147(n)*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 27 2007
a(n) ~ 2^(n+1/2)*n^n/exp(n+1). - Vaclav Kotesovec, Aug 13 2013
a(n) = (-1)^n*2*hypergeom([n, -n], [], 1/2) for n >= 2. - Peter Luschny, Nov 10 2016

a(0)=1 prepended by Gus Wiseman, Feb 27 2019

A368755 Number of regions in the hyperoctahedral (or cocktail party) graph of order n.

Original entry on oeis.org

0, 2, 18, 64, 186, 380, 838, 1504, 2242, 4082, 6266, 8320, 13010, 17866, 20218, 31808, 41390, 50100, 66530, 82560, 93446, 123642, 149398, 171920, 212166, 249810, 283678, 340704, 394882, 428892, 521406, 594560, 659382, 764866, 863154, 954192, 1086490, 1212506, 1326654, 1498720, 1660278

Offset: 1

Scott R. Shannon, Jan 04 2024

nonn

Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 9.
Scott R. Shannon, Image for n = 10.
Eric Weisstein's World of Mathematics, Cocktail Party Graph.

Cf. A368756 (vertices), A368757 (edges), A368758 (k-gons), A129348, A193130, A282010.

a(n) = A368757(n) - A368756(n) + 1 by Euler's formula.

A368756 Number of vertices in the hyperoctahedral (or cocktail party) graph of order n.

Original entry on oeis.org

2, 5, 17, 49, 151, 273, 693, 1249, 1711, 3525, 5529, 6777, 11711, 16133, 15937, 29121, 38227, 44561, 61985, 77041, 81423, 116165, 140997, 157649, 201211, 237125, 263449, 324689, 377359, 392185, 499789, 570241, 621255, 735493, 831537, 909097, 1048887, 1171013, 1265501, 1450081, 1608523

Offset: 1

Scott R. Shannon, Jan 04 2024

nonn

Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 9.
Scott R. Shannon, Image for n = 10.
Scott R. Shannon, Image for n = 15. Note this 30-gon still contains vertices with 7 chords crossing, so this maximum possible value is the same as the regular n-gon with all diagonals drawn; see A007569.
Eric Weisstein's World of Mathematics, Cocktail Party Graph.

Cf. A368755 (regions), A368757 (edges), A368758 (k-gons), A007569, A129348, A193130, A282010.

a(n) = A368757(n) - A368755(n) + 1 by Euler's formula.

A368758 Irregular table read by rows: T(n,k) is the number of k-sided regions, k>=3, in the hyperoctahedral (or cocktail party) graph of order n.

Original entry on oeis.org

0, 2, 14, 2, 2, 42, 22, 100, 72, 12, 2, 234, 142, 4, 418, 320, 90, 10, 734, 610, 116, 44, 1248, 878, 82, 20, 14, 1968, 1454, 534, 98, 12, 16, 2696, 2662, 744, 74, 56, 34, 4040, 3434, 770, 74, 0, 2, 5806, 4722, 1932, 430, 94, 26, 7706, 7102, 2048, 894, 92, 24, 10868, 7492, 1448, 406, 4

Offset: 1

Scott R. Shannon, Jan 04 2024

See A368755 and A368756 for further images of the graphs.

			The table begins:
0;
2;
14, 2, 2;
42, 22;
100, 72, 12, 2;
234, 142, 4;
418, 320, 90, 10;
734, 610, 116, 44;
1248, 878, 82, 20, 14;
1968, 1454, 534, 98, 12, 16;
2696, 2662, 744, 74, 56, 34;
4040, 3434, 770, 74, 0, 2;
5806, 4722, 1932, 430, 94, 26;
7706, 7102, 2048, 894, 92, 24;
10868, 7492, 1448, 406, 4;
13438, 12122, 4682, 1356, 206, 4;
17438, 15950, 5420, 2194, 296, 84, 6, 2;
22990, 17734, 7166, 1976, 182, 52;
27284, 25902, 9672, 2718, 772, 182;
34160, 31164, 12650, 3710, 648, 188, 0, 0, 8, 32;
.
.

Scott R. Shannon, Image for T(8,k).
Eric Weisstein's World of Mathematics, Cocktail Party Graph.

Cf. A368755 (regions), A368756 (vertices), A368757 (edges), A129348, A193130, A282010.

Sum of row n = A368755(n).

A368757 Number of edges in the hyperoctahedral (or cocktail party) graph of order n.

Original entry on oeis.org

0, 6, 34, 112, 336, 652, 1530, 2752, 3952, 7606, 11794, 15096, 24720, 33998, 36154, 60928, 79616, 94660, 128514, 159600, 174868, 239806, 290394, 329568, 413376, 486934, 547126, 665392, 772240, 821076, 1021194, 1164800, 1280636, 1500358, 1694690, 1863288, 2135376, 2383518, 2592154

Offset: 1

Scott R. Shannon, Jan 04 2024

nonn

See A368755 and A368756 for images of the graphs.

Eric Weisstein's World of Mathematics, Cocktail Party Graph.

Cf. A368755 (regions), A368756 (vertices), A368758 (k-gons), A129348, A193130, A282010.

a(n) = A368755(n) + A368756(n) - 1 by Euler's formula.

A003435 Number of directed Hamiltonian circuits on n-octahedron with a marked starting node.

Original entry on oeis.org

8, 192, 11904, 1125120, 153262080, 28507207680, 6951513784320, 2153151603671040, 826060810479206400, 384600188992919961600, 213656089636192754073600, 139620366072628402087526400, 106033731334825319789808844800

Offset: 2

N. J. A. Sloane

Also called the relaxed menage problem (cf. A000179).

These are labeled and the order and starting point matter.

			n=2: label vertices of a square 1,2,3,4. Then the 8 Hamiltonian circuits are 1234, 1432, 2341, 2143, 3412, 3214, 4123, 4321; so a(2) = 8.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 2..100
Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93 (1986), no. 7, 514-519.
D. Singmaster, Enumerating unlabeled Hamiltonian circuts, Preprint (1974).
D. Singmaster, Hamiltonian circuits on the n-dimensional octahedron, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.
D. Singmaster, Letter to N. J. A. Sloane, May 1975
Eric Weisstein's World of Mathematics, Cocktail Party Graph

Cf. A003436, A003437, A129348.

[(&+[ (-1)^k*2^(k+1)*n*Binomial(n, k)*Factorial(2*n-k-1): k in [0..n]]) : n in [2..20]]; // G. C. Greubel, Nov 17 2022

A003435 := n->add((-1)^k*binomial(n,k)*((2*n)/(2*n-k))*2^k*(2*n-k)!,k=0..n);

a[n_] := 2^n*n!*(2n-1)!!*Hypergeometric1F1[-n, 1-2n, -2]; Table[ a[n], {n, 2, 14}] (* Jean-François Alcover, Nov 04 2011 *)

a(n)=sum(k=0,n,(-1)^k*binomial(n,k)*((2*n)/(2*n-k))*2^k*(2*n-k)!) \\ Charles R Greathouse IV, Nov 04 2011

[sum( (-1)^k*2^(k+1)*n*binomial(n, k)*factorial(2*n-k-1) for k in (0..n)) for n in (2..20)] # G. C. Greubel, Nov 17 2022

For n >= 2, a(n) = Sum_{k=0..n}(-1)^k*binomial(n, k)*((2*n)/(2*n-k))*2^k*(2*n-k)!.
Conjecture: a(n) -(4*n^2 - 2*n + 5)*a(n-1) + 2*(n-1)*(4*n-17)*a(n-2) + 12*(n-1)*(n-2)*a(n-3) = 0. - R. J. Mathar, Oct 02 2013
Recurrence: (2*n-3)*a(n) = 2*n*(4*n^2 - 8*n + 5)*a(n-1) + 4*(n-1)*n*(2*n-1)*a(n-2). - Vaclav Kotesovec, Feb 12 2014
a(n) ~ sqrt(Pi) * 2^(2*n+1) * n^(2*n+1/2) / exp(2*n+1). - Vaclav Kotesovec, Feb 12 2014
a(n) = -(-2)^(n+1)*n!*hypergeom([n, -n], [], 1/2). - Peter Luschny, Nov 10 2016

Name made more precise by Andrew Howroyd, May 14 2017

A307923 Number of (undirected) Hamiltonian cycles in the n-cocktail party graph.

Original entry on oeis.org

0, 1, 16, 744, 56256, 6385920, 1018114560, 217234805760, 59809766768640, 20651520261980160, 8740913386202726400, 4451168534087349043200, 2685007039858238501683200, 1893459488121880710532300800, 1543515756205349079583241011200, 1440363330182802737753009160192000

Offset: 1

Eric W. Weisstein, May 06 2019

nonn

Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Cf. A129348, A167987, A307935.

Join[{0}, Table[Gamma[2 n] Hypergeometric1F1[-n, 1 - 2 n, -2]/2, {n, 2, 20}]] (* Eric W. Weisstein, Feb 20 2025 *)
Join[{0}, RecurrenceTable[{-4 (1 + n) (2 + n) (5 + 2 n) a[n] - 2 (2 + n) (17 + 16 n + 4 n^2) a[n + 1] + (3 + 2 n) a[n + 2] == 0, a[1] == 1, a[2] == 16}, a[n], {n, 20}]] (* Eric W. Weisstein, Feb 20 2025 *)

a(n) = A129348(n)/2.

A286038 Number of (undirected) paths in the n-cocktail party graph.

Original entry on oeis.org

0, 12, 396, 21672, 1918920, 250696980, 45304472052, 10816917169296, 3296928965854032, 1248938916843586140, 575559130836761023260, 317049200473798671358392, 205722831410326997504441496, 155295648728262284680608862692, 134934407215203512994225979686660

Offset: 1

Eric W. Weisstein, Jun 15 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Graph Path

Cf. A167987 (cycles), A007060 (Hamiltonian paths), A129348 (Hamiltonian cycles).

a[n_] := (1/2)*(-2n - 1 + Sum[Sum[(-1)^j*2^j*(k - j)!*Binomial[n, j]* Binomial[2n - 2j, k - 2j], {k, 2j, 2n}], {j, 0, n}]);
Array[a, 15] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)
Table[(Sum[(-2)^k Binomial[n, k] k! HypergeometricU[k + 1, 2 n + 2 - k, 1], {k, 0, n}] - 2 n - 1)/2, {n, 20}] // FunctionExpand (* Eric W. Weisstein, Oct 02 2017 *)

a(n) = (-2*n-1 + sum(j=0,n, sum(k=2*j,2*n, (-1)^j*2^j*(k-j)! * binomial(n,j) * binomial(2*n-2*j, k-2*j))) )/2; \\ Andrew Howroyd, Jun 19 2017

a(n) = (1/2) * (-2*n - 1 + Sum_{j=0..n} Sum_{k=2*j..2*n} (-1)^j*2^j*(k-j)! * binomial(n,j) * binomial(2*n-2*j,k-2*j) ). - Andrew Howroyd, Jun 19 2017

Terms a(7) and beyond from Andrew Howroyd, Jun 19 2017

cp's OEIS Frontend

A003436 Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A368755 Number of regions in the hyperoctahedral (or cocktail party) graph of order n.

Views

Author

Keywords

Links

Crossrefs

Formula

A368756 Number of vertices in the hyperoctahedral (or cocktail party) graph of order n.

Views

Author

Keywords

Links

Crossrefs

Formula

A368758 Irregular table read by rows: T(n,k) is the number of k-sided regions, k>=3, in the hyperoctahedral (or cocktail party) graph of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A368757 Number of edges in the hyperoctahedral (or cocktail party) graph of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A003435 Number of directed Hamiltonian circuits on n-octahedron with a marked starting node.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A307923 Number of (undirected) Hamiltonian cycles in the n-cocktail party graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A286038 Number of (undirected) paths in the n-cocktail party graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI