# Number of possible solutions for an equation

If $x$, $y$, and $z$ are natural numbers, how many solutions are there to $x+y+z=25$?

How would I figure this out? I can't even begin dissecting this problem. Where do I begin?

Suppose that "natural number" doesn't include 0. Take 25 balls, and put a wall between any two. A partition $a+b+c=25$ is the same as a choice of two walls, and there are $\binom{24}{2} = 276$ of these.

If zeroes are allowed, then $(x+1)+(y+1)+(z+1) = 28$, and so the answer is $\binom{27}{2} = 351$.

• Wait...whattttttt – Snowman Nov 8 '10 at 5:37
• Ok wait I think I get it, but why 24 and not 25 in the first case? What would putting a wall at the end of the last ball represent? – Snowman Nov 8 '10 at 5:41
• See what happens when we replace 25 by 2,3,4. – Yuval Filmus Nov 8 '10 at 5:48
• Well if we had four balls, then a wall at the end would represent z being zero. Ok so youre saying if were not including zero, then we cant have a wall at the end. But this works fine for our last case where we do include zeros? Looking through my notes, I do see a general form for this, but when we do include zeros, I dont understand the intuition of having 27 on top. Doing a manual count of possible positions of the wall, it seems like there would only be 26 possibilites.. – Snowman Nov 8 '10 at 5:53
• Keep thinking... – Yuval Filmus Nov 8 '10 at 6:10

This is called the "partition function" of 25. See here:

http://en.wikipedia.org/wiki/Partition_function_%28number_theory%29

It's not an easy-to-compute-directly function - the best bet is simply writing a small script that counts solutions using a double loop.

• You sure its supposed to be that complicated? It was given as a minor excercise problem that should be abled to solve on paper.. – Snowman Nov 8 '10 at 5:30
• No it isn't, since there are exactly 3 parts. – Yuval Filmus Nov 8 '10 at 5:30
• No it isnt what? Complicated? – Snowman Nov 8 '10 at 5:32
• I meant it isn't the partition function. It's also not complicated. – Yuval Filmus Nov 8 '10 at 5:33
• You are of course correct. My bad. – Gadi A Nov 8 '10 at 6:03

HINT $\rm\ \ (x,y,z)\ \to\ \{x,\ x+y\}\$ bijects solutions with two elt subsets of $\{1,2,\cdots,24\}$

Here is a simpler explanation: Lets look at the equation x + y = k where x >= 0 && y >=0 the solution set is of form {{k, 0}, {k-1, 1}, ... {0, k+1}} and there are (k+1) items in the set.

x + y + z = k can be broken down into: x + (y + z) = k

if we choose x = 0, solutions of (y + z) = k are k+1. if we choose x = 1, solutions of (y + z) = k-1 are k. if we choose x = 2, solutions of (y + z) = k-2 are k-1. if we choose x = k, solutions of (y + z) = 0 are 1.

this is a simple natural number sum: 1 + 2 + 3 + ... + (k +1) = ((k + 1) * (k +2)/ 2)

My math is weak so I dont know what are the proper names to call something.