1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutations and Combinations Question | Unlimited balls of 4 varieties |

  1. Mar 13, 2010 #1
    The questions is pretty short...

    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.
     
  2. jcsd
  3. Mar 13, 2010 #2
    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!
     
  4. Mar 13, 2010 #3
    I think you could use polynomials for that.

    Logic tells that if you multiply out
    [tex](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[/tex]
    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.
     
    Last edited: Mar 13, 2010
  5. Mar 13, 2010 #4
    Now THAT is a genius method!
     
  6. Mar 13, 2010 #5
    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.

     
  7. Mar 13, 2010 #6
    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.
     
  8. Mar 13, 2010 #7
    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?
     
  9. Mar 13, 2010 #8
    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.
     
  10. Mar 13, 2010 #9
    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.
     
  11. Mar 13, 2010 #10
    Indeed!

    Can you give me an idea about the missing steps. Unable to think!
     
  12. Mar 13, 2010 #11

    uart

    User Avatar
    Science Advisor

    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
     
  13. Mar 13, 2010 #12
    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.

    Good to know. Had not heard that before :)

    One little advantage of the polynomials is that they easily generalize to arbitrary contraints and problems.
     
  14. Mar 13, 2010 #13
    Never thought the same way. can you elaborate on this one?
     
  15. Mar 13, 2010 #14
    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
    [tex](1+x^3+x^4)(x^2+x^3+x^5)(x+x^2+x^3)=\dotsb+Ax^5+\dotsb[/tex]

    For less random number sets one might be able to find a closed form expression for the final answer.
     
  16. Mar 13, 2010 #15

    Redbelly98

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    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.
     
  17. Mar 14, 2010 #16

    Landau

    User Avatar
    Science Advisor

    See here.
     
  18. Mar 14, 2010 #17
    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.
     
  19. Mar 14, 2010 #18
    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 49, 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.
     
  20. Mar 14, 2010 #19

    Landau

    User Avatar
    Science Advisor

    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.
     
  21. Mar 14, 2010 #20
    That made me laugh.
    Many thanks for the response and for clearing up that confusion.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Permutations and Combinations Question | Unlimited balls of 4 varieties |
Loading...