A003436 -id:A003436 - cp's OEIS frontend

A348813 a(n) = number of chord labeled loopless diagrams by number of K_3.

0, 1, 22, 1415, 140343, 20167651, 3980871156, 1035707510307, 343866839138005, 141979144588872613, 71386289535825383386, 42954342000612934599071, 30482693813120122213093587, 25196997894058490607106028095, 24001522306527907199721466108488, 26102037346800387738363882455862531

Offset: 1

Michael De Vlieger, Nov 01 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
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 2.

Row 3 of A369923.

Cf. A190826, A348814, A292409; A003436, A348815, A348818, A348821.

a(14) onwards from Andrew Howroyd, Feb 05 2024

A348818 a(n) = number of chord labeled loopless diagrams by number of K_5.

Original entry on oeis.org

0, 1, 866, 4446741, 55279816356, 1450728060971387, 72078730629785795963, 6235048155225093080061949, 879601407931825739964190440635, 192100729970218737700046212217095291, 62258393664270652226502315136978421947948, 28913744296806659870889046765907226809528931041

Offset: 1

Michael De Vlieger, Nov 01 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
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.

Row 5 of A369923.

Cf. A190833, A348819, A348820; A003436, A348813, A348815, A348821.

a(9) onwards from Andrew Howroyd, Feb 05 2024

A348821 a(n) = number of chord labeled loopless diagrams by number of K_6.

Original entry on oeis.org

0, 1, 5812, 276154969, 39738077935264, 14571371516350429940, 11876790400066163254723167, 19372051918038657958659363247949, 58256941603805590330534264712744407687, 302616041649108508974263266688425815263488561, 2575195630881373033515248134269171034879932771154311

Offset: 1

Michael De Vlieger, Nov 01 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
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.

Row 6 of A369923.

Cf. A190835, A348822, A348823; A003436, A348813, A348815, A348818.

a(8) onwards from Andrew Howroyd, Feb 05 2024

A190823 Number of permutations of 2 copies of 1..n introduced in order 1..n with no element equal to another within a distance of 2.

Original entry on oeis.org

1, 0, 0, 1, 10, 99, 1146, 15422, 237135, 4106680, 79154927, 1681383864, 39034539488, 983466451011, 26728184505750, 779476074425297, 24281301468714902, 804688068731837874, 28269541494090294129, 1049450257149017422000, 41050171013933837206545

Offset: 0

R. H. Hardin, May 21 2011

From Gus Wiseman, Feb 27 2019: (Start)
Also the number of 2-uniform set partitions of {1..2n} such that no block has its two vertices differing by less than 3. For example, the a(4) = 10 set partitions are:
  {{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,5}, {2,8}, {3,6}, {4,7}}
  {{1,6}, {2,5}, {3,7}, {4,8}}
  {{1,6}, {2,5}, {3,8}, {4,7}}
  {{1,7}, {2,5}, {3,6}, {4,8}}
  {{1,8}, {2,5}, {3,6}, {4,7}}
(End)

			All solutions for n=4 (read downwards):
  1    1    1    1    1    1    1    1    1    1
  2    2    2    2    2    2    2    2    2    2
  3    3    3    3    3    3    3    3    3    3
  4    4    4    4    1    4    4    1    4    4
  1    1    2    1    4    2    1    4    2    2
  3    3    1    2    2    3    2    3    1    3
  2    4    4    4    3    4    3    2    3    1
  4    2    3    3    4    1    4    4    4    4

Alois P. Heinz, Table of n, a(n) for n = 0..404
Dmitry Efimov, Hafnian of two-parameter matrices, arXiv:2101.09722 [math.CO], 2021.
Everett Sullivan, Linear chord diagrams with long chords, arXiv preprint arXiv:1611.02771 [math.CO], 2016.

Distance of 1 instead of 2 gives |A000806|.
Column k=3 of A293157.
Cf. A000699, A001147 (2-uniform set partitions), A003436, A005493, A011968, A170941, A278990 (distance 2+ version), A306386 (cyclical version).

I:=[1,0,0,1,10,99]; [n le 5 select I[n] else 2*n*Self(n-1) -2*(3*n-8)*Self(n-2) +2*(3*n-11)*Self(n-3) -2*(n-5)*Self(n-4) -Self(n-5): n in [1..40]]; // G. C. Greubel, Dec 03 2023

a[0]=1; a[1]=0; a[2]=0; a[3]=1; a[4]=10; a[5]=99; a[n_] := a[n] = (2*n+2) a[n-1] - (6*n-10) a[n-2] + (6*n-16) a[n-3] - (2*n-8) a[n-4] - a[n-5]; Array[a, 20, 0] (* based on Sullivan's formula, Giovanni Resta, Mar 20 2017 *)
dtui[{}]:={{}};dtui[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@dtui[Complement[set,s]]]/@Table[{i,j},{j,Select[set,#>i+2&]}];
Table[Length[dtui[Range[n]]],{n,0,12,2}] (* Gus Wiseman, Feb 27 2019 *)

@CachedFunction
def a(n): # a = A190823
    if (n<6): return (1,0,0,1,10,99)[n]
    else: return 2*(n+1)*a(n-1) - 2*(3*n-5)*a(n-2) + 2*(3*n-8)*a(n-3) - 2*(n-4)*a(n-4) - a(n-5)
[a(n) for n in range(41)] # G. C. Greubel, Dec 03 2023

a(n) = 2*(n+1)*a(n-1) - 2*(3*n-5)*a(n-2) + 2*(3*n-8)*a(n-3) - 2*(n-4)*a(n-4) - a(n-5) (proved). - Everett Sullivan, Mar 16 2017

a(n) ~ 2^(n+1/2) * n^n / exp(n+2), based on Sullivan's formula. - Vaclav Kotesovec, Mar 21 2017

a(16)-a(20) (using Everett Sullivan's formula) from Giovanni Resta, Mar 20 2017

a(0)=1 prepended by 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

A322402 Triangle read by rows: The number of chord diagrams with n chords and k topologically connected components, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 4, 6, 5, 0, 27, 36, 28, 14, 0, 248, 310, 225, 120, 42, 0, 2830, 3396, 2332, 1210, 495, 132, 0, 38232, 44604, 29302, 14560, 6006, 2002, 429, 0, 593859, 678696, 430200, 204540, 81900, 28392, 8008, 1430, 0, 10401712, 11701926, 7204821, 3289296, 1263780, 431256, 129948, 31824, 4862

Offset: 0

R. J. Mathar, Dec 06 2018

If all subsets are allowed instead of just pairs (chords), we get A324173. The rightmost column is A000108 (see Riordan). - Gus Wiseman, Feb 27 2019

			From _Gus Wiseman_, Feb 27 2019: (Start)
Triangle begins:
  1
  0      1
  0      1      2
  0      4      6      5
  0     27     36     28     14
  0    248    310    225    120     42
  0   2830   3396   2332   1210    495    132
  0  38232  44604  29302  14560   6006   2002    429
  0 593859 678696 430200 204540  81900  28392   8008   1430
Row n = 3 counts the following chord diagrams (see link for pictures):
  {{1,3},{2,5},{4,6}}  {{1,2},{3,5},{4,6}}  {{1,2},{3,4},{5,6}}
  {{1,4},{2,5},{3,6}}  {{1,3},{2,4},{5,6}}  {{1,2},{3,6},{4,5}}
  {{1,4},{2,6},{3,5}}  {{1,3},{2,6},{4,5}}  {{1,4},{2,3},{5,6}}
  {{1,5},{2,4},{3,6}}  {{1,5},{2,3},{4,6}}  {{1,6},{2,3},{4,5}}
                       {{1,5},{2,6},{3,4}}  {{1,6},{2,5},{3,4}}
                       {{1,6},{2,4},{3,5}}
(End)

P. Flajolet and M. Noy, Analytic Combinatorics of Chord Diagrams, in: Formal power series and algebraic combinatorics (FPSAC '00) Moscow, 2000, p 191-201, eq (2)
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222. [Annotated scanned copy]
Gus Wiseman, Chords diagrams with 3 chords, organized by number of components.

Cf. A000699 (k = 1 column), A001147 (row sums), A000108 (diagonal), A002694 (subdiagonal k = n - 1).

Cf. A000096, A003436, A016098, A099947, A136653, A278990, A293157, A324173, A324323, A324327, A324328.

The g.f. satisfies g(z,w) = 1+w*A000699(w*g^2), where A000699(z) is the g.f. of A000699.

Offset changed to 0 by Gus Wiseman, Feb 27 2019

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

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

A348813 a(n) = number of chord labeled loopless diagrams by number of K_3.

Views

Author

Keywords

Links

Crossrefs

Extensions

A348818 a(n) = number of chord labeled loopless diagrams by number of K_5.

Views

Author

Keywords

Links

Crossrefs

Extensions

A348821 a(n) = number of chord labeled loopless diagrams by number of K_6.

Views

Author

Keywords

Links

Crossrefs

Extensions

A190823 Number of permutations of 2 copies of 1..n introduced in order 1..n with no element equal to another within a distance of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

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

A322402 Triangle read by rows: The number of chord diagrams with n chords and k topologically connected components, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs