|
%I #77 Jan 31 2024 14:15:08
%S 1,1,1,2,2,3,5,8,14,23,40,70,124,221,397,722,1314,2410,4441,8220,
%T 15272,28460,53222,99820,187692,353743,668273,1265204,2399784,4559828,
%U 8679280,16547220,31592878,60400688,115633260,221653776,425363952,817175698
%N Maximal coefficient of Product_{k<=n} (1 + x^k). Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1.
%C If k is allowed to approach infinity, this gives the partition numbers A000009.
%C a(n) is the maximal number of subsets of {1,2,...,n} that share the same sum.
%H T. D. Noe, Alois P. Heinz and Ray Chandler, <a href="/A025591/b025591.txt">Table of n, a(n) for n = 0..3339</a> (terms < 10^1000, first 201 terms from T. D. Noe, next 200 terms from Alois P. Heinz)
%H Dorin Andrica and Ioan Tomescu, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Tomescu/tomescu4.html">On an Integer Sequence Related to a Product of Trigonometric Functions, and Its Combinatorial Relevance </a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.4.
%H Vlad-Florin Dragoi and Valeriu Beiu, <a href="https://arxiv.org/abs/1911.01153">Fast Reliability Ranking of Matchstick Minimal Networks</a>, arXiv:1911.01153 [cs.DM], 2019.
%H Steven R. Finch, <a href="/A000980/a000980.pdf">Signum equations and extremal coefficients</a>, February 7, 2009. [Cached copy, with permission of the author]
%H E. Friedman and M. Keith, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/KEITH/carpet.html">Magic Carpets</a>, J. Int Sequences, 3 (2000), Article 00.2.5.
%H Marco Mondelli, S. H. Hassani, and R. Urbanke, <a href="http://arxiv.org/abs/1612.05295">Construction of Polar Codes with Sublinear Complexity</a>, arXiv preprint arXiv:1612.05295 [cs.IT], 2016-2017. See Sect. I.
%H Robert A. Proctor, <a href="http://www.jstor.org/stable/2975833">Solution of two difficult combinatorial problems with linear algebra</a>, American Mathematical Monthly 89, 721-734.
%H B. D. Sullivan, <a href="http://cs.uwaterloo.ca/journals/JIS/VOL16/Sullivan/sullivan8.html">On a conjecture of Adrica and Tomescu</a>, J. Int. Sequences 16 (2013), Article 13.3.1.
%F a(n) = A063865(n) + A063866(n).
%F a(n) ~ sqrt(6/Pi) * 2^n / n^(3/2) [conjectured by Andrica and Tomescu (2002) and proved by Sullivan (2013)]. - _Vaclav Kotesovec_, Mar 17 2020
%F More precise asymptotics: a(n) ~ sqrt(6/Pi) * 2^n / n^(3/2) * (1 - 6/(5*n) + 589/(560*n^2) - 39/(50*n^3) + ...). - _Vaclav Kotesovec_, Dec 30 2022
%F a(n) = max_{k>=0} A053632(n,k). - _Alois P. Heinz_, Jan 20 2023
%p b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,
%p `if`(i=0, 1, b(n+i, i-1)+b(abs(n-i), i-1)))
%p end:
%p a:=n-> b(0, n)+b(1, n):
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Mar 10 2014
%t f[n_, s_] := f[n, s]=Which[n==0, If[s==0, 1, 0], Abs[s]>(n*(n+1))/2, 0, True, f[n-1, s-n]+f[n-1, s+n]]; Table[Which[Mod[n, 4]==0||Mod[n, 4]==3, f[n, 0], Mod[n, 4]==1||Mod[n, 4]==2, f[n, 1]], {n, 0, 40}]
%t (* Second program: *)
%t p = 1; Flatten[{1, Table[p = Expand[p*(1 + x^n)]; Max[CoefficientList[p, x]], {n, 1, 50}]}] (* _Vaclav Kotesovec_, May 04 2018 *)
%t b[n_, i_] := b[n, i] = If[n > i(i+1)/2, 0, If[i == 0, 1, b[n+i, i-1] + b[Abs[n-i], i-1]]];
%t a[n_] := b[0, n] + b[1, n]; a /@ Range[0, 40] (* _Jean-François Alcover_, Feb 17 2020, after _Alois P. Heinz_ *)
%o (PARI) a(n)=if(n<0,0,polcoeff(prod(k=1,n,1+x^k),n*(n+1)\4))
%o (Python)
%o from collections import Counter
%o def A025591(n):
%o c = {0:1,1:1}
%o for i in range(2,n+1):
%o d = Counter(c)
%o for k in c:
%o d[k+i] += c[k]
%o c = d
%o return max(c.values()) # _Chai Wah Wu_, Jan 31 2024
%Y Cf. A039828, A063865, A069918, A063866, A063867, A083309, A083527, A086376.
%Y Cf. A053632, A160235, A359319, A359320.
%K nonn,nice
%O 0,4
%A _David W. Wilson_
|
