cp's OEIS Frontend

A025591 Maximal coefficient of Product_{k<=n} (1 + x^k). Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1.

%I A025591 #82 May 15 2024 11:00:35
%S A025591 1,1,1,2,2,3,5,8,14,23,40,70,124,221,397,722,1314,2410,4441,8220,
%T A025591 15272,28460,53222,99820,187692,353743,668273,1265204,2399784,4559828,
%U A025591 8679280,16547220,31592878,60400688,115633260,221653776,425363952,817175698
%N A025591 Maximal coefficient of Product_{k<=n} (1 + x^k). Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1.
%C A025591 If k is allowed to approach infinity, this gives the partition numbers A000009.
%C A025591 a(n) is the maximal number of subsets of {1,2,...,n} that share the same sum.
%H A025591 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 A025591 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 A025591 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 A025591 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 A025591 Erich Friedman and Mike 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 A025591 Susumu Kubo, <a href="https://arxiv.org/abs/2405.05544">Partially Ordered Sets Corresponding to the Partition Problem</a>, arXiv:2405.05544 [cs.DM], 2024. See pp. 2, 16.
%H A025591 Marco Mondelli, S. Hamed Hassani, and Rüdiger 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 A025591 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 A025591 Blair 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 A025591 a(n) = A063865(n) + A063866(n).
%F A025591 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 A025591 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 A025591 a(n) = max_{k>=0} A053632(n,k). - _Alois P. Heinz_, Jan 20 2023
%p A025591 b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,
%p A025591       `if`(i=0, 1, b(n+i, i-1)+b(abs(n-i), i-1)))
%p A025591     end:
%p A025591 a:=n-> b(0, n)+b(1, n):
%p A025591 seq(a(n), n=0..40);  # _Alois P. Heinz_, Mar 10 2014
%t A025591 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 A025591 (* Second program: *)
%t A025591 p = 1; Flatten[{1, Table[p = Expand[p*(1 + x^n)]; Max[CoefficientList[p, x]], {n, 1, 50}]}] (* _Vaclav Kotesovec_, May 04 2018 *)
%t A025591 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 A025591 a[n_] := b[0, n] + b[1, n]; a /@ Range[0, 40] (* _Jean-François Alcover_, Feb 17 2020, after _Alois P. Heinz_ *)
%o A025591 (PARI) a(n)=if(n<0,0,polcoeff(prod(k=1,n,1+x^k),n*(n+1)\4))
%o A025591 (Python)
%o A025591 from collections import Counter
%o A025591 def A025591(n):
%o A025591     c = {0:1,1:1}
%o A025591     for i in range(2,n+1):
%o A025591         d = Counter(c)
%o A025591         for k in c:
%o A025591             d[k+i] += c[k]
%o A025591         c = d
%o A025591     return max(c.values()) # _Chai Wah Wu_, Jan 31 2024
%Y A025591 Cf. A039828, A063865, A069918, A063866, A063867, A083309, A083527, A086376.
%Y A025591 Cf. A053632, A160235, A359319, A359320.
%K A025591 nonn,nice
%O A025591 0,4
%A A025591 _David W. Wilson_