# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a174072
Showing 1-1 of 1

%I A174072 #37 Feb 04 2024 14:15:46
%S A174072 1,1,2,6,24,114,674,4714,37754,340404,3412176,37631268,452745470,
%T A174072 5900431012,82802497682,1244815252434,19958707407096,339960096280062,
%U A174072 6130407887839754,116675071758609742,2337186717333367706,49153251967227002616,1082860432463176004544
%N A174072 Number of permutations of length n with no consecutive triples i,i+2,i+4.
%C A174072 Note for n<5 there are no such subsequences, so those values are trivially n!.
%H A174072 Max Alekseyev, <a href="/A174072/b174072.txt">Table of n, a(n) for n = 0..100</a>
%H A174072 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 A174072 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 A174072 b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
%p A174072      `if`(x=0 or x-y<>2 or y-j<>2, b(s minus {j}, y, j), 0), j=s))
%p A174072     end:
%p A174072 a:= n-> b({$1..n}, 0$2):
%p A174072 seq(a(n), n=0..14);  # _Alois P. Heinz_, Apr 13 2021
%t A174072 b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[
%t A174072      If[x == 0 || x - y != 2 || y - j != 2,
%t A174072      b[s ~Complement~ {j}, y, j], 0], {j, s}]];
%t A174072 a[n_] := b[Range[n], 0, 0];
%t A174072 Table[a[n], {n, 0, 14}] (* _Jean-François Alcover_, Mar 02 2022, after _Alois P. Heinz_ *)
%Y A174072 Cf. A002628, A174073, A174074, A174075.
%Y A174072 First column of A216716.
%K A174072 nonn
%O A174072 0,3
%A A174072 _Isaac Lambert_, Mar 06 2010
%E A174072 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 A174072 a(12)-a(22) from _Alois P. Heinz_, Apr 13 2021

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE