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$