# Decomposition by subtraction

In how many ways one can decompose an integer $n$ to smaller integers at least 3? for example 13 has the following decompositions:

\begin{gather*} 13\\ 3,10\\ 4,9\\ 5,8\\ 6,7\\ 3,3,7\\ 3,4,6\\ 3,5,5\\ 3,3,3,4\\ 4,4,5\\ \end{gather*}

Points and hints are welcome.

-
Is there any reason you have not yet accepted an answer? I believe the question you raised has been answered in full. This also goes for the other related question you raised. – quantumelixir Apr 18 '11 at 20:17

Let there be $p(n)$ partitions of the positive integer $n$ that use integers $1, 2, \dots, n$ (A000041).

Using the inclusion-exclusion principle, the number of partitions that don't use the numbers $1$ and $2$ is given by:

$$p(n) - p(n - 1) - p(n - 2) + p(n - 3)$$

since, there are $p(n-1)$ numbers that use $1$ in the partition of $n$, $p(n-2)$ that use $2$, and there are $p(n-3)$ that use both $1$ and $2$ in the partition of $n$.

In your case, the answer is $p(13)-p(12)-p(11)+p(10)=101-77-56+42=10$ (counting the trivial partition $13=13$).

-
Both comments were extremely helpful. Now, is there any idea about how I can count those decompositions with exactly $i$ members? for example there are $\lfloor \frac{n}{2} \rfloor$ decompositions for $n$ with exactly two members, for 13 we have $\{10,3\}$,$\{9,4\}$,.... What about the number of decompositions of $n$ with exactly $i$ members, members are greater than two? It is clear that because the members are at least three, $i$ is smaller than $\lfloor \frac{n}{3} \rfloor$. – Losy Apr 16 '11 at 13:39
You can pull off a kind of recursion similar to the one @DerekJennings mentions in his answer below, by adjoining one more variable to the recursive formula to keep track of the number of addends that you've used so far. See this answer. – quantumelixir Apr 17 '11 at 5:38

This is usually called "partitions of $n$ into parts of at least 3"

You will find much of what you want in OEIS A008483. There are some differences: with your example of partitions of 13, the single part $13$ is usually regarded as meeting the condition, and you have also missed $4+4+5$, while the partition $3+6+4$ is seen as being equivalent to $3+4+6$. So the OEIS has 10 possible partitions of 13 with each parts at least 3.

-

Let $p(k,n)$ be the number of partitions of $n$ into parts at least as large as $k$ then

$$p(k,n) = p(k,n-k) + p(k+1,n)$$

And so

$$p(k+1,n) = p(k,n) - p(k,n-k).$$

Therefore

\begin{align} p(3,n) &= p(2,n) - p(2,n-2) \\ &= \{ p(1,n) - p(1,n-1) \} - \{ p(1,n-2) - p(1,n-3) \} \\ &= p(n) - p(n-1) - p(n-2) + p(n-3), \end{align}

where $p(n)$ is the usual partition function, as per quantumelixir's formula.

-