cp's OEIS Frontend

A296530 Number of non-averaging permutations of [n] with first element n.

%I A296530 #20 Feb 16 2025 08:33:52
%S A296530 1,1,1,1,2,2,5,10,28,24,50,124,283,528,1266,3715,10702,8740,15414,
%T A296530 31988,68465,160964,380124,890738,2230219,3990852,8354276,20281732,
%U A296530 46056920,131289988,349369117,1054037937,3081527146,2440225484,4201202020,7475926894,13276918426
%N A296530 Number of non-averaging permutations of [n] with first element n.
%C A296530 A non-averaging permutation avoids any 3-term arithmetic progression.
%C A296530 a(0) = 1 by convention.
%H A296530 Alois P. Heinz, <a href="/A296530/b296530.txt">Table of n, a(n) for n = 0..99</a>
%H A296530 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/NonaveragingSequence.html">Nonaveraging Sequence</a>
%H A296530 Wikipedia, <a href="https://en.wikipedia.org/wiki/Arithmetic_progression">Arithmetic progression</a>
%H A296530 <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%F A296530 a(n) = A296529(n,n).
%e A296530 a(4) = 2: 4213, 4231.
%e A296530 a(5) = 2: 51324, 51342.
%e A296530 a(6) = 5: 621453, 624153, 624315, 624351, 624513.
%e A296530 a(7) = 10: 7312564, 7315264, 7315426, 7315462, 7315624, 7351264, 7351426, 7351462, 7351624, 7356124.
%p A296530 b:= proc(s) option remember; local n, r, ok, i, j, k;
%p A296530       if nops(s) = 1 then 1
%p A296530     else n, r:= max(s), 0;
%p A296530          for j in s minus {n} do ok, i, k:= true, j-1, j+1;
%p A296530            while ok and i>=0 and k<n do ok, i, k:=
%p A296530              not i in s xor k in s, i-1, k+1 od;
%p A296530            r:= r+ `if`(ok, b(s minus {j}), 0)
%p A296530          od; r
%p A296530       fi
%p A296530     end:
%p A296530 a:= n-> b({$0..n} minus {n-1}):
%p A296530 seq(a(n), n=0..30);
%t A296530 b[s_] := 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 A296530 a[n_] := b[Complement[Range[0, n], {n - 1}]]
%t A296530 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 02 2018, from Maple *)
%Y A296530 Main diagonal of A296529.
%Y A296530 Cf. A003407, A292523.
%K A296530 nonn
%O A296530 0,5
%A A296530 _Alois P. Heinz_, Dec 14 2017