A295370
Number of permutations of [n] avoiding three consecutive terms in arithmetic progression.
Original entry on oeis.org
1, 1, 2, 4, 18, 80, 482, 3280, 26244, 231148, 2320130, 25238348, 302834694, 3909539452, 54761642704, 816758411516, 13076340876500, 221396129723368, 3985720881222850, 75503196628737920, 1510373288335622576, 31634502738658957588, 696162960370556156224, 15978760340940405262668
Offset: 0
a(3) = 4: 132, 213, 231, 312.
a(4) = 18: 1243, 1324, 1342, 1423, 2134, 2143, 2314, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4132, 4213, 4231, 4312.
-
b:= proc(s, j, k) option remember; `if`(s={}, 1,
add(`if`(k=0 or 2*j<>i+k, b(s minus {i}, i,
`if`(2*i-j in s, j, 0)), 0), i=s))
end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..12);
-
Table[Length[Select[Permutations[Range[n]],!MemberQ[Differences[#,2],0]&]],{n,0,5}] (* Gus Wiseman, Jun 03 2019 *)
b[s_, j_, k_] := b[s, j, k] = If[s == {}, 1, Sum[If[k == 0 || 2*j != i + k, b[s~Complement~{i}, i, If[MemberQ[s, 2*i - j ], j, 0]], 0], {i, s}]];
a[n_] := a[n] = b[Range[n], 0, 0];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, Nov 20 2023, after Alois P. Heinz *)
A174081
Number of permutations of length n with no consecutive triples i,i+d,i+2d (mod n) for all d.
Original entry on oeis.org
16, 40, 300, 1764, 17056, 118908, 1466840, 14079340, 184672896, 2206738248, 33901722288, 458478528000
Offset: 4
For n=4, there are 4!-a(4)=8 permutations with some consecutive triple i,i+d,i+2d (mod 4). Here only d=1 and d=3 works, and the permutations are (0,1,2,3), (1,2,3,0), (2,3,0,1), (3,0,1,2), (0,3,2,1), (3,2,1,0), (2,1,0,3), and (1,0,3,2)
A174082
Number of circular permutations of (0,1,...,n-1) with no consecutive triples i,i+d,i+2d for all d>0.
Original entry on oeis.org
1, 1, 1, 5, 18, 91, 544, 3842, 30573, 277532, 2770405, 30591153, 366836571, 4783219673, 66906770461, 1006000805687
Offset: 1
For n=4 there is only (4-1)!-a(4) = 1 circular permutation with a consecutive triple i,i+d,i+2d. It is (0,1,2,3).
A174083
Number of circular permutations of length n with no consecutive triples (i, i+d, i+2d) (mod n) for all d.
Original entry on oeis.org
4, 0, 40, 168, 1652, 9408, 117896, 1019260, 12737856, 140794368, 2072921376, 25990014896, 439692361160
Offset: 4
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.
A174084
Number of permutations of length n with no consecutive triples i,...i+r,...i+2r for all positive r, and for all equal spacings d.
Original entry on oeis.org
21, 94, 544, 3509, 26799, 223123, 2133511, 21793042, 248348572, 3008632130, 39989075942, 558800689295
Offset: 4
For n=4 there are 4!-a(4)=3 with some progression. These are (0,1,2,3), (1,2,3,0), and (3,0,1,2). Here for all the progressions, r=1 and d=1, hence this term is the same as a(4) in A002628.
Showing 1-5 of 5 results.
Comments