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

A324429 Number T(n,k) of labeled cyclic chord diagrams having n chords and minimal chord length k (or k=0 if n=0); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 11, 3, 1, 0, 74, 24, 6, 1, 0, 652, 225, 57, 10, 1, 0, 7069, 2489, 678, 141, 17, 1, 0, 90946, 32326, 9375, 2107, 352, 28, 1, 0, 1353554, 483968, 146334, 35568, 6722, 832, 46, 1, 0, 22870541, 8211543, 2555228, 661329, 137225, 21510, 1973, 75, 1

Offset: 0

Alois P. Heinz, Feb 27 2019

T(n,k) is defined for all n,k >= 0. The triangle contains only the terms with 0 <= k <= n. T(n,k) = 0 for k > n.

			Triangle T(n,k) begins:
  1;
  0,       1;
  0,       2,      1;
  0,      11,      3,      1;
  0,      74,     24,      6,     1;
  0,     652,    225,     57,    10,    1;
  0,    7069,   2489,    678,   141,   17,   1;
  0,   90946,  32326,   9375,  2107,  352,  28,  1;
  0, 1353554, 483968, 146334, 35568, 6722, 832, 46, 1;
  ...

Alois P. Heinz, Rows n = 0..19, flattened

Columns k=0-10 give: A000007, A324445, A324446, A324447, A324448, A324449, A324450, A324451, A324452, A324453, A324454.
Row sums give A001147.
Main diagonal gives A000012.
T(n+1,n) gives A001610.
Cf. A293157, A293881, A324428.

b:= proc(n, f, m, l, j) option remember; (k-> `if`(n `if`(n=0 or k<2, doublefactorial(2*n-1),
              b(2*n-k+1, [1$k-1], 0, [0$k-1], k-1)):
T:= (n, k)-> `if`(n=k, 1, A(n, k)-A(n, k+1)):
seq(seq(T(n, k), k=0..n), n=0..10);

b[n_, f_List, m_, l_List, j_] := b[n, f, m, l, j] = Function[k, If[n < Total[f] + m +  Total[l], 0, If[n == 0, 1, Sum[If[f[[i]] == 0, 0, b[n - 1, ReplacePart[f, i -> 0], m + l[[1]], Append[ReplacePart[l, 1 -> Nothing], 0], Max[0, j - 1]]], {i, Max[1, j + 1], Min[k, n - 1]}] + If[m == 0, 0, m*b[n - 1, f, m - 1 + l[[1]], Append[ReplacePart[l, 1 -> Nothing], 0], Max[0, j-1]]] + b[n-1, f, m + l[[1]], Append[ReplacePart[ l, 1 -> Nothing], 1], Max[0, j - 1]]]]][Length[l]];
A[n_, k_] := If[n == 0 || k < 2, 2^(n-1) Pochhammer[3/2, n-1], b[2n-k+1, Table[1, {k - 1}], 0, Table[0, {k - 1}], k - 1]];
T[n_, k_] := If[n == k, 1, A[n, k] - A[n, k + 1]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 27 2020, after Alois P. Heinz *)

T(n,k) = A324428(n,k) - A324428(n,k+1) for k > 0, T(n,0) = A000007(n).

A306386 Number of chord diagrams with n chords all having arc length at least 3.

Original entry on oeis.org

1, 0, 0, 1, 7, 68, 837, 11863, 189503, 3377341, 66564396, 1439304777, 33902511983, 864514417843, 23735220814661, 698226455579492, 21914096529153695, 731009183350476805, 25829581529376423945, 963786767538027630275, 37871891147795243899204, 1563295398737378236910447

Offset: 0

Gus Wiseman, Feb 26 2019

nonn

A cyclical form of A190823.

Also the number of 2-uniform set partitions of {1...2n} such that, when the vertices are arranged uniformly around a circle, no block has its two vertices separated by an arc length of less than 3.

			The a(8) = 7 2-uniform set partitions with all arc lengths at least 3:
  {{1,4},{2,6},{3,7},{5,8}}
  {{1,4},{2,7},{3,6},{5,8}}
  {{1,5},{2,6},{3,7},{4,8}}
  {{1,5},{2,6},{3,8},{4,7}}
  {{1,5},{2,7},{3,6},{4,8}}
  {{1,6},{2,5},{3,7},{4,8}}
  {{1,6},{2,5},{3,8},{4,7}}

Alois P. Heinz, Table of n, a(n) for n = 0..404
Gus Wiseman, The a(5) = 68 chord diagrams with all arc lengths at least 3.

Cf. A000296, A000699, A001006, A001147, A001610, A003436, A038041, A054726, A135042, A170941, A190823, A278990, A306419, A322402, A324011, A324169.

Column k=3 of A324428.

a:= proc(n) option remember; `if`(n<8, [1, 0$2, 1, 7, 68, 837, 11863][n+1],
      ((8*n^4-64*n^3+142*n^2-66*n+109)    *a(n-1)
      -(24*n^4-248*n^3+870*n^2-1106*n+241)*a(n-2)
      +(24*n^4-264*n^3+982*n^2-1270*n+145)*a(n-3)
      -(8*n^4-96*n^3+374*n^2-486*n+33)    *a(n-4)
      -(4*n^3-24*n^2+39*n-2)              *a(n-5))/(4*n^3-36*n^2+99*n-69))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 27 2019

dtui[{},]:={{}};dtui[set:{i,___},n_]:=Join@@Function[s,Prepend[#,s]&/@dtui[Complement[set,s],n]]/@Table[{i,j},{j,Switch[i,1,Select[set,3<#i+2&]]}];
Table[Length[dtui[Range[n],n]],{n,0,12,2}]

a(n) is even <=> n in { A135042 }. - Alois P. Heinz, Feb 27 2019

a(10)-a(16) from Alois P. Heinz, Feb 26 2019

a(17)-a(21) from Alois P. Heinz, Feb 27 2019

A324430 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least four.

Original entry on oeis.org

1, 0, 0, 0, 1, 11, 159, 2488, 43169, 822113, 17066007, 384422661, 9357185385, 245099146171, 6881055868664, 206270437643247, 6578921849694561, 222533460191360229, 7959059236941486231, 300168498172776752829, 11907361524870216908385, 495692886834636282431752

Offset: 0

Alois P. Heinz, Feb 27 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..404

Column k=4 of A324428.

A324431 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least five.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 18, 381, 7601, 160784, 3621067, 87089383, 2235081950, 61129825519, 1778536033055, 54930050817476, 1796853497380257, 62110926582550043, 2263534922105574576, 86779223311878261139, 3492564794206986891273, 147269976213917444452508

Offset: 0

Alois P. Heinz, Feb 27 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..404

Column k=5 of A324428.

A324432 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least six.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 29, 879, 23559, 607897, 16179520, 449286927, 13098525681, 401675273973, 12961858610835, 439969542845247, 15694595867800757, 587665598756534677, 23065866584266238427, 947631130543961813887, 40691002929409496892633, 1823524185613956274776800

Offset: 0

Alois P. Heinz, Feb 27 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..200

Column k=6 of A324428.

A324433 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least seven.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 47, 2049, 72989, 2320389, 72984903, 2340136832, 77373758909, 2655913191455, 94925974424159, 3537409377070327, 137498256564370813, 5573810976335976071, 235519207528086247775, 10365638931006805924491, 474762601555480759969273

Offset: 0

Alois P. Heinz, Feb 27 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..150

Column k=7 of A324428.

A324434 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least eight.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 1, 76, 4788, 221917, 8887710, 331432067, 12269388935, 460168784128, 17665933357441, 698638441294365, 28556568958525122, 1208570048233111199, 53007713800631794460, 2410148120774836584364, 113594056221675357350279, 5547970208256475164372741

Offset: 0

Alois P. Heinz, Feb 27 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..97

Column k=8 of A324428.

A324435 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least nine.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 123, 11179, 678033, 33920411, 1510561303, 64644980613, 2750055687841, 118100969286656, 5165550855166131, 231446409801491355, 10658817807766612225, 505538573513456703833, 24722367556570294858207, 1247328697401969440599017

Offset: 0

Alois P. Heinz, Feb 27 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..50

Column k=9 of A324428.

A324436 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least ten.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 199, 26071, 2076337, 128036597, 6885473559, 341688260735, 16496710343843, 792460210118481, 38341661821182976, 1882679817632403839, 94308395144305086977, 4834964742446401521057, 254210075409129027824513

Offset: 0

Alois P. Heinz, Feb 27 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..30

Column k=10 of A324428.

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

A324429 Number T(n,k) of labeled cyclic chord diagrams having n chords and minimal chord length k (or k=0 if n=0); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A306386 Number of chord diagrams with n chords all having arc length at least 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A324430 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least four.

Views

Author

Keywords

Links

Crossrefs

A324431 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least five.

Views

Author

Keywords

Links

Crossrefs

A324432 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least six.

Views

Author

Keywords

Links

Crossrefs

A324433 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least seven.

Views

Author

Keywords

Links

Crossrefs

A324434 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least eight.

Views

Author

Keywords

Links

Crossrefs

A324435 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least nine.

Views

Author

Keywords

Links

Crossrefs

A324436 Number of labeled cyclic chord diagrams with n chords such that every chord has length at least ten.

Views

Author

Keywords

Links