cp's OEIS Frontend

A296531 Number of non-averaging permutations of [n] with first element ceiling(n/2).

%I A296531 #18 Feb 16 2025 08:33:52
%S A296531 1,1,1,2,3,6,13,32,51,76,161,386,903,2280,5018,12828,19720,27656,
%T A296531 48788,100120,220686,537208,1258242,3123166,7056165,17189752,35968308,
%U A296531 82137764,189847917,509880208,1322092262,3807727932,5678509066,7721623440,13293899416,23650787296
%N A296531 Number of non-averaging permutations of [n] with first element ceiling(n/2).
%C A296531 A non-averaging permutation avoids any 3-term arithmetic progression.
%C A296531 a(0) = 1 by convention.
%H A296531 Alois P. Heinz, <a href="/A296531/b296531.txt">Table of n, a(n) for n = 0..99</a>
%H A296531 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/NonaveragingSequence.html">Nonaveraging Sequence</a>
%H A296531 Wikipedia, <a href="https://en.wikipedia.org/wiki/Arithmetic_progression">Arithmetic progression</a>
%H A296531 <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%F A296531 a(n) = A296529(n,ceiling(n/2)).
%e A296531 a(5) = 6: 31254, 31524, 31542, 35124, 35142, 35412.
%e A296531 a(6) = 13: 312564, 315264, 315426, 315462, 315624, 351264, 351426, 351462, 351624, 354126, 354162, 354612, 356124.
%p A296531 b:= proc(s) option remember; local n, r, ok, i, j, k;
%p A296531       if nops(s) = 1 then 1
%p A296531     else n, r:= max(s), 0;
%p A296531          for j in s minus {n} do ok, i, k:= true, j-1, j+1;
%p A296531            while ok and i>=0 and k<n do ok, i, k:=
%p A296531              not i in s xor k in s, i-1, k+1 od;
%p A296531            r:= r+ `if`(ok, b(s minus {j}), 0)
%p A296531          od; r
%p A296531       fi
%p A296531     end:
%p A296531 a:= n-> b({$0..n} minus {ceil(n/2)-1}):
%p A296531 seq(a(n), n=0..25);
%t A296531 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 A296531 a[n_] := b[Complement[Range[0, n], {Ceiling[n/2] - 1}]];
%t A296531 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Jun 02 2018, from Maple *)
%Y A296531 Cf. A003407, A292523, A296529.
%K A296531 nonn
%O A296531 0,4
%A A296531 _Alois P. Heinz_, Dec 14 2017