1
$\begingroup$

Given the set of integers $S = \{1,..n\}$, how many subsets of $S$ with $k$ elements sum to $N\in \mathbb Z$?

$\endgroup$
2
  • 1
    $\begingroup$ What exactly do you mean asking "how many"? There is no closed expression, I am afraid. $\endgroup$ Dec 19, 2014 at 21:57
  • 4
    $\begingroup$ Could you give a bit more background for your question? For instance, where did this question arise? Would you be happy with an asymptotic formula? etc $\endgroup$
    – Yemon Choi
    Dec 19, 2014 at 22:05

2 Answers 2

4
$\begingroup$

See http://mathworld.wolfram.com/PartitionFunctionQ.html, or google "partitions into distinct parts"

$\endgroup$
2
$\begingroup$

There is a bijection between the subsets of size $k$ summing to $N$ and partitions of $N-{k \choose 2}$ with $k$ parts so that each part has size at most $n-k+1$,

$$\lbrace a_0 \lt a_1 \lt ... \lt a_{k-1} \rbrace \leftrightarrow \sum (a_i - i),$$

or partitions of $N-{k+1 \choose 2}$ into at most $k$ parts so that each part has size at most $n-k$,

$$\sum(a_i-i-1).$$

Those are partitions of $N-{k+1 \choose 2}$ whose Ferrers diagrams fit inside a $k \times (n-k)$ box. For a fixed $k$ and $n$, the generating function is a Gaussian binomial coefficient ${n \choose k}_q$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.