login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of permutations of length n with no consecutive triples i,i+d,i+2d for all d>0.
5

%I #16 Sep 27 2022 07:56:01

%S 1,1,2,5,21,100,597,4113,32842,292379,2925367,31983248,383514347,

%T 4966286235,69508102006,1039315462467,16627618496319,282023014602100,

%U 5075216962675445,96263599713301975,1925002914124917950

%N Number of permutations of length n with no consecutive triples i,i+d,i+2d for all d>0.

%e For n=4, there are 4!-a(4)=3 permutations with some consecutive triple i,i+d,i+2d. Note for n=4, only d=1 applies. Hence those three permutations are (0,1,2,3), (1,2,3,0), and (3,0,1,2). Since here only d=1, this is the same value of a(4) in A002628.

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

%p `if`(x=0 or x<y or x-y<>y-j,

%p 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[If[x == 0 || x < y || x-y != y-j, 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_, Sep 27 2022, after _Alois P. Heinz_ *)

%Y Cf. A002628, A174072, A174081, A174082, A174083, A295370.

%K nonn,more

%O 0,3

%A _Isaac Lambert_, Mar 15 2010

%E a(0)-a(3) and a(10)-a(20) from _Alois P. Heinz_, Apr 13 2021