Distribution (combinations) problem

1. Sep 28, 2011

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

2. Sep 28, 2011

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

3. Sep 28, 2011

uart

Are the bikes/shops distinguishable?

4. Sep 28, 2011

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.

Last edited: Sep 28, 2011
5. Sep 28, 2011

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

6. Sep 28, 2011

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

7. Sep 28, 2011

gsal

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

8. Sep 28, 2011

holyGrill

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

9. Sep 28, 2011

uart

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.

10. Sep 28, 2011

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.

11. Sep 28, 2011

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

12. Sep 28, 2011

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

13. Sep 28, 2011

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.

14. Sep 29, 2011

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

15. Sep 29, 2011

awkward

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

16. Sep 29, 2011

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

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.

17. Sep 29, 2011

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

18. Sep 30, 2011

uart

Agreed.

19. Sep 30, 2011

awkward

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

20. Oct 1, 2011

uart

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

21. Oct 1, 2011

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.