A006184 -id:A006184 - cp's OEIS frontend

A242522 Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is at least 2.

0, 0, 0, 0, 1, 5, 33, 245, 2053, 19137, 196705, 2212037, 27029085, 356723177, 5058388153, 76712450925, 1239124984693, 21241164552785, 385159565775633, 7365975246680597, 148182892455224845, 3128251523599365177, 69149857480654157545, 1597343462243140957757

Offset: 1

Stanislav Sykora, May 27 2014

nonn

a(n)=NPC(n;S;P) is the count of all neighbor-property cycles for a specific set S of n elements and a specific pair-property P. For more details, see the link and A242519.
Number of Hamiltonian cycles in the complement of P_n, where P_n is the n-path graph. - Andrew Howroyd, Mar 15 2016
a(n) also agrees with the number of optimal fundamentally distinct radio labelings of the wheel graph on (n+1) nodes for n = 5 up to at least n = 10 (and likely all larger n). - Eric W. Weisstein, Jan 12 2021
a(n) also agrees with the number of optimal fundamentally distinct radio labelings of the n-dipyramidal graph for n = 5 up to at least n = 9 (and likely all larger n). - Eric W. Weisstein, Jan 14 2021

			The 5 cycles of length n=6 having this property are {1,3,5,2,4,6}, {1,3,5,2,6,4}, {1,3,6,4,2,5}, {1,4,2,5,3,6}, {1,4,2,6,3,5}.

Andrew Woods, Table of n, a(n) for n = 1..100 (terms up to a(24) from _Hiroaki Yamanouchi_, Aug 28 2014)
F. C. Holroyd and W. J. G. Wingate, Cycles in the complement of a tree or other graph, Discrete Math., 55 (1985), 267-282.
S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.
Eric Weisstein's World of Mathematics, Dipyramidal Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Path Complement Graph
Eric Weisstein's World of Mathematics, Radio Labeling
Eric Weisstein's World of Mathematics, Wheel Graph

Cf. A242519, A242520, A242521, A242523, A242524, A242525, A242526, A242527, A242528, A242529, A242530, A242531, A242532, A242533, A242534.

Cf. A006184.

a[n_ /; n < 5] = 0; a[5] = 1; a[6] = 5; a[n_] := a[n] = n a[n - 1] - (n - 5) a[n - 2] - (n - 4) a[n - 3] + (n - 4) a[n - 4]; Array[a, 24] (* Jean-François Alcover, Oct 07 2017 *)
Join[{0, 0}, RecurrenceTable[{a[n] == n a[n - 1] - (n - 5) a[n - 2] - (n - 4) a[n - 3] + (n - 4) a[n - 4], a[3] == a[4] == 0, a[5] == 1, a[6] == 5}, a, {n, 20}]] (* Eric W. Weisstein, Apr 12 2018 *)

a(n) = A002493(n)/(2*n), n>1. - Andrew Woods, Dec 08 2014
a(n) = Sum_{k=1..n} (-1)^(n-k)*k!*A102413(n,k) / (2*n), n>2. - Andrew Woods after Vladeta Jovovic, Dec 08 2014
a(n) = (n-1)!/2 + sum_{i=1..n-1} ((-1)^i * (n-i-1)! * sum_{j=0..i-1} (2^j * C(i-1,j) * C(n-i,j+1))), for n>=5. - Andrew Woods, Jan 08 2015
a(n) = n a(n-1) - (n-5) a(n-2) - (n-4) a(n-3) + (n-4) a(n-4), for n>6. - Jean-François Alcover, Oct 07 2017

A002816 Number of polygons that can be formed from n points on a circle, no two adjacent.

Original entry on oeis.org

1, 0, 0, 0, 1, 3, 23, 177, 1553, 14963, 157931, 1814453, 22566237, 302267423, 4340478951, 66541218865, 1084982173641, 18752743351339, 342523093859011, 6593167693927885, 133408305489947029, 2831112931136162775, 62878579846490149375, 1458746608689369440265

Offset: 1

N. J. A. Sloane

Also number of ways of arranging the numbers 1..n in a circle so that adjacent numbers do not differ by 1 mod n. Reversing the direction around the circle does not count as a different solution (cf. A078603).
Also number of ways of seating n people around a circular table so that no one sits next to any of his neighbors in a previous seating order.
Suppose n people are seated at random around a circular table for two meals. Then p(n) = a(n)/((n-1)!/2) is the probability that no two people sit together at both meals.
Number of Hamiltonian cycles in the complement of C_n where C_n is the n-cycle graph. - Andrew Howroyd, Mar 15 2016

			a(6)=3: 135264, 136425, 142635.

P. Poulet, Reply to Query 4750, Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..100
B. Aspvall and F. M. Liang, The dinner table problem, Technical Report CS-TR-80-829, Computer Science Department, Stanford, California, 1980.
D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.
Eric Weisstein's World of Mathematics, Cycle Complement Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Index entries for sequences related to shoe lacings

Cf. A000179 (Ménage problem), A078603, A078630, A078631, A242522 (Hamiltonian cycles in complement of path), A006184, left column of A326411.

dinner := proc(n) local j,k,sum; sum := (n-1)!/2 + (-1)^n; for k from 1 to n-1 do for j from 1 to min(n-k,k) do sum := sum+(-1)^k*binomial(k-1,j-1)*binomial(n-k,j)*n/(n-k)*(n-k-1)!/2*2^j; od; od; end;

t = {1, 0, 0, 0, 1, 3, 23}; Do[AppendTo[t, ((n^3 - 8*n^2 + 18*n - 21) t[[-1]] + 4*n*(n - 5) t[[-2]] - 2*(n - 6) (n^2 - 5 n + 3) t[[-3]] + (n^2 - 7*n + 9)  t[[-4]] + (n - 5) (n^2 - 5*n + 3) t[[-5]])/(n^2 - 7*n + 9)], {n, 8, 25}]; t (* T. D. Noe, Jan 04 2012 *)
Join[{1, 0}, RecurrenceTable[{a[3] == 0, a[4] == 0, a[5] == 1, a[6] == 3, a[7] == 23, (n^2 - 7 n + 9) a[n] == (n^3 - 8 n^2 + 18 n - 21) a[n - 1] + 4 n (n - 5) a[n - 2] - 2 (n - 6) (n^2 - 5 n + 3) a[n - 3] + (n^2 - 7 n + 9) a[n - 4] + (n - 5) (n^2 - 5 n + 3) a[n - 5]}, a, {n, 3, 20}]] (* Eric W. Weisstein, Feb 26 2021 *)

D-finite with recurrence (n^2 - 7n + 9)a(n) = (n^3 - 8n^2 + 18n - 21)a(n - 1) + 4n(n - 5)a(n - 2) - 2(n - 6)(n^2 - 5n + 3)a(n - 3) + (n^2 - 7n + 9)a(n - 4) + (n - 5)(n^2 - 5n + 3)a(n - 5), for n >= 8. - Poulet.
p(n) = exp(-2)*(1 + O(1/n)). - Aspvall and Liang.
Asymptotic: a(n)/(n-1)! ~ 1/(2*e^2)*(1 - 4/n + 20/(3n^3) + 58/(3n^4) + 796/(15n^5) + 7858/(45n^6) + 40324/(63n^7) + 140194/(63n^8) + 2444744/(405n^9) + 40680494/(14175n^10) + ...). - Vaclav Kotesovec, Apr 10 2012

Entry improved by Michael Steyer (m.steyer(AT)osram.de), Aug 30 2001

More terms from Sascha Kurz, Mar 22 2002

A002493 Number of ways to arrange n non-attacking kings on an n X n board, with 2 sides identified to form a cylinder, with 1 in each row and column.

Original entry on oeis.org

1, 0, 0, 0, 10, 60, 462, 3920, 36954, 382740, 4327510, 53088888, 702756210, 9988248956, 151751644590, 2454798429600, 42130249479562, 764681923900260, 14636063499474054, 294639009867223880

Offset: 1

N. J. A. Sloane

nonn

Number of directed Hamiltonian paths in the complement of C_n where C_n is the n-cycle graph. - Andrew Howroyd, Mar 15 2016

Number of ways of arranging n consecutive integers in a circle such that no pair of adjacent integers differ by 1, rotations are distinct. - Graham Holmes, Sep 03 2020

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 1..100
M. Abramson and W. O. J. Moser, Permutations without rising or falling w-sequences, Ann. Math. Stat., 38 (1967), 1245-1254.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Counting King Permutations on the Cylinder, arXiv:2001.02948 [math.CO], 2020.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 627-8.
A. J. Schwenk, Letter to N. J. A. Sloane, Mar 24 1980 (with enclosure and notes)

Cf. A002464, A002816, A006184.

Right diagonal of A338838.

b1:= proc(n, r) local gu, x; if r=0 then RETURN(0): fi: gu := (x*diff(x*(1+x)/(1-x),x))* (x*(1 + x)/(1 - x))^(r-1); gu := taylor(gu, x = 0, n +1); coeff(gu, x, n ) end: b:=proc(n) local r: if n=1 then 1 elif n=2 then 0 else add((-1)^(n-r)*r!*b1(n,r),r=0..n): fi: end: # Doron Zeilberger, Nov 14 2007

b[n_]:=(If[n>0, n!+Sum[(-1)^r*(n-r)!*Sum[2^c*Binomial[r-1, c-1]*Binomial[n-r,c], {c, 1, r}], {r, 1, n-1}], 0]); Table[If[n>2, b[n]-2*Sum[b[n-1-2k], {k, 0, Floor[n/2]}], If[n==1, 1, 0]], {n, 1, 25}] (* Vaclav Kotesovec after Vladeta Jovovic, Apr 06 2012 *)

The linear recurrence operator annihilating this sequence is (N is the shift operator Na(n):=a(n + 1)) is - 3*(43*n + 197)*(n - 2)*(n + 1)/( - 1222 + 753*n + 349*n^2) - 5*(n - 1)*(44*n^2 + 477*n + 1222)/( - 1222 + 753*n + 349*n^2)*N + 2*(n + 1)*(239*n^2 + 873*n - 1232)/( - 1222 + 753*n + 349*n^2)*N^2 + 4*(394 - 259*n + 215*n^2 + 55*n^3)/( - 1222 + 753*n + 349*n^2)*N^3 - ( - 7342 + 3699*n + 2718*n^2 + 349*n^3)/( - 1222 + 753*n + 349*n^2)*N^4 + N^5. - Doron Zeilberger, Nov 14 2007
a(n) = Sum((-1)^(n-k)*k!*A102413(n,k),k=1..n), n>2. - Vladeta Jovovic, Nov 23 2007
a(n) = b(n+1) - 2*Sum_{k=0..floor(n/2)} b(n-2*k) for n>1, where b(n)=A002464(n) if n>0 else b(0)=0. - Vladeta Jovovic, Nov 24 2007
Asymptotic: a(n) ~ n!/e^2*(1 - 2/n - 2/n^2 - 4/(3n^3) + 8/(3n^4) + 326/(15n^5) + 4834/(45n^6) + 154258/(315n^7) + 232564/(105n^8) + ...). - Vaclav Kotesovec, Apr 06 2012
a(n) = n! + Sum_{i=1..n-1} ((-1)^i * (n-i-1)! * n * Sum_{j=0..i-1} (2^(j+1) * C(i-1,j) * C(n-i,j+1))), for n>=5. - Andrew Woods, Jan 08 2015

A302734 Number of paths in the n-path complement graph.

Original entry on oeis.org

0, 0, 1, 6, 32, 186, 1245, 9588, 83752, 817980, 8827745, 104277450, 1337781336, 18518728326, 275087536717, 4364152920456, 73637731186160, 1316713607842968, 24869730218182497, 494752411594456110, 10339913354716379440, 226485946787802241650, 5188447062121251600221

Offset: 1

Eric W. Weisstein, Apr 12 2018

nonn

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

Cf. A001266, A006184, A242522.

Array[(1/2) Sum[Sum[Sum[(-1)^(k - i) i!*2^j*Binomial[# + i - k, i] Binomial[i, j] Binomial[k - i - 1, k - i - j], {j, 0, k - i}], {i, k}], {k, 2, #}] &, 23] (* Michael De Vlieger, Apr 21 2018 *)
Table[Sum[(-1)^(k - i) i! 2^j Binomial[n + i - k, i] Binomial[i, j] Binomial[k - i - 1, k - i - j], {k, 2, n}, {i, k}, {j, 0, k - i}]/2, {n, 20}] (* Eric W. Weisstein, Apr 23 2018 *)

a(n)={sum(k=2, n, sum(i=1, k, sum(j=0, min(i, k-i), (-1)^(k-i)*i!*2^j*binomial(n+i-k, i)*binomial(i, j)*binomial(k-i-1, k-i-j))))/2} \\ Andrew Howroyd, Apr 21 2018

a(n) = (1/2)*Sum_{k=2..n} Sum_{i=1..k} Sum_{j=0..k-i} (-1)^(k-i)*i!*2^j*binomial(n+i-k, i)*binomial(i, j)*binomial(k-i-1, k-i-j). - Andrew Howroyd, Apr 21 2018

a(n) ~ n! / (2*exp(1)). - Vaclav Kotesovec, Apr 22 2018

Terms a(15) and beyond from Andrew Howroyd, Apr 21 2018

A375619 a(n) is the largest integer such that there exists a simple graph with n vertices, a(n) edges, and no cycles of length 0 mod 4.

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 9, 11, 12, 14, 15, 17, 19, 20, 22, 23, 25, 26, 28, 30, 31, 33, 34, 36, 38, 39, 41, 42, 44, 45, 47, 49, 50, 52, 53, 55, 57, 58, 60, 61, 63, 64, 66, 68, 69, 71, 72, 74, 76, 77, 79, 80, 82, 83, 85, 87, 88, 90, 91, 93, 95, 96, 98, 99, 101, 102

Offset: 1

Luc Ta, Aug 21 2024

In the parlance of extremal graph theory, a(n) is the extremal number ex(n, C_(0 mod 4)).

			For n = 4, any simple graph with 4 vertices and 5 edges contains a cycle of length 4 == 0 (mod 4), so a(4) < 5. There are exactly two nonisomorphic graphs with 4 vertices and 4 edges. One of them has no cycles of any length other than 3, so a(4) = 4.

Luc Ta, Table of n, a(n) for n = 1..10000
Ervin Győri, Binlong Li, Nika Salia, Casey Tompkins, Kitti Varga, and Manran Zhu, On graphs without cycles of length 0 modulo 4, arXiv: 2312.09999 [math.CO], 2023.
Index entries for sequences related to graphs

Cf. A172272, A056576, A006855, A000066, A345248, A006184.

Mathematica
```
Table[Floor[19/12 * (n - 1)], {n, 100}]
```

a(n) = floor(19/12(n-1)). See Győri et al. in Links.
a(n) = A172272(n-1) for all n <= 77; then a(78) = 121 != 122 = A172272(77).
a(n) = A056576(n-1) for all n <= 53; then a(54) = 83 != 84 = A056576(53).

cp's OEIS Frontend

A242522 Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is at least 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A002816 Number of polygons that can be formed from n points on a circle, no two adjacent.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A002493 Number of ways to arrange n non-attacking kings on an n X n board, with 2 sides identified to form a cylinder, with 1 in each row and column.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A302734 Number of paths in the n-path complement graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A375619 a(n) is the largest integer such that there exists a simple graph with n vertices, a(n) edges, and no cycles of length 0 mod 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula