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

A278990 Number of loopless linear chord diagrams with n chords.

Original entry on oeis.org

1, 0, 1, 5, 36, 329, 3655, 47844, 721315, 12310199, 234615096, 4939227215, 113836841041, 2850860253240, 77087063678521, 2238375706930349, 69466733978519340, 2294640596998068569, 80381887628910919255, 2976424482866702081004, 116160936719430292078411

Offset: 0

N. J. A. Sloane, Dec 07 2016

nonn

See the signed version of these numbers, A000806, for much more information about these numbers.
From Gus Wiseman, Feb 27 2019: (Start)
Also the number of 2-uniform set partitions of {1..2n} containing no two successive vertices in the same block. For example, the a(3) = 5 set partitions are:
  {{1,3},{2,5},{4,6}}
  {{1,4},{2,5},{3,6}}
  {{1,4},{2,6},{3,5}}
  {{1,5},{2,4},{3,6}}
  {{1,6},{2,4},{3,5}}
(End)
From Gus Wiseman, Jul 05 2020: (Start)
Also the number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal and where the first i appears before the first j for i < j. For example, the a(3) = 5 permutations are the following.
  (1,2,3,1,2,3)
  (1,2,3,1,3,2)
  (1,2,3,2,1,3)
  (1,2,3,2,3,1)
  (1,2,1,3,2,3)
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..404 (terms 0..200 from Gheorghe Coserea)
Dmitry Efimov, The hafnian of Toeplitz matrices of a special type, perfect matchings and Bessel polynomials, arXiv:1904.08651 [math.CO], 2019.
H. Eriksson and A. Martin, Enumeration of Carlitz multipermutations, arXiv:1702.04177 [math.CO], 2017.
E. Krasko, I. Labutin, and A. Omelchenko, Enumeration of labelled and unlabelled Hamiltonian Cycles in complete k-partite graphs, arXiv:1709.03218 [math.CO], 2017, Table 1.
E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, 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.
Gus Wiseman, The a(4) = 36 loopless linear chord diagrams.
Donovan Young, Counting Bubbles in Linear Chord Diagrams, arXiv:2311.01569 [math.CO], 2023.
Donovan Young, Bubbles in Linear Chord Diagrams: Bridges and Crystallized Diagrams, arXiv:2408.17232 [math.CO], 2024.

Column k=0 of A079267.
Column k=2 of A293157.
Row n=2 of A322013.
Cf. A000110, A000699 (topologically connected 2-uniform), A000806, A001147 (2-uniform), A003436 (cyclical version), A005493, A170941, A190823 (distance 3+ version), A322402, A324011, A324172.
Anti-run compositions are A003242.
Separable partitions are A325534.
Cf. A007716, A292884, A333489.
Other sequences involving the multiset {1,1,2,2,...,n,n}: A001147, A007717, A020555, A094574, A316972.

[n le 2 select 2-n else (2*n-3)*Self(n-1) + Self(n-2): n in [1..30]]; // G. C. Greubel, Sep 26 2023

