Math Is Fun Forum

Douglasm

Member

Registered: 2009-12-25

Posts: 15

Combinatorics

Hi everyone! I've tried a lot but I can't solve this question...can anyone help me?

How many are the integer, non-negative solutions of x + y + z +w = 20 if x > y?

The answer is 815.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinatorics

Hi Douglasm;

You mean there are 825 solutions.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Combinatorics

Break it down.  First solve the following problem:

If z and w are any non-negative integers, how many solutions are there to:

z + w = n

Where n is any integer.

Once you know this, we can use this solution because we just need to the number of solutions to:

z + w = 20 - x - y (= n)

So we can split it up into cases for each pair (x,y) with x > y.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Douglasm

Member

Registered: 2009-12-25

Posts: 15

Re: Combinatorics

I got it right now! Thanks for your assitance.

PS: You're right Bobby, the anwser is 825, it was a typo.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinatorics

Hi Douglasm;

I addition to the way that Ricky pointed out there are many ways to solve that problem. If you need more, we have it.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Douglasm

Member

Registered: 2009-12-25

Posts: 15

Re: Combinatorics

Actually, I would like to know a faster way to solve it. I'm studing for an entrance examination and I need to be able to solve these simple (but tiring) problems without wasting much time.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinatorics

Hi Douglasm;

If you used the above idea you should have something similar to:

Which can be simplified to:

and then to:

If you have access to a computer or the internet then you can use generating functions to fully solve the problem. Again this is only for the curious.

You treat that like any other function meaning you can expand it around zero.

Do you see your 825 as the coefficient of x^20 ?

From the GF we can get a recurrence form using the method outlined in the Vilenkin book on combinatorics.

Priming it with a(1) = 1 and a(3) = 3 you get:

Again you should see a(20) = 825.

We can solve the recurrence to get a closed form.

Plugging n=20 into that gets 825.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Douglasm

Member

Registered: 2009-12-25

Posts: 15

Re: Combinatorics

Great! I'll not be able to use those methods in a test, but they are really nice though. Thanks a lot.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinatorics

Hi Douglasm;

That's why I worked out the simple method for ya. Just wanted to show how those problems can be handled through other methods.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.