%I #37 Feb 04 2024 14:15:46

%S 1,1,2,6,24,114,674,4714,37754,340404,3412176,37631268,452745470,

%T 5900431012,82802497682,1244815252434,19958707407096,339960096280062,

%U 6130407887839754,116675071758609742,2337186717333367706,49153251967227002616,1082860432463176004544

%N Number of permutations of length n with no consecutive triples i,i+2,i+4.

%C Note for n<5 there are no such subsequences, so those values are trivially n!.

%H Max Alekseyev, <a href="/A174072/b174072.txt">Table of n, a(n) for n = 0..100</a>

%H Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, <a href="http://math.ku.edu/~ilambert/CN.pdf">Arithmetic Progressions in Permutations</a>, 2012. [broken link]

%e 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.

%p b:= proc(s, x, y) option remember; `if`(s={}, 1, add(

%p `if`(x=0 or x-y<>2 or y-j<>2, b(s minus {j}, y, j), 0), j=s))

%p end:

%p a:= n-> b({$1..n}, 0$2):

%p seq(a(n), n=0..14); # _Alois P. Heinz_, Apr 13 2021

%t b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[

%t If[x == 0 || x - y != 2 || y - j != 2,

%t b[s ~Complement~ {j}, y, j], 0], {j, s}]];

%t a[n_] := b[Range[n], 0, 0];

%t Table[a[n], {n, 0, 14}] (* _Jean-François Alcover_, Mar 02 2022, after _Alois P. Heinz_ *)

%Y Cf. A002628, A174073, A174074, A174075.

%Y First column of A216716.

%K nonn

%O 0,3

%A _Isaac Lambert_, Mar 06 2010

%E a(0)-a(4) and a(10)-a(11) moved from a duplicate entry based on the Dymacek et al. paper on Apr 13 2021

%E a(12)-a(22) from _Alois P. Heinz_, Apr 13 2021