1. Limited time only! Sign up for a free 30min personal 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!

Distribution (combinations) problem

  1. Sep 28, 2011 #1
    Hello,

    I have a small problem/puzzle to solve which goes as follows:
    (I have already calculated it, however I am not sure I followed the right reasoning as mathematics is not my strong point and after building a Java app to brute force it, it crashed on out-of-memory error):

    ------------------------------

    We have ten bikes (b1, b2, …, b10) that need to be sold at 3 shops
    houses (s1, s2, s3). Each shop can sell at most 5 bikes.

    How many solutions are possible? You may solve this using
    mathematics, or brute force with a spreadsheet, or small program.

    This is a problem in combinations where the order of selection does not matter.
    Selecting r things from n: nCr = n! / (r! (n-r)!)

    --------------------------------

    According to my math calc's there's 10! permutations of bikes (http://www.wtamu.edu/academic/anns/mps/math/mathlab/col_algebra/col_alg_tut56_perm.htm), but I am not entirely sure where to take it after that ...

    Any advice would be much appreciated !

    hg
     
  2. jcsd
  3. Sep 28, 2011 #2
    The way I understood the problem...the number of combinations is small.

    The way I see, the mathematical statement looks like this:

    [itex]0 \leq x \leq 5[/itex]

    [itex]0 \leq y \leq 5[/itex]

    [itex]0 \leq z \leq 5[/itex]

    and

    [itex]x+y+z=10[/itex]

    If I brute force it with 3 nested do-loops, I get this:


    0 5 5
    1 4 5
    1 5 4
    2 3 5
    2 4 4
    2 5 3
    3 2 5
    3 3 4
    3 4 3
    3 5 2
    4 1 5
    4 2 4
    4 3 3
    4 4 2
    4 5 1
    5 0 5
    5 1 4
    5 2 3
    5 3 2
    5 4 1
    5 5 0

    n = 21
     
  4. Sep 28, 2011 #3

    uart

    User Avatar
    Science Advisor

    Are the bikes/shops distinguishable?
     
  5. Sep 28, 2011 #4
    Hi yes the numbers bikes and shops are distinguishable sorry forgot to mention that. So there are quite a few combinations.

    The order of bikes at a particular shop doesn't matter though:

    So :
    a1={b1, b2} a2={b3 - b6}, a3={b7 - b10}

    is equavalent to ( only order of b1 and b2 switched):

    a1={b2, b1} a2={b3 - b6}, a3={b7 - b10}


    I also get 21 for the initial shopCombos ... from here it is where I get a bit stuck,
    I would love to hear any final value you guys get and then I can compare my value & methodology with yours.
     
    Last edited: Sep 28, 2011
  6. Sep 28, 2011 #5
    Oh, I see...you are already talking about 10! combinations...maybe the final solution is the 21 ways in which each those 10! combinations can be broken down into the 3 shops...

    21 x 10! ?
     
  7. Sep 28, 2011 #6
    hey gsal yes it would be 10! ( = 3,628,800 ) combinations, only, the order of bikes at any shop doesn't matter (in my prev post, which I must have sneaked in just before yours!) so this reduces it down again ... I'm not exactly sure how to tackle this one though ?!
     
  8. Sep 28, 2011 #7
    How about this?

    Code (Text):

    0 5 5
        shop 1, 1 combinations out of 10 available bikes
        shop 2, 252 combinations out of 10 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 252
    1 4 5
        shop 1, 10 combinations out of 10 available bikes
        shop 2, 126 combinations out of  9 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 1260
    1 5 4
        shop 1, 10 combinations out of 10 available bikes
        shop 2, 126 combinations out of  9 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 1260
    2 3 5
        shop 1, 45 combinations out of 10 available bikes
        shop 2, 56 combinations out of  8 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 2520
    2 4 4
        shop 1, 45 combinations out of 10 available bikes
        shop 2, 70 combinations out of  8 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 3150
    2 5 3
        shop 1, 45 combinations out of 10 available bikes
        shop 2, 56 combinations out of  8 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 2520
    3 2 5
        shop 1, 120 combinations out of 10 available bikes
        shop 2, 21 combinations out of  7 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 2520
    3 3 4
        shop 1, 120 combinations out of 10 available bikes
        shop 2, 35 combinations out of  7 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 4200
    3 4 3
        shop 1, 120 combinations out of 10 available bikes
        shop 2, 35 combinations out of  7 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 4200
    3 5 2
        shop 1, 120 combinations out of 10 available bikes
        shop 2, 21 combinations out of  7 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 2520
    4 1 5
        shop 1, 210 combinations out of 10 available bikes
        shop 2, 6 combinations out of  6 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 1260
    4 2 4
        shop 1, 210 combinations out of 10 available bikes
        shop 2, 15 combinations out of  6 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 3150
    4 3 3
        shop 1, 210 combinations out of 10 available bikes
        shop 2, 20 combinations out of  6 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 4200
    4 4 2
        shop 1, 210 combinations out of 10 available bikes
        shop 2, 15 combinations out of  6 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 3150
    4 5 1
        shop 1, 210 combinations out of 10 available bikes
        shop 2, 6 combinations out of  6 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 1260
    5 0 5
        shop 1, 252 combinations out of 10 available bikes
        shop 2, 1 combinations out of  5 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 252
    5 1 4
        shop 1, 252 combinations out of 10 available bikes
        shop 2, 5 combinations out of  5 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 1260
    5 2 3
        shop 1, 252 combinations out of 10 available bikes
        shop 2, 10 combinations out of  5 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 2520
    5 3 2
        shop 1, 252 combinations out of 10 available bikes
        shop 2, 10 combinations out of  5 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 2520
    5 4 1
        shop 1, 252 combinations out of 10 available bikes
        shop 2, 5 combinations out of  5 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 1260
    5 5 0
        shop 1, 252 combinations out of 10 available bikes
        shop 2, 1 combinations out of  5 available bikes
        shop 3, no choices, simply remaining bikes...1 combination
        total combinations = 252
    Grand total n = 45507
     
     
  9. Sep 28, 2011 #8
    looks awesome gsal, i will find out the answer soon and let you know!! many many thanks, this defo makes sense to me ...
     
  10. Sep 28, 2011 #9

    uart

    User Avatar
    Science Advisor

    Without reading gsal's above solution I used a somewhat ad-hoc method and got answer of 45486.

    At the moment I cant see that I've missed any combinations so I suspect it is the correct answer. Might post some more details later.
     
  11. Sep 28, 2011 #10
    Also make sure you test small numbers first and work your way up. If you run out of memory with small numbers, there may be something wrong with the code.

    If you are working from small to huge and back down (say 200!/199! ) make sure you work it out before going large or you'll crash (or take a really long time). If you have no choice (like trying to work on huge primes brute force for some reason), break the formula apart and store it. It slows things down, but you won't have to hold the large numbers in RAM.
     
  12. Sep 28, 2011 #11
    uart:

    yeah, I wonder what you have done...and, by the way, it so happens that your solution and mine are exactly 21 apart...recall that I already determined 21 ways to distribute 10 bikes into 3 shops...
     
  13. Sep 28, 2011 #12
    The number of ways a single shop can sell exactly i bikes (of 10 possible types) is
    [tex]\binom{10+i-1}{i}[/tex]
    so the number of ways a shop can sell 0 to 5 bikes is
    [tex]\sum_{i=0}^5 \binom{10+i-1}{i}[/tex]
    and the number of ways 3 shops can sell 0 to 5 bikes each is
    [tex]\left( \sum_{i=0}^5 \binom{10+i-1}{i} \right) ^3[/tex]
     
  14. Sep 28, 2011 #13

    uart

    User Avatar
    Science Advisor

    Hi awkward, that comes out to 3003^3 = 27081081027. Seems a bit high to me.

    gsal. I will post my working as soon as I've got a spare 5 minutes. It's a fairly straight forward sum.
     
  15. Sep 29, 2011 #14

    uart

    User Avatar
    Science Advisor

    I first divided the problem into the various ways that ten bikes can be distributed amongst three shops, without identifying shops or bikes. I then calculated the number of shop permutations for each case (3 or 6) and multiplied it by the number of combinations of bikes for each case. The results are as follows.

    1) 5,5,0 -> 3 C(10,5)
    2) 5,4,1 -> 6 C(10,5) C(5,4)
    3) 5,3,2 -> 6 C(10,5) C(5,3)
    4) 4,4,2 -> 3 C(10,4) C(6,4)
    5) 4,3,3 -> 3 C(10,4) C(6,3)


    Summing those up gave 93 C(10,5) + 105 C(10,4) = 45486.

    Sorry I'm having a lazy latex day today, C(n,r) is the usual n! / ( r! (n-r)! ).
     
  16. Sep 29, 2011 #15
    On the contrary, 2708108102 is a poor, undernourished little number, by comparison with his big brothers in the combinatorics texts.

    Seriously, problems like this are characterized by having solutions whose sizes defy easy comprehension.

    Unless someone comes up with an objection to the method I used, I will consider the problem solved. It is entirely possible, however, that I have misunderstood the problem statement and solved the wrong problem, or at least not the problem intended by the OP. (I do that a lot.)
     
  17. Sep 29, 2011 #16
    uart:

    Just discovered why I am exactly 21 over...there was a left over line in my code from when I was using n for something else...

    Code (Text):

    from math import factorial
    n=0
    for x in range(6):
       for y in range(6):
          for z in range(6):
             if (x+y+z)==10:
               [COLOR="Red"]n=n+1    #   <======  guilty line[/COLOR]
               print "%d %d %d" % (x, y, z)
               n1 = factorial(10)   / ( factorial(x) * factorial(10-x))
               n2 = factorial(10-x) / ( factorial(y) * factorial((10-x)-y))
               print "    shop 1, %d combinations out of 10 available bikes" % n1
               print "    shop 2, %d combinations out of %2d available bikes " % (n2, 10-x)
               print "    shop 3, no choices, simply remaining bikes...1 combination"
               print "    total combinations = %d" % (n1*n2)
               n=n+n1*n2
    print "Grand total n = %d" % n

     
    So, 45486 it is.
     
  18. Sep 29, 2011 #17
    yes, awkward, I think you are doing something incorrectly...in particular, the last equation in your post (from 12:33) seems to assume that each of the 3 shops has access to 5 bikes...but there are only 10 bikes, so for the case when the first shop gets 5 bikes, and the second another 5, the third shop has no bikes at all...so, I think you have failed to consider the full set of equation (refer to my very first post)

    cheers
     
  19. Sep 30, 2011 #18

    uart

    User Avatar
    Science Advisor

    Agreed. :approve:
     
  20. Sep 30, 2011 #19
    Indeed, I misinterpreted your initial post as saying there were 10 _types_ of bicycles rather than 10 bicycles.
     
  21. Oct 1, 2011 #20

    uart

    User Avatar
    Science Advisor

    Ok I see. Yes, your answer looks correct for that variant of the problem.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Distribution (combinations) problem
  1. Combination problem (Replies: 8)

Loading...