Distribution (combinations) problem

[holyGrill]

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

 

[gsal]

The way I understood the problem...the number of combinations is small.

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

0 \leq x \leq 5

0 \leq y \leq 5

0 \leq z \leq 5

and

x+y+z=10

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

 

[uart]

Are the bikes/shops distinguishable?

 

[holyGrill]

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.

 

[gsal]

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! ?

 

[holyGrill]

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 ?!

 

[gsal]

How about this?

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

 

[holyGrill]

looks awesome gsal, i will find out the answer soon and let you know! many many thanks, this defo makes sense to me ...

 

[uart]

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

At the moment I can't see that I've missed any combinations so I suspect it is the correct answer. Might post some more details later.

 

[cone]

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.

 

[gsal]

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...

 

[awkward]

The number of ways a single shop can sell exactly i bikes (of 10 possible types) is
\binom{10+i-1}{i}
so the number of ways a shop can sell 0 to 5 bikes is
\sum_{i=0}^5 \binom{10+i-1}{i}
and the number of ways 3 shops can sell 0 to 5 bikes each is
\left( \sum_{i=0}^5 \binom{10+i-1}{i} \right) ^3

 

[uart]

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.

 

[uart]

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)! ).

 

[awkward]

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

[snip]

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.)

 

[gsal]

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...

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:
           n=n+1    #   <======  guilty line
           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.

 

[gsal]

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

 

[uart]

So, 45486 it is.

Agreed.

 

[awkward]

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

Indeed, I misinterpreted your initial post as saying there were 10 _types_ of bicycles rather than 10 bicycles.

 

[uart]

Indeed, I misinterpreted your initial post as saying there were 10 _types_ of bicycles rather than 10 bicycles.

Ok I see. Yes, your answer looks correct for that variant of the problem.

 

[awkward]

OK, now that I understand the problem statement, here is a different approach (not that there is anything wrong with solutions by gsal and uart).

Let's generalize the problem and say we have r bicycles. Let a_r be the number of ways to distribute the bicycles to 3 shops with no more than 5 bicycles per shop. Define
f(x) = \sum_r \frac{1}{r!} a_r x^r
which is an "exponential generating function". It helps to have had some experience with these functions, but you can eventually convince yourself that
f(x) = \left( \sum_{i=0}^5 \frac{1}{i!} x^i \right) ^3

Expanding (here it helps to have a computer algebra package, or you can use Wolfram Alpha), we find the coefficient of (1/10!) x^{10} is
a_{10} = 45,486
which is in agreement with the previous answers.