A293984 - OEIS

%I #52 Sep 17 2020 20:24:24

%S 1,1,1,2,3,3,4,10,16,23,35,85,142,229,369,895,1522,2614,4348,10467,

%T 18038,32160,54488,130148,226594,414130,710880,1685496,2958666,

%U 5503780,9544629,22476690,39724867,74884360,130949625,306457174,544777361,1037587152,1827129712

%N a(n) = A293857(n)/A010551(n).

%C Or row sums of the compressed triangle in A293783.

%C Conjecture: all terms are positive integers.

%C From _David A. Corneth_ (with participation of _Vladimir Shevelev_), Oct 24 2017: (Start)

%C Conjecture is true. Proof.

%C 1) Let C={c_1..c_n} be a permutation of {1..n}, d(C) be alternating sum c_1 - c_2 + ... +(-1)^(n-1)*c_n. Then max_{C in S_n}d(C) = A008794(n+1). Indeed, if n = 2*m, then evidently the maximum is reached on a C={2*m,1,2*m-1,2,...,m+1,m}; if n=2*m - 1, then the maximum is reached on a C={2*m-1,1,2*m-2,2,...,m-1,m}. In both cases max_{C in S_n}d(C) = m^2 = A008794(n+1). The number of distinct reaches of the maximum is, evidently, floor(n/2)!*floor((n+1)/2)! which is also Avi Peretz's representation (2001) of A010551(n). So, A293857(n) >= A010551(n) and a(n)>=1.

%C 2) Consider two cases: a) there are no C in S_n for which d(C) = k^2 < A008794(n+1). Then A293857(n) = A010551(n) and a(n) = 1; b) there is C for which d(C) = k^2 < A008794(n+1). Then, as in 1) to reach k^2 in case n=2*m consider all (n/2)! permutations of {c_1,c_3,...,c_n} and all (n/2)! permutations of {c_2, c_4, ... , c_(n+1)), or in case n = 2*m-1, all ((n+1)/2)! permutations of {c_1,c_3,...,c_(2*m-1)} and ((n-1)/2)! permutations of {c_2,c_4,...,c_(2m-2)}. So we again have A010551(n) distinct reaches. If the same k^2 could be reached by another permutation C_1 (other than above permutations of C), then we again obtain A010551 distinct reaches, etc. So, A293857(n) is always divisible by A010551(n). (End)

%H Peter J. C. Moses, <a href="/A293984/b293984.txt">Table of n, a(n) for n = 0..250</a>

%p b:= proc(p, m, s) option remember; (n-> `if`(n=0, `if`(issqr(s), 1, 0),

%p       `if`(p>0, b(p-1, m, s+n), 0)+`if`(m>0, b(p, m-1, s-n), 0)))(p+m)

%p     end:

%p a:= n-> (t-> b(n-t, t, 0))(iquo(n, 2)):

%p seq(a(n), n=0..40);  # _Alois P. Heinz_, Sep 17 2020

%t a293984=Table[

%t possibleSums=Range[1/2-(-1)^n/2-Floor[n/2]^2,Floor[(n+1)/2]^2];

%t filteredSums=Select[possibleSums,IntegerQ[Sqrt[#]]&];

%t positions=Map[Flatten[{#,Position[possibleSums,#,1]-1}]&,filteredSums];

%t Total[Map[SeriesCoefficient[QBinomial[n,Floor[(n+1)/2],q],{q,0,#[[2]]/2}]&,positions]],{n,20}] (* _Peter J. C. Moses_, Nov 05 2017 *)

%Y Cf. A008794, A010551, A293783, A293857.

%K nonn

%O 0,4

%A _Vladimir Shevelev_, Oct 21 2017

%E a(13)-a(30) from _David A. Corneth_, Oct 21 2017; a(31)-a(38) from _Peter J. C. Moses_, Nov 02 2017

%E a(0)=1 prepended by _Alois P. Heinz_, Sep 17 2020