How many ways are there to choose non-repeating numbers that add up to $N$?

Question

I'm trying to find a formula for the number of ways (and maybe an easy road to find those ways) to find all the sets $A$ of natural numbers $A_i\in\mathbb{N}<N$, such that no numbers in $A$ repeat and the numbers in $A$ add up to $N\in\mathbb{N}$. I have no idea how to find this, so any help would be appreciated.

Answer 1

We have for the unlabeled set operator

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET(\mathcal{A})}$$

by the exponential formula the OGF

$$\exp \left(\sum_{\ell\ge 1} (-1)^{\ell-1} \frac{A(z^\ell)}{\ell}\right).$$

In the present case $$A(z) = z+z^2+\cdots = \frac{z}{1-z}$$

so that we find

$$Q(z) = \sum_{n\ge 0} Q_n z^n = \exp\left(\sum_{\ell\ge 1} (-1)^{\ell-1} \frac{1}{\ell} \frac{z^\ell}{1-z^\ell}\right).$$

We now build a recurrence. We have $Q_0 = 1$ and get

$$[z^{n-1}] Q'(z) = n Q_n \\ = [z^{n-1}] \exp\left(\sum_{\ell\ge 1} (-1)^{\ell-1} \frac{1}{\ell} \frac{z^\ell}{1-z^\ell}\right) \sum_{\ell\ge 1} (-1)^{\ell-1} \frac{z^{\ell-1}}{(1-z^\ell)^2} \\ = [z^{n-1}] Q(z) \sum_{\ell\ge 1} (-1)^{\ell-1} \frac{z^{\ell-1}}{(1-z^\ell)^2} = [z^{n-1}] Q(z) \sum_{\ell= 1}^{n} (-1)^{\ell-1} \frac{z^{\ell-1}}{(1-z^\ell)^2} \\ = \sum_{\ell= 1}^{n} (-1)^{\ell-1} [z^{n-\ell}] \frac{1}{(1-z^\ell)^2} Q(z) = \sum_{\ell= 1}^{n} (-1)^{\ell-1} \sum_{q=0}^{\lfloor n/\ell \rfloor -1} (q+1) Q_{n-(q+1)\ell} \\ = \sum_{\ell= 1}^{n} (-1)^{\ell-1} \sum_{q=1}^{\lfloor n/\ell \rfloor} q Q_{n-q\ell} = \sum_{p=1}^n Q_{n-p} \sum_{\ell|p} (-1)^{\ell-1} \frac{p}{\ell}.$$

This finally yields

