A003437 -id:A003437 - 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

A054499 Number of pairings on a bracelet; number of chord diagrams that can be turned over and having n chords.

Original entry on oeis.org

1, 1, 2, 5, 17, 79, 554, 5283, 65346, 966156, 16411700, 312700297, 6589356711, 152041845075, 3811786161002, 103171594789775, 2998419746654530, 93127358763431113, 3078376375601255821, 107905191542909828013, 3997887336845307589431

Offset: 0

Christian G. Bower, Apr 06 2000 based on a problem by Wouter Meeussen

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.

			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

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.

W. Y.-C. Chen, D. C. Torney, Equivalence classes of matchings and lattice-square designs, Discr. Appl. Math. 145 (3) (2005) 349-357.
Étienne Ghys, A Singular Mathematical Promenade, arXiv:1612.06373 [math.GT], 2016-2017. See p. 252.
A. Khruzin, Enumeration of chord diagrams, arXiv:math/0008209 [math.CO], 2000.
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.
R. J. Mathar, Chord Diagrams A054499 (2018)
R. J. Mathar, Feynman diagrams of the QED vacuum polarization, vixra:1901.0148 (2019)
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233.
Index entries for sequences related to bracelets

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.), A260847 (directed chords).

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));
Table[a[n], {n, 0, max}] (* Jean-François Alcover, Sep 05 2013, after R. J. Mathar; corrected by Andrey Zabolotskiy, Jul 27 2016 *)

a(n) = (2*A007769(n) + A047974(n) + A047974(n-1))/4 for n > 0.

Corrected and extended by N. J. A. Sloane, Oct 29 2006

a(0)=1 prepended back again by Andrey Zabolotskiy, Jul 27 2016

A129348 Number of (directed) Hamiltonian circuits in the cocktail party graph of order n.

Original entry on oeis.org

0, 2, 32, 1488, 112512, 12771840, 2036229120, 434469611520, 119619533537280, 41303040523960320, 17481826772405452800, 8902337068174698086400, 5370014079716477003366400, 3786918976243761421064601600, 3087031512410698159166482022400, 2880726660365605475506018320384000

Offset: 1

Eric W. Weisstein, Apr 10 2007

nonn

Also, the number of ways (up to rotations) to seat n married couples at a circular table with no spouses next to each other. Cf. A007060, A193639. - Geoffrey Critzer, Feb 09 2014

The cocktail party graph may also be called the n-octahedron, n-orthoplex or n-dimensional cross polytope. - Andrew Howroyd, May 14 2017

Max Alekseyev, Table of n, a(n) for n = 1..100
Marko R. Riedel, Math.Stackexchange.com Proof of asymptotic (saddle point method) and closed form (inclusion-exclusion)
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Cf. A003435, A003436, A003437, A007060, A167987.

a:= proc(n) option remember; `if`(n<3, n*(n-1),
     ((136*n^3-608*n^2+762*n-470) *a(n-1)
       +4*(n-2)*(14*n^2+29*n-193) *a(n-2)
       -80*(n-2)*(n-3)*(n-4) *a(n-3)) /(34*n-101))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 09 2014

Prepend[Table[Sum[(-1)^i Binomial[n, i] (2n - 1 - i)! 2^i, {i, 0, n}], {n, 2, 16}], 0] (* Geoffrey Critzer, Feb 09 2014 *)
Table[Piecewise[{{(-1 + 2 n)! Hypergeometric1F1[-n, 1 - 2 n, -2],
    n > 1}}], {n, 16}] (* Eric W. Weisstein, Mar 29 2014 *)

{ A129348(n) = sum(m=0,n-1, sum(k=1,n-m, (-1)^k * binomial(n-1,m) * binomial(n-m-1,k-1) * 2^(k-1) * ([0,k-1,2*(n-m-k);1,k-2,2*(n-m-k);1,k-1,2*(n-m-k-1)]^(2*n))[1,1] ) + sum(k=0,n-m, (-1)^k * binomial(n-1,m) * binomial(n-m-1,k) * 2^(k-1) * ([0,k,2*(n-m-k-1);2,k-1,2*(n-m-k-1);2,k,2*(n-m-k-2)]^(2*n))[1,1] ) ) } \\ Max Alekseyev, Dec 22 2013

For n>=2, a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)*(2*n-1-k)!*2^k. - Geoffrey Critzer, Feb 09 2014
Recurrence (for n>=4): (2*n-3)*a(n) = 2*(n-1)*(4*n^2 - 8*n + 5)*a(n-1) + 4*(n-2)*(n-1)*(2*n-1)*a(n-2). - Vaclav Kotesovec, Feb 09 2014
a(n) ~ sqrt(Pi) * 2^(2*n) * n^(2*n-1/2) / exp(2*n+1). - Vaclav Kotesovec, Feb 09 2014
For n>=2, a(n) = (-1 + 2 n)! Hypergeometric1F1[-n, 1 - 2 n, -2]. - Eric W. Weisstein, Mar 29 2014
a(n) = A003435(n) / (2*n) = A003436(n) * (n-1)! * 2^(n-1). - Andrew Howroyd, May 14 2017

Terms a(6) onward from Max Alekseyev, Nov 10 2007

A278991 a(n) is the number of simple linear diagrams with n+1 chords.

Original entry on oeis.org

0, 1, 3, 24, 211, 2325, 30198, 452809, 7695777, 146193678, 3069668575, 70595504859, 1764755571192, 47645601726541, 1381657584006399, 42829752879449400, 1413337528735664887, 49465522112961344241, 1830184115528550306438, 71375848864779552073957

Offset: 0

N. J. A. Sloane, Dec 07 2016

nonn

Gheorghe Coserea, Table of n, a(n) for n = 0..301
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.

Cf. A003436, A003437, A007474, A278990, A278992, A278993, A278994.

a[0] = 0; a[1] = 1; a[2] = 3; a[n_] := a[n] = (2 n - 1) a[n - 1] + (4 n - 3) a[n - 2] + (2 n - 4) a[n - 3]; Table[a@ n, {n, 0, 19}] (* Michael De Vlieger, Dec 10 2016 *)

seq(N) = {
  my(a = vector(N)); a[1]=1; a[2]=3; a[3]=24;
  for (n=4, N, a[n] = (2*n-1)*a[n-1] + (4*n-3)*a[n-2] + (2*n-4)*a[n-3]);
  concat(0, a);
};
seq(20) \\ Gheorghe Coserea, Dec 10 2016

N = 20; x = 'x + O('x^N);
concat(0, Vec(serlaplace((1-sqrt(1-2*x))*(1-2*x)^(-3/2)*exp(-1-x+sqrt(1-2*x))))) \\ Gheorghe Coserea, Dec 10 2016

E.g.f.: (1-sqrt(1-2*x))*(1-2*x)^(-3/2)*exp(-1-x+sqrt(1-2*x)).
a(n) ~ 2^(n+3/2) * n^(n+1) / exp(n+3/2). - Vaclav Kotesovec, Dec 07 2016
a(n) = (2*n-1)*a(n-1) + (4*n-3)*a(n-2) + (2*n-4)*a(n-3). - Gheorghe Coserea, Dec 10 2016

Offset corrected by Gheorghe Coserea, Dec 10 2016

A348817 a(n) = number of loopless diagrams by number of K_4 up to all symmetries.

Original entry on oeis.org

0, 1, 13, 2576, 2081393, 3309962320, 8755277273334, 35815698613833466, 214713439275724149414, 1808298469877117320495867

Offset: 1

Michael De Vlieger, Nov 01 2021

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. See Appendix Table 3.

Cf. A190830, A348815, A348816; A003437, A292409, A348820, A348823.

A348820 a(n) = number of loopless diagrams by number of K_5 up to all symmetries.

Original entry on oeis.org

0, 1, 42, 112418, 1105696796, 24178822553773, 1029696155560021174, 77938101941693076258854

Offset: 1

Michael De Vlieger, Nov 01 2021

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. See Appendix Table 4.

Cf. A190833, A348818, A348819; A003437, A292409, A348817, A348823.

A348823 a(n) = number of loopless diagrams by number of K_6 up to all symmetries.

Original entry on oeis.org

0, 1, 203, 5765385, 662305416760, 202380163158922023, 141390361908351519807928

Offset: 1

Michael De Vlieger, Nov 01 2021

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. See Appendix Table 5.

Cf. A190835, A348821, A348822; A003437, A292409, A348817, A348820.

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

A278992 Number of simple chord-labeled chord diagrams with n chords.

Original entry on oeis.org

0, 1, 1, 21, 168, 1968, 26094, 398653, 6872377, 132050271, 2798695656, 64866063276, 1632224748984, 44316286165297, 1291392786926821, 40202651019430461, 1331640833909877144, 46762037794122159492, 1735328399106396110310, 67858430028772637693845

Offset: 1

N. J. A. Sloane, Dec 07 2016

nonn

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.

Cf. A003436, A003437, A007474, A278990, A278991, A278993, A278994.

terms = 20;
CoefficientList[(Sqrt[1 - 2t]+1)(1/Sqrt[1 - 2t])*E^(Sqrt[1 - 2t] - t - 1) - (2-t)/E^t + O[t]^(terms+1), t]*Range[0, terms]! // Rest (* Jean-François Alcover, Sep 14 2018 *)

E.g.f.: (1+sqrt(1-2*t))*(1-2*t)^(-1/2)*exp(-1-t+sqrt(1-2*t))-(2-t)*exp(-t).
a(n) ~ 2^(n+1/2) * n^n / exp(n+3/2). - Vaclav Kotesovec, Dec 07 2016
Conjecture D-finite with recurrence: +(-n+2)*a(n) +(2*n^2-8*n+7)*a(n-1) +(6*n^2-18*n+11)*a(n-2) +(n-1)*(6*n-11)*a(n-3) +2*(n-1)*(n-2)*a(n-4)=0. - R. J. Mathar, Jan 27 2020

A278993 Number of simple chord diagrams with n chords, up to rotation.

Original entry on oeis.org

0, 1, 1, 4, 21, 176, 1893, 25030, 382272, 6604535, 127222636, 2702798537, 62778105236, 1582725739329, 43046433007765, 1256332883208474, 39165907107963273, 1298945495674093932, 45666536827274985585, 1696460750775267473762

Offset: 1

N. J. A. Sloane, Dec 07 2016

nonn

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.

Cf. A003436, A003437, A007474, A278990, A278991, A278992, A278994.

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

A054499 Number of pairings on a bracelet; number of chord diagrams that can be turned over and having n chords.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A129348 Number of (directed) Hamiltonian circuits in the cocktail party graph of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A278991 a(n) is the number of simple linear diagrams with n+1 chords.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A348817 a(n) = number of loopless diagrams by number of K_4 up to all symmetries.

Views

Author

Keywords

Links

Crossrefs

A348820 a(n) = number of loopless diagrams by number of K_5 up to all symmetries.

Views

Author

Keywords

Links

Crossrefs

A348823 a(n) = number of loopless diagrams by number of K_6 up to all symmetries.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs