cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 15 results. Next

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

Original entry on oeis.org

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

Views

Author

Stanislav Sykora, May 27 2014

Keywords

Comments

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

Examples

			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}.

Links

Crossrefs

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

Programs

  • Mathematica
    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 *)

Formula

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

A242527 Number of cyclic arrangements (up to direction) of {0,1,...,n-1} such that the sum of any two neighbors is a prime.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 2, 6, 6, 22, 80, 504, 840, 6048, 3888, 37524, 72976, 961776, 661016, 11533030, 7544366, 133552142, 208815294, 5469236592, 6429567323, 153819905698, 182409170334, 4874589558919, 7508950009102, 209534365631599
Offset: 1

Views

Author

Stanislav Sykora, May 30 2014

Keywords

Comments

a(n)=NPC(n;S;P) is the count of all neighbor-property cycles for a specific set S={0,1,...,n-1} of n elements and a specific pair-property P. For more details, see the link and A242519.
For the same pair-property P but the set {1 through n}, see A051252. Using for pair-property the difference, rather than the sum, one obtains A228626.

Examples

			The first such cycle is of length n=5: {0,2,1,4,3}.
The first case with 2 solutions is for cycle length n=7:
C_1={0,2,3,4,1,6,5}, C_2={0,2,5,6,1,4,3}.
The first and the last of the 22 such cycles of length n=10 are:
C_1={0,3,2,1,4,9,8,5,6,7}, C_22={0,5,8,9,4,3,2,1,6,7}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242527[n_] := Count[Map[lpf, Map[j0f, Permutations[Range[n - 1]]]], 0]/2;
j0f[x_] := Join[{0}, x, {0}];
lpf[x_] := Length[Select[asf[x], ! PrimeQ[#] &]];
asf[x_] := Module[{i}, Table[x[[i]] + x[[i + 1]], {i, Length[x] - 1}]];
Table[A242527[n], {n, 1, 10}]
(* OR, a less simple, but more efficient implementation. *)
A242527[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[PrimeQ[First[perm] + Last[perm]], ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[! PrimeQ[Last[perm] + new], Continue[]];
      A242527[n, Join[perm, {new}],
       Complement[Range[n - 1], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Table[ct = 0; A242527[n, {0}, Range[n - 1]]/2, {n, 1, 15}]
(* Robert Price, Oct 18 2018 *)

Extensions

a(23)-a(30) from Max Alekseyev, Jul 09 2014

A242528 Number of cyclic arrangements of {0,1,...,n-1} such that both the difference and the sum of any two neighbors are prime.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 18, 13, 62, 8, 133, 225, 209, 32, 2644, 4462, 61341, 113986, 750294, 176301, 7575912, 3575686, 7705362, 36777080, 108638048, 97295807
Offset: 1

Views

Author

Stanislav Sykora, May 30 2014

Keywords

Comments

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.
In this case the set is S={0 through n-1}. For the same pair-property P but the set S={1 through n}, see A227050.

Examples

			For n=12 (the first n for which a(n)>0) there are two such cycles:
C_1={0, 5, 2, 9, 4, 1, 6, 11, 8, 3, 10, 7},
C_2={0, 7, 10, 3, 8, 5, 2, 9, 4, 1, 6, 11}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242528[n_] :=
Count[Map[lpf, Map[j0f, Permutations[Range[n - 1]]]], 0]/2;
j0f[x_] := Join[{0}, x, {0}];
lpf[x_] := Length[
   Join[Select[asf[x], ! PrimeQ[#] &],
    Select[Differences[x], ! PrimeQ[#] &]]];
asf[x_] := Module[{i}, Table[x[[i]] + x[[i + 1]], {i, Length[x] - 1}]];
Table[A242528[n], {n, 1, 8}]
(* OR, a less simple, but more efficient implementation. *)
A242528[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[PrimeQ[First[perm] - Last[perm]] &&
       PrimeQ[First[perm] + Last[perm]], ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[! (PrimeQ[Last[perm] - new] && PrimeQ[Last[perm] + new]),
       Continue[]];
      A242528[n, Join[perm, {new}],
       Complement[Range[n - 1], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Table[ct = 0; A242528[n, {0}, Range[n - 1]]/2, {n, 1, 18}]
(* Robert Price, Oct 22 2018 *)

Extensions

a(29)-a(33) from Fausto A. C. Cariboni, May 20 2017

A242519 Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is 2^k for some k=0,1,2,...

Original entry on oeis.org

0, 1, 1, 1, 4, 8, 14, 32, 142, 426, 1204, 3747, 9374, 26306, 77700, 219877, 1169656, 4736264, 17360564, 69631372, 242754286, 891384309, 3412857926, 12836957200, 42721475348, 152125749587, 549831594988
Offset: 1

Views

Author

Stanislav Sykora, May 27 2014

Keywords

Comments

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. Evaluating this sequence for n>=3 is equivalent to counting Hamiltonian cycles in a pair-property graph with n vertices and is often quite hard. For more details, see the link.

Examples

			The four such cycles of length 5 are:
C_1={1,2,3,4,5}, C_2={1,2,4,3,5}, C_3={1,2,4,5,3}, C_4={1,3,2,4,5}.
The first and the last of the 426 such cycles of length 10 are:
C_1={1,2,3,4,5,6,7,8,10,9}, C_426={1,5,7,8,6,4,3,2,10,9}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242519[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[Abs[Differences[x]], ! MemberQ[t, #] &]];
t = Table[2^k, {k, 0, 10}];
Join[{0, 1}, Table[A242519[n], {n, 3, 10}]]
(* OR, a less simple, but more efficient implementation. *)
A242519[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[MemberQ[t, Abs[First[perm] - Last[perm]]], ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[! MemberQ[t, Abs[Last[perm] - new]], Continue[]];
      A242519[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
t = Table[2^k, {k, 0, 10}];
Join[{0, 1}, Table[ct = 0; A242519[n, {1}, Range[2, n]]/2, {n, 3, 12}]] (* Robert Price, Oct 22 2018 *)

Formula

For any S and any P, and for n>=3, NPC(n;S;P)<=A001710(n-1).

Extensions

a(22)-a(27) from Hiroaki Yamanouchi, Aug 29 2014

A242520 Number of cyclic arrangements of S={1,2,...,2n} such that the difference between any two neighbors is 3^k for some k=0,1,2,...

Original entry on oeis.org

1, 1, 2, 3, 27, 165, 676, 3584, 19108, 80754, 386776, 1807342, 8218582, 114618650, 1410831012, 12144300991, 126350575684
Offset: 1

Views

Author

Stanislav Sykora, May 27 2014

Keywords

Comments

a(n)=NPC(2n;S;P) is the count of all neighbor-property cycles for a specific set S of 2n elements and a specific pair-property P. For more details, see the link and A242519.
In this particular instance of NPC(n;S;P), all the terms with odd cycle lengths are necessarily zero.

Examples

			The two such cycles of length n=6 are:
C_1={1,2,3,6,5,4}, C_2={1,2,5,6,3,4}.
The first and last of the 27 such cycles of length n=10 are:
C_1={1,2,3,4,5,6,7,8,9,10}, C_27={1,4,7,8,5,2,3,6,9,10}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242520[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, 2 n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[Abs[Differences[x]], ! MemberQ[t, #] &]];
t = Table[3^k, {k, 0, 10}];
Join[{1}, Table[A242520[n], {n, 2, 5}]]
(* OR, a less simple, but more efficient implementation. *)
A242520[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[MemberQ[t, Abs[First[perm] - Last[perm]]], ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[! MemberQ[t, Abs[Last[perm] - new]], Continue[]];
      A242520[n, Join[perm, {new}],
       Complement[Range[2, 2 n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
t = Table[3^k, {k, 0, 10}];
Join[{1}, Table[ct = 0; A242520[n, {1}, Range[2, 2 n]]/2, {n, 2, 8}]] (* Robert Price, Oct 22 2018 *)

Extensions

a(14)-a(17) from Andrew Howroyd, Apr 05 2016

A242521 Number of cyclic arrangements (up to direction) of {1,2,...,n} such that the difference between any two neighbors is b^k for some b>1 and k>1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 4, 6, 9, 42, 231, 1052, 3818, 10086, 27892, 90076, 310301, 993680, 4663558, 22038882, 162588454, 1246422151, 8655752023, 58951670318, 347675502245
Offset: 1

Views

Author

Stanislav Sykora, May 27 2014

Keywords

Comments

a(n)=NPC(n;S;P) is the count of all neighbor-property cycles for a specific set S={1,2,...,n} of n elements and a specific pair-property P. For more details, see the link and A242519.

Examples

			The two cycles of length n=13 (the smallest n such that a(n)>0) are: C_1={1,5,9,13,4,8,12,3,7,11,2,6,10}, C_2={1,9,5,13,4,8,12,3,7,11,2,6,10}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242521[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[Abs[Differences[x]], ! MemberQ[t, #] &]];
t = Flatten[Table[b^k, {k, 2, 5}, {b, 2, 5}]];
Table[A242521[n], {n, 1, 10}]
(* OR, a less simple, but more efficient implementation. *)
A242521[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[MemberQ[t, Abs[First[perm] - Last[perm]]], ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[! MemberQ[t, Abs[Last[perm] - new]], Continue[]];
      A242521[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
t = Flatten[Table[b^k, {k, 2, 5}, {b, 2, 5}]];
Table[ct = 0; A242521[n, {1}, Range[2, n]]/2, {n, 1, 18}] (* Robert Price, Oct 24 2018 *)

Extensions

a(27)-a(30) from Max Alekseyev, Jul 12 2014
a(31)-a(32) from Fausto A. C. Cariboni, May 17 2017, May 24 2017

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 11, 125, 1351, 15330, 184846, 2382084, 32795170, 481379278, 7513591430, 124363961357, 2176990766569, 40199252548280, 781143277669538, 15937382209774353, 340696424417421213, 7616192835573406931, 177723017354688250713, 4321711817908214684734
Offset: 1

Views

Author

Stanislav Sykora, May 27 2014

Keywords

Comments

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.

Examples

			The shortest cycle with this property has length n=7: {1,4,7,3,6,2,5}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242523[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[Abs[Differences[x]], # < 3 &]];
Table[A242523[n], {n, 1, 10}]
 (* OR, a less simple, but more efficient implementation. *)
A242523[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[Abs[First[perm] - Last[perm]] >= 3, ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[Abs[Last[perm] - new] < 3, Continue[]];
      A242523[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Table[ct = 0; A242523[n, {1}, Range[2, n]]/2, {n, 1, 11}] (* Robert Price, Oct 24 2018 *)

Extensions

a(16)-a(25) from Hiroaki Yamanouchi, Aug 28 2014

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 24, 504, 8320, 131384, 2070087, 33465414, 561681192, 9842378284, 180447203232, 3462736479324, 69517900171056, 1458720714556848, 31955023452174314, 729874911380470641, 17359562438053760533, 429391730229931885360
Offset: 1

Views

Author

Stanislav Sykora, May 27 2014

Keywords

Comments

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.

Examples

			The shortest such cycle has length n=9: {1,5,9,4,8,3,7,2,6}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242524[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[Abs[Differences[x]], # < 4 &]];
Table[A242524[n], {n, 1, 10}]
 (* OR, a less simple, but more efficient implementation. *)
A242524[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[Abs[First[perm] - Last[perm]] >= 4, ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[Abs[Last[perm] - new] < 4, Continue[]];
      A242524[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Table[ct = 0; A242524[n, {1}, Range[2, n]]/2, {n, 1, 12}] (* Robert Price, Oct 24 2018 *)

Extensions

a(17)-a(25) from Hiroaki Yamanouchi, Aug 29 2014

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

Original entry on oeis.org

1, 1, 1, 3, 12, 36, 90, 214, 521, 1335, 3473, 9016, 23220, 59428, 152052, 389636, 999776, 2566517, 6586825, 16899574, 43352560, 111213798, 285319258, 732016006, 1878072638, 4818362046, 12361809384, 31714901077, 81366445061, 208750870961
Offset: 1

Views

Author

Stanislav Sykora, May 27 2014

Keywords

Comments

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.

Examples

			The 3 cycles of length n=4 are: {1,2,3,4},{1,2,4,3},{1,3,2,4}.
The first and the last of the 1335 such cycles of length n=10 are:
C_1={1,2,3,4,6,7,8,10,9,5}, C_1335={1,4,8,10,9,7,6,3,2,5}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242526[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[Abs[Differences[x]], # > 4 &]];
Join[{1, 1}, Table[A242526[n], {n, 3, 10}]]
(* OR, a less simple, but more efficient implementation. *)
A242526[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[Abs[First[perm] - Last[perm]] <= 4, ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[Abs[Last[perm] - new] > 4, Continue[]];
      A242526[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Join[{1, 1}, Table[ct = 0; A242526[n, {1}, Range[2, n]]/2, {n, 3, 12}] ](* Robert Price, Oct 25 2018 *)

Formula

From Andrew Howroyd, Apr 08 2016: (Start)
Empirical: a(n) = 2*a(n-1) + a(n-2) - a(n-4) + 9*a(n-5) + 5*a(n-6) - a(n-7) - 7*a(n-8) - 10*a(n-9) + 2*a(n-10) + 2*a(n-11) + 2*a(n-12) + 4*a(n-13) - 2*a(n-17) - a(n-18) for n>20.
Empirical g.f.: x + (3 - 6*x - 2*x^2 - x^3 + 3*x^4 - 22*x^5 - 5*x^6 + x^7 + 8*x^8 + 14*x^9 - 6*x^10 + 2*x^11 - 6*x^12 - 6*x^13 - 3*x^15 + x^16 + 3*x^17) / (1 - 2*x - x^2 + x^4 - 9*x^5 - 5*x^6 + x^7 + 7*x^8 + 10*x^9 - 2*x^10 - 2*x^11 - 2*x^12 - 4*x^13 + 2*x^17 + x^18). (End)

Extensions

a(22)-a(30) from Andrew Howroyd, Apr 08 2016

A242529 Number of cyclic arrangements (up to direction) of numbers 1,2,...,n such that any two neighbors are coprime.

Original entry on oeis.org

1, 1, 1, 1, 6, 2, 36, 36, 360, 288, 11016, 3888, 238464, 200448, 3176496, 4257792, 402573312, 139511808, 18240768000, 11813990400, 440506183680, 532754620416, 96429560832000, 32681097216000, 5244692024217600, 6107246661427200, 490508471914905600, 468867166554931200, 134183696369843404800
Offset: 1

Views

Author

Stanislav Sykora, May 30 2014

Keywords

Comments

a(n)=NPC(n;S;P) is the count of all neighbor-property cycles for a specific set S={1,2,...,n} of n elements and a specific pair-property P of "being coprime". For more details, see the link and A242519.

Examples

			There are 6 such cycles of length n=5: C_1={1,2,3,4,5}, C_2={1,2,3,5,4},
C_3={1,2,5,3,4}, C_4={1,2,5,4,3}, C_5={1,3,2,5,4}, and C_6={1,4,3,2,5}.
For length n=6, the count drops to just 2:
C_1={1,2,3,4,5,6}, C_2={1,4,3,2,5,6}.

Links

Crossrefs

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

Programs

  • Mathematica
    A242529[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[cpf[x], # != 1 &]];
cpf[x_] := Module[{i},
   Table[GCD[x[[i]], x[[i + 1]]], {i, Length[x] - 1}]];
Join[{1, 1}, Table[A242529[n], {n, 3, 10}]]
(* OR, a less simple, but more efficient implementation. *)
A242529[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[GCD[First[perm], Last[perm]] == 1, ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[GCD[Last[perm], new] != 1, Continue[]];
      A242529[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Join[{1, 1},Table[ct = 0; A242529[n, {1}, Range[2, n]]/2, {n, 3, 12}] ](* Robert Price, Oct 25 2018 *)

Formula

For n>2, a(n) = A086595(n)/2.

Extensions

a(1) corrected, a(19)-a(29) added by Max Alekseyev, Jul 04 2014
Showing 1-10 of 15 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.