How many k-subsets of the integers {1,...,n} sum to N?

Question

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

Answer 1

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

Answer 2

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$.