1
$\begingroup$

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.

  • 0
    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](http://math.stackexchange.com/q/33315/9436) you raised.2011-04-18

3 Answers 3

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.

4

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.

3

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

  • 0
    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](http://math.stackexchange.com/questions/33315/partition-an-integer-n-by-limitation-on-size-of-the-partition/33411#33411).2011-04-17