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.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ The first place to check would be the references of OEIS A053632. $\endgroup$– Peter TaylorNov 10, 2022 at 13:54
-
$\begingroup$ Thanks for the pointer! $\endgroup$– mukhujjeNov 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$– Fedor PetrovNov 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$– mukhujjeNov 11, 2022 at 7:47
Add a comment
|