$$\bbox[5px,border:2px solid #00A000]{ Q_n = \frac{1}{n} \sum_{p=1}^n Q_{n-p} \sum_{\ell|p} (-1)^{p/\ell-1} \ell.}$$

This will produce the sequence

$$1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, \\ 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, \ldots $$

which does indeed point to OEIS A000009. OEIS A111133 is then obtained by inspection.

Remark. An alternative representation of

$$p \sum_{\ell|p} (-1)^{\ell-1} \frac{1}{\ell} \quad\text{is}\quad \sum_{\ell|p \wedge \ell\;\mathrm{odd}} \ell = \sigma_{\mathrm{odd}}(p).$$

To see this write $p= 2^{v_2(p)} m$ to get

$$2^{v_2(p)} m \sum_{q=0}^{v_2(p)} \sum_{\ell|m} (-1)^{\ell 2^q-1} \frac{1}{\ell 2^q} \\ = 2^{v_2(p)} m \sum_{\ell|m} (-1)^{\ell-1} \frac{1}{\ell} + 2^{v_2(p)} m \sum_{q=1}^{v_2(p)} \sum_{\ell|m} (-1)^{\ell 2^q-1} \frac{1}{\ell 2^q} \\ = 2^{v_2(p)} \sigma_{\mathrm{odd}}(p) - 2^{v_2(p)} m \sum_{q=1}^{v_2(p)} \sum_{\ell|m} \frac{1}{\ell 2^q} = 2^{v_2(p)} \sigma_{\mathrm{odd}}(p) - 2^{v_2(p)} m \sum_{\ell|m} \frac{1}{\ell} \sum_{q=1}^{v_2(p)} \frac{1}{2^q}. \\ = 2^{v_2(p)} \sigma_{\mathrm{odd}}(p) - \sigma_{\mathrm{odd}}(p) \sum_{q=1}^{v_2(p)} 2^{v_2(p)-q} = 2^{v_2(p)} \sigma_{\mathrm{odd}}(p) - \sigma_{\mathrm{odd}}(p) (2^{v_2(p)}-1) \\ = \sigma_{\mathrm{odd}}(p).$$

A slightly different version of the same proof goes like this (put $v_2(p) = v$):

$$\sum_{\ell|p} (-1)^{p/\ell-1} \ell = \sum_{q=0}^v \sum_{\ell|m} (-1)^{2^v m/\ell/2^q-1} \ell 2^q \\ = \sum_{\ell|m} (-1)^{m/\ell-1} \ell 2^v + \sum_{q=0}^{v-1} \sum_{\ell|m} (-1)^{2^v m/\ell/2^q-1} \ell 2^q \\ = 2^v \sigma_{\mathrm{odd}}(p) - \sum_{q=0}^{v-1} \sum_{\ell|m} \ell 2^q = 2^v \sigma_{\mathrm{odd}}(p) - \sum_{\ell|m} \ell \sum_{q=0}^{v-1} 2^q \\ = 2^v \sigma_{\mathrm{odd}}(p) - (2^v-1) \sigma_{\mathrm{odd}}(p) \\ = \sigma_{\mathrm{odd}}(p).$$

Addendum. We may use the alternate form of $Q(z)$ which is

$$Q(z) = \prod_{m\ge 1} (1+z^m).$$

This yields

$$Q'(z) = Q(z) \sum_{m\ge 1} \frac{m z^{m-1}}{1+z^m}.$$

We obtain

$$[z^{n-1}] Q'(z) = [z^{n-1}] Q(z) \sum_{m=1}^n \frac{m z^{m-1}}{1+z^m} = \sum_{m=1}^n [z^{n-m}] \frac{m}{1+z^m} Q(z) \\ = \sum_{m=1}^n \sum_{q=0}^{\lfloor n/m \rfloor - 1} m (-1)^q [z^{n-m-qm}] Q(z) = \sum_{m=1}^n \sum_{q=0}^{\lfloor n/m \rfloor - 1} m (-1)^q Q_{n-(q+1)m} \\ = \sum_{m=1}^n \sum_{q=1}^{\lfloor n/m \rfloor} m (-1)^{q-1} Q_{n-qm} = \sum_{p=1}^n \sum_{q|p} \frac{p}{q} (-1)^{q-1} Q_{n-p} \\ = \sum_{p=1}^n Q_{n-p} \sum_{q|p} (-1)^{p/q-1} q.$$

We may then continue as before.

Answer 2

Let $f(n,k)$ be the number of sets of $k$ natural numbers summing to $n$. You want to find $\sum_{k=2}^{\sqrt{2n}} f(n,k)$. The reason for the $\sqrt{2n}$ in the upper bound is that any set of $k$ numbers will have sum at least $k(k+1)/2$; therefore, there is no need to consider sets of size $\sqrt{2n}$ or larger.

I claim that $$ f(n,k) = f(n-k,k)+f(n-k,k-1) $$ To see this, let $x_k>x_{k-1}>\dots>x_1$ be $k$ numbers summing to $n$. If $x_1>1$, then $$ x_k-1,x_{k-1}-1,\dots,x_2-1,x_1-1 $$ is a set of $k$ numbers summing to $n-k$. If $x_1=1$, then the above list with $x_1-1$ removed is a list of $k-1$ numbers summing to $n-k$.

This recursion gives you an algorithm to compute $f(n,k)$ for all $2\le k\le \sqrt{2n}$ via dynamic programming using $O(n^{3/2})$ additions.