login
A242524
Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is at least 4.
16
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,10
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.
LINKS
Hiroaki Yamanouchi, Table of n, a(n) for n = 1..27 (terms a(1)-a(16) from Stanislav Sykora)
S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.
EXAMPLE
The shortest such cycle has length n=9: {1,5,9,4,8,3,7,2,6}.
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 *)
PROG
(C++) See the link.
KEYWORD
nonn,hard
AUTHOR
Stanislav Sykora, May 27 2014
EXTENSIONS
a(17)-a(25) from Hiroaki Yamanouchi, Aug 29 2014
STATUS
approved