|
|
A296529
|
|
Number T(n,k) of non-averaging permutations of [n] with first element k; triangle T(n,k), n >= 0, k = 0..n, read by rows.
|
|
4
|
|
|
1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 2, 3, 3, 2, 0, 2, 5, 6, 5, 2, 0, 5, 6, 13, 13, 6, 5, 0, 10, 10, 16, 32, 16, 10, 10, 0, 28, 26, 36, 51, 51, 36, 26, 28, 0, 24, 50, 62, 74, 76, 74, 62, 50, 24, 0, 50, 50, 134, 138, 161, 161, 138, 134, 50, 50, 0, 124, 120, 146, 302, 345, 386, 345, 302, 146, 120, 124
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
A non-averaging permutation avoids any 3-term arithmetic progression.
T(0,0) = 1 by convention.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = T(n,n+1-k) > 0 for k=1..n.
|
|
EXAMPLE
|
T(5,1) = 2: 15324, 15342.
T(5,2) = 5: 21453, 24153, 24315, 24351, 24513.
T(5,3) = 6: 31254, 31524, 31542, 35124, 35142, 35412.
T(5,4) = 5: 42153, 42315, 42351, 42513, 45213.
T(5,5) = 2: 51324, 51342.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 1, 2, 1;
0, 2, 3, 3, 2;
0, 2, 5, 6, 5, 2;
0, 5, 6, 13, 13, 6, 5;
0, 10, 10, 16, 32, 16, 10, 10;
0, 28, 26, 36, 51, 51, 36, 26, 28;
0, 24, 50, 62, 74, 76, 74, 62, 50, 24;
0, 50, 50, 134, 138, 161, 161, 138, 134, 50, 50;
...
|
|
MAPLE
|
b:= proc(s) option remember; local n, r, ok, i, j, k;
if nops(s) = 1 then 1
else n, r:= max(s), 0;
for j in s minus {n} do ok, i, k:= true, j-1, j+1;
while ok and i>=0 and k<n do ok, i, k:=
not i in s xor k in s, i-1, k+1 od;
r:= r+ `if`(ok, b(s minus {j}), 0)
od; r
fi
end:
T:= (n, k)-> `if`(k=0, 0^n, b({$0..n} minus {k-1})):
seq(seq(T(n, k), k=0..n), n=0..14);
|
|
MATHEMATICA
|
b[s_List] := b[s] = Module[{n = Max[s], r = 0, ok, i, j, k}, If[Length[s] == 1, 1, Do[{ok, i, k} = {True, j-1, j+1}; While[ok && i >= 0 && k < n, {ok, i, k} = {FreeQ[s, i] ~Xor~ MemberQ[s, k], i-1, k+1}]; r = r + If[ok, b[s ~Complement~ {j}], 0], {j, s ~Complement~ {n}}]; r]];
T[0, 0]=1; T[n_, k_] := If[k==0, 0^n, b[Range[0, n] ~Complement~ {k-1}]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|