0
$\begingroup$

Let $[n]$ be the set of natural numbers $1,2,3 \cdots n$ and $k$ be a natural number. Define $S(n,k) = \# \{ A \subset [n] \mid \displaystyle\sum_{i \in A} i =k \}$. My question is; Are there any known good bounds (both upper and lower) on these numbers? Instead of taking the subsets in a special set such as $[n]$, if we take from a given subset $A$ of the set of integers, then it is the famous subset sum problem to decide whether $S(A,k) = 0$ or not.

$\endgroup$
4
  • 1
    $\begingroup$ The first place to check would be the references of OEIS A053632. $\endgroup$ Nov 10, 2022 at 13:54
  • $\begingroup$ Thanks for the pointer! $\endgroup$
    – mukhujje
    Nov 10, 2022 at 15:21
  • 2
    $\begingroup$ It is a number of strict partitions of $k$ with parts not exceeding $n$, that is, the coefficient of $x^k$ in the polynomial $(1+x)(1+x^2)\cdots(1+x^n)$. A lot is known about asymptotics in various regimes. $\endgroup$ Nov 10, 2022 at 16:44
  • $\begingroup$ Thanks, I looked at a few articles by S. Finch (following the OEIS pointer of @PeterTaylor) on related objects but haven't found any good asymptotic bounds. These numbers seem to be related to various problems in Physics and Biology as well. $\endgroup$
    – mukhujje
    Nov 11, 2022 at 7:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.