Decomposition by subtraction

Question

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.

Answer 1

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

Answer 2

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.

Answer 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)$$

as per Partition (Number Theory).

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.