Permutations and Combinations Question | Unlimited balls of 4 varieties |

[dharavsolanki]

The questions is pretty short...

An unlimited no. of green, blue, red and white balls are given. If 9 balls are drawn, then no. of ways is...

The source was a chat session and hence the simple sentence.

I am stuck with this and thought that Homework Help doesn't attend out of the way questions and so I'm asking them here.

 

[dharavsolanki]

I have a faint idea that the question can be solved in the same manner as finding out the number of solutions to the equation - x + y + z + w = some number...

The fundamental idea beneath both the questions is the same...

Maybe that can help!

 

[Gerenuk]

I think you could use polynomials for that.

Logic tells that if you multiply out
$$(1+x+x^2+x^3+\dotsb)(1+x+x^2+x^3+\dotsb)(1+x+x^2+x^3+\dotsb)(1+x+x^2+x^3+\dotsb)=\frac{1}{(1-x)^4}=1+4x+\dotsb+220x^9+\dotsb$$
then the coefficient of x^9 is the answer to how many ways for
a+b+c+d=9 are possible (a,b,c,d are the powers picked out of each bracket and whenever they add up to 9, these terms contribute to the x^9 term).

See http://www.wolframalpha.com/input/?i=expand[1/(1-x)^4] for the calculation.

I suppose one could find some "closed form expression" for that involving a complicating sum over a product of binomials, but that isn't much better than just using wolfram.

 

[dharavsolanki]

Now THAT is a genius method!

 

[dharavsolanki]

I have come up with an explanation. Can someone help me out in polishing this? Just wondering, because people roundh ere have far more composed solutions than the one that I have posted below.

1) Consider the first bracket to represent the Green balls. The variable x does NOT mean ANYTHING. However, it's powers represent the number of green balls taken.

2) Similarly for the other brackets.



3) Now, consider that you have expanded the four brackets... so now you will have an infinite number of terms on the right. But the term with the power to nine would be special. Why? Because that term will be comprised of Two powers from the green bracket, three powers from white bracket, one from blue and the remaining from red. And all other combinations of the balls possible.



4) The funda here was that we never knew how many balls can we pick of each type. There was just too much confusion regarding that, so nCr was just not helpful. Instead we come up with this.



5) Now each time we have x to the power nine on the right side, we have one way of choosing nine balls. So how many times we have x to the power nine? As many times as the coefficient.

 

[Gerenuk]

I find it hard to follow the way you describe it. I can make a short try and you can combine it.

The problem is equivalent to find all possible ways to add for integers (determining the number of balls for each of the four colours) and get nine: a+b+c+d=9
To calculate the number of combinations, let us consider the following polynomial product. Later we will see that each braket corresponds to one colour of ball and the powers of the dummy variable x are the number of this ball colour taken.
When you multiply out the brakets completely then you get all possible combinations of four factors where each factor is from one braket. Let us call the powers of one such four factor combination a, b, c and d. Whenever these four factors yield x^9, i.e. a+b+c+d=9, you get a x^9 term in the total product. In the end you'd have to add up all x^9 terms (it will be 220 of these) ending up with a final expression 1+4x+...+220x^9+...
Thus, by solving the algebraic multiplication of polynomials, which a computer algebra system can do for you, you have found the number of ways of expression 9 as a sum of four integers.

 

[dharavsolanki]

Interesting. Because your description is sooo different, i find it way too similar to a textbook phrase.

What if we were to explain this in a class room situation?

 

[dharavsolanki]

Looking at my own reply, it is INDEED very complicated. Will need some thought to write down in a meaningful way.

Also, We don't need a computer system to solve the problem of finding the coefficients. It's a standard series expansion.

 

[Gerenuk]

My explanation is mathematical and boring. It should only serve as a guide to which information to present. Your's is more "classroom", but I find there are steps missing and there are some confusing remarks. That's why you can try to combine these ;)
Of course also an example would be useful, like doing the full multiplication for a smaller problem. Like having 3 times the numbers 1 to 3 only and counting powers in the end again.

 

[dharavsolanki]

Indeed!

Can you give me an idea about the missing steps. Unable to think!

 

[uart]

The answer is C(12,3), where C(n,r) = n!/(r! (n-r)! )

In general when choosing r items from n categories with arbitrary repeats then the number of combinations is : C(n+r-1,n-1)

So the answer is C(12,3) = 220

 

[Gerenuk]

Indeed!

Can you give me an idea about the missing steps. Unable to think!

Hard to say. Maybe you can go through my explanation sentence by sentence and write down the keywords and key statement I make. I was trying to be as concise as possible so each sentence could contain like 3 important informations. Then you could interweave these ideas into your text.

In general when choosing r items from n categories with arbitrary repeats then the number of combinations is : C(n+r-1,n-1)

Good to know. Had not heard that before :)

One little advantage of the polynomials is that they easily generalize to arbitrary contraints and problems.

 

[dharavsolanki]

One little advantage of the polynomials is that they easily generalize to arbitrary contraints and problems.

Never thought the same way. can you elaborate on this one?

 

[Gerenuk]

Never thought the same way. can you elaborate on this one?

I mean say you want to pick one number out of each of the sets
{1,3,5} {2,3,5} {1,2,3} and their sum should be 5
(for example you could have funny dice)

This can be "solved" with polynomials by finding
$$(1+x^3+x^4)(x^2+x^3+x^5)(x+x^2+x^3)=\dotsb+Ax^5+\dotsb$$

For less random number sets one might be able to find a closed form expression for the final answer.

 

[Redbelly98]

Moderator's note:

Thread moved to Homework & Coursework area. This covers any text-book style question, even if it is for independent study and not an actual school assignment.

 

[Landau]

The answer is C(12,3), where C(n,r) = n!/(r! (n-r)! )

In general when choosing r items from n categories with arbitrary repeats then the number of combinations is : C(n+r-1,n-1)

So the answer is C(12,3) = 220

Good to know. Had not heard that before :)

See here.

 

[Gerenuk]

Thanks. I was trying to close that knowledge gap. I think I memorized these forumlas by logic and forgot that there was another case which requires more thinking.

 

[nobahar]

Hello!
Hey everyone, I find this thread very interesting, but I am having trouble follwing the idea. I hope someone will be kind enough to expound the reasoning for me.
I figure the answer would simply be 4⁹, as there are four ways to choose the first colour, four the second, and so forth. This is clearly not the case, but I am having difficult understanding why.
A comprehensive explanation is not necessary, but any pointers would be helpful.
Many thanks,
Nobahar.

 

[Landau]

Short pointer: order doesn't matter.
Longer pointer: blue, blue, green, red, ..., red is to be considered the same as blue, green, blue, red, ..., red. In mathematical language, we're considering multisets.

You can pick the 9 balls as follows: a blue ones, b green ones, c red ones, d white ones.
The question is, how many different pairs (a,b,c,d) are there such that a+b+c+d=9.

 

[nobahar]

Short pointer:... Longer pointer:...

That made me laugh.
Many thanks for the response and for clearing up that confusion.