Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.