Partition (number theory)

[colerelm]

I'm trying to write a computer program that takes in any integer and tells me how many different ways I can add numbers up to get that number. For example, the number 3 would have 3 different ways(excluding 0): 1+2,2+1, and 1+1+1. The programming part isn't really what I'm struggling with, it's the mathematics behind it that I'm not understanding. How could I create a general (maybe recursive) function to this problem?


Wikipedia has an article on it but it didn't help me so much: http://en.wikipedia.org/wiki/Partition_function_(number_theory)#Asymptotic_behaviour


Can anyone provide some insight as to how I would go about doing something like this?


Thanks

 

[SlipEternal]

Given a number \(\displaystyle n\), you are looking for all possible integral solutions to:

\(\displaystyle 1a_1 + 2a_2 + ... + (n-1)a_{n-1} = n\) where \(\displaystyle a_i \ge 0\) for all \(\displaystyle i\). This is a Diophantine equation. Look up finding all integral solutions to a Diophantine equation.

Then, once you have all possible integral solutions, you are looking for all possible permutations of the multiset \(\displaystyle \{a_1 \bullet 1, a_2 \bullet 2, ..., a_{n-1} \bullet (n-1)\}\).

The number of permutations of each multiset is given by: \(\displaystyle \frac{\left(\sum_{i=1}^{n-1}{a_i}\right)!}{\prod_{i=1}^n{(a_i)!}}\).

So, the total number of ways this is possible is given by: \(\displaystyle \sum_{a \in A}{\left(\frac{\left(\sum_{i=1}^{n-1}{a_i}\right)!}{\prod_{i=1}^n{(a_i)!}}\right)}\) where \(\displaystyle A \subset \mathbb{Z}^{n-1}\) is all possible solutions to the above Diophantine equation.

Note: for the purposes of programming, it is easier if you give each \(\displaystyle a_i\) a maximum value, as well.
\(\displaystyle 0 \le a_1 \le \lfloor \frac{n}{i}\rfloor\). Now, you can set up a loop for each variable, as each variable has an upper and lower bound.

 

[pka]

I'm trying to write a computer program that takes in any integer and tells me how many different ways I can add numbers up to get that number. For example, the number 3 would have 3 different ways(excluding 0): 1+2,2+1, and 1+1+1. The programming part isn't really what I'm struggling with, it's the mathematics behind it that I'm not understanding. How could I create a general (maybe recursive) function to this problem?
Wikipedia has an article on it but it didn't help me so much: http://en.wikipedia.org/wiki/Partition_function_(number_theory)#Asymptotic_behaviour

This is a well know result in counting theory.
But if you notice in the wikipedia article, we do not consider 1+2 a different partition of three from 2+1. There is a standard routine to count the partitions as understood in that article. But does not count the partitions as you understand them.

 

[soroban]

Hello, colerelm!

Here's a baby-talk solution . . .

I'm trying to write a computer program that takes in any integer
and tells me how many different ways I can add numbers up to get that number.
For example, the number 3 would have 3 different ways (excluding 0): 1+2,2+1, and 1+1+1.
The programming part isn't really what I'm struggling with.
It's the mathematics behind it that I'm not understanding.
How could I create a general (maybe recursive) function to this problem?

Suppose we are considering \(\displaystyle n = 6.\)

Place 6 objects in a row, with a space between them:..\(\displaystyle \bullet\;\_\,\bullet\,\_\,\bullet\,\_\,\bullet\,\_\,\bullet\,\_\;\bullet\)

In any of the spaces, insert a "divider".

So that: .\(\displaystyle \bullet\;\_\,\bullet\,|\,\bullet\,|\,\bullet\,\_\,\bullet\,\_\;\bullet\,\text{ represents }\,2 + 1 + 3.\)


For each of the \(\displaystyle n-1\) spaces, there are two choices:
. . (1) insert a divider, or (2) don't insert a divider.

Hence, there are \(\displaystyle 2^{n-1}\) possible outcomes.

But this includes the case where no dividers are inserted.


Therefore: .\(\displaystyle 2^{n-1}-1\)