RecurrenceTable[{a[n]== (2n-1)a[n-1] +a[n-2], a[0]==1, a[1]==0}, a, {n,0,20}] (* Vaclav Kotesovec, Sep 15 2017 *)
FullSimplify[Table[-I*(BesselI[1/2+n,-1] BesselK[3/2,1] - BesselI[3/2,-1] BesselK[1/2+ n,1]), {n,0,20}]] (* Vaclav Kotesovec, Sep 15 2017 *)
Table[(2 n-1)!! Hypergeometric1F1[-n,-2 n,-2], {n,0,20}] (* Eric W. Weisstein, Nov 14 2018 *)
Table[Sqrt[2/Pi]/E ((-1)^n Pi BesselI[1/2+n,1] +BesselK[1/2+n,1]), {n,0,20}] // FunctionExpand // FullSimplify (* Eric W. Weisstein, Nov 14 2018 *)
twouniflin[{}]:={{}};twouniflin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@twouniflin[Complement[set,s]]]/@Table[{i,j},{j,Select[set,#>i+1&]}];
Table[Length[twouniflin[Range[n]]],{n,0,14,2}] (* Gus Wiseman, Feb 27 2019 *)

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

def A278990_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( exp(-1+sqrt(1-2*x))/sqrt(1-2*x) ).egf_to_ogf().list()
A278990_list(30) # G. C. Greubel, Sep 26 2023

From Gheorghe Coserea, Dec 09 2016: (Start)
D-finite with recurrence a(n) = (2*n-1)*a(n-1) + a(n-2), with a(0) = 1, a(1) = 0.
E.g.f. y satisfies: 0 = (1-2*x)*y'' - 3*y' - y.
a(n) - a(n-1) = A003436(n) for all n >= 2. (End)
From Vaclav Kotesovec, Sep 15 2017: (Start)
a(n) = sqrt(2)*exp(-1)*(BesselK(1/2 + n, 1)/sqrt(Pi) - i*sqrt(Pi)*BesselI(1/2 + n, -1)), where i is the imaginary unit.
a(n) ~ 2^(n+1/2) * n^n  / exp(n+1). (End)
a(n) = A114938(n)/n! - Gus Wiseman, Jul 05 2020 (from Alexander Burstein's formula at A114938).
From G. C. Greubel, Sep 26 2023: (Start)
a(n) = (-1)^n * (i/e)*Sqrt(2/Pi) * BesselK(n + 1/2, -1).
G.f.: sqrt(Pi/(2*x)) * exp(-(1+x)^2/(2*x)) * Erfi((1+x)/sqrt(2*x)).
E.g.f.: exp(-1 + sqrt(1-2*x))/sqrt(1-2*x). (End)

a(0)=1 prepended by Gheorghe Coserea, Dec 09 2016

A293157 Triangle read by rows: T(n,k) = number of linear chord diagrams with n chords such that every chord has length at least k (1 <= k <= n).

Original entry on oeis.org

1, 3, 1, 15, 5, 1, 105, 36, 10, 1, 945, 329, 99, 20, 1, 10395, 3655, 1146, 292, 40, 1, 135135, 47844, 15422, 4317, 876, 80, 1, 2027025, 721315, 237135, 69862, 16924, 2628, 160, 1, 34459425, 12310199, 4106680, 1251584, 332507, 67404, 7884, 320, 1, 654729075, 234615096, 79154927, 24728326, 6944594, 1627252, 269616, 23652, 640, 1

Offset: 1

N. J. A. Sloane, Oct 10 2017

There is a surprising change in notation in Sullivan (2016) between Definition 1 and Table 1.

The first 11 columns are given in the reference.

			Triangle begins:
      1;
      3,    1;
     15,    5,    1;
    105,   36,   10,    1;
    945,  329,   99,   20,    1;
  10395, 3655, 1146,  292,   40,    1;
  ...

Everett Sullivan, Linear chord diagrams with long chords, arXiv preprint arXiv:1611.02771 [math.CO], 2016.

Cf. A000806, A001147, A190823, A190824, A190825, A020714, A278990, A293156, A293881.

More terms from Alois P. Heinz, Oct 17 2017

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

A265373 T(n,k)=Number of nXk arrays containing k copies of 0..n-1 with no equal horizontal, vertical or antidiagonal neighbors and new values introduced sequentially from 0.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 10, 1, 0, 0, 1, 32, 99, 1, 0, 0, 1, 236, 4954, 1146, 1, 0, 0, 1, 1238, 363850, 878953, 15422, 1, 0, 0, 1, 7968, 25964546, 860077644, 192333677, 237135, 1, 0, 0, 1, 49214, 2006263350, 919241950442, 3040856393843, 53404173562

Offset: 1

R. H. Hardin, Dec 07 2015

Table starts
.1.......0...........0.............0............0..........0............0
.1.......0...........0.............0............0..........0............0
.1.......1...........1.............1............1..........1............1
.1......10..........32...........236.........1238.......7968........49214
.1......99........4954........363850.....25964546.2006263350.159927435847
.1....1146......878953.....860077644.919241950442
.1...15422...192333677.3040856393843
.1..237135.53404173562
.1.4106680
.1

			Some solutions for n=4 k=4
..0..1..2..0....0..1..2..3....0..1..2..0....0..1..2..3....0..1..2..1
..2..3..1..3....3..0..1..2....3..0..3..2....2..3..0..2....2..0..3..2
..0..2..0..2....1..3..0..1....1..2..1..3....1..2..1..0....3..1..0..3
..1..3..1..3....0..2..3..2....3..0..2..1....3..0..3..1....0..3..1..2

R. H. Hardin, Table of n, a(n) for n = 1..60

Column 2 is A190823.

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

A278990 Number of loopless linear chord diagrams with n chords.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A293157 Triangle read by rows: T(n,k) = number of linear chord diagrams with n chords such that every chord has length at least k (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

A265373 T(n,k)=Number of nXk arrays containing k copies of 0..n-1 with no equal horizontal, vertical or antidiagonal neighbors and new values introduced sequentially from 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs