A216727 Duplicate of A174075.
1, 6, 18, 93, 600, 4320, 35168, 321630, 3257109, 36199458, 438126986, 5736774869
Offset: 3
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.
For n=5 (0,2,4,1,3) is an example of a permutation with an i,i+2,i+4 triple. If we look at 0,2,4 as a block, then we have 3! ways to permute the triple with the remaining 1 & 3. Hence a(5) = 5! - 3! = 114.
b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
`if`(x=0 or x-y<>2 or y-j<>2, b(s minus {j}, y, j), 0), j=s))
end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..14); # Alois P. Heinz, Apr 13 2021
b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[
If[x == 0 || x - y != 2 || y - j != 2,
b[s ~Complement~ {j}, y, j], 0], {j, s}]];
a[n_] := b[Range[n], 0, 0];
Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Mar 02 2022, after Alois P. Heinz *)
Since a(5)=22, there are (5-1)!-22=2 circular permutations with consecutive triples i,i+2,i+4 in all circular permutations of length 5. They are exactly (0,2,4,1,3) and (0,2,4,3,1).
For example, a(5) does not count the permutation (0,4,1,3,2) since 4,1,3 is an arithmetic progression of 2 mod(5).
For n=5 since a(5)=0 all (5-1)! = 24 circular permutations of length 5 have some consecutive triple (i, i+d, i+2d) (mod 5). For example, the permutation (0,4,2,1,3) has a triple (1,3,0) with d=2. This is clearly a special case.
Triangle begins: 1 0 0 1 6 0 0 0 0 18 5 0 0 0 1 93 18 9 0 0 0 0 600 84 28 7 0 0 0 1 4320 512 192 0 16 0 0 0 0 35168 4122 810 156 54 9 0 0 0 1 321630 34000 5625 1400 200 0 25 0 0 0 0 ...
Comments