combinatorics help Log Out | Topics | Search Moderators | Register | Edit Profile

 Ask NRICH » Onwards and Upwards » combinatorics help « Previous Next »

Author Message
nahomyemane
Frequent poster

Post Number: 106
 Posted on Tuesday, 31 December, 2013 - 09:02 pm:

You have $7$ baskets labelled $1-7$ and $7$ IDENTICAL objects. How many ways can you distribute all the IDENTICAL objects? (one basket can take as many IDENTICAL objects as you want)

Bit confused at first. I thought $7^7$ at first but I realised this was a massive overcount since they are not distinct.

Then I thought it had something to do with number of partitions of $7$ using non-negative integers since we only care that they add up to $7$. Using each partition then you could sort out in how many ways you could arrange the numbers to go around $7$ baskets. Once you've done this for every partition you sum them all together.

For example $4+2+1+0+0+0+0$ is a partition. But if you split them in this way you could arrange in the baskets in $\frac{7!}{4!}$ ways since there are $4$ repetitions of $0$

So now do this for every partition and sum all your arrangements to get a total.
But the hard part was finding all the partitions of $7$

So I then decided to do it systematically starting with each of them having an equal number of objects so

$1 1 1 1 1 1 1$

and from here saying if you want to change the configuration you can choose to increase some baskets by an overall say $2$ you must take away $2$ objects- i.e $1$ from each of $2$ baskets

So for an increase of $1$ being cancelled by a decrease of $1$

you get $2 0 1 1 1 1 1$ So I increased one basket by $1$ and decreased another to $0$. The number of ways you could arrange this configuration for $7$ baskets is

$\frac{7!}{5!}= 7*6=42$ (BECAUSE YOU COULD HAVE $2 1 0 1 1 1 1$ or $1 1 0 1 1 2 1$ etc)

For an increase of $2$ total cancelled by a reduction of $2$ baskets to $0$

You have either $3 0 0 1 1 1 1$ which results in $\frac{7!}{4!2!}=105$ ways
or $2 2 0 0 1 1 1$ so you have $\frac{7!}{2!2!3!}=210$ ways

and so I went on this way up to a maximum increase of $6$ cancelled by decrease of $6$ baskets to $0$ i.e the configuration $7 0 0 0 0 0 0$

and added together to get $1716$ (including the one which is $1 1 1 1 1 1$ where there is no increase). However this is slow, boring and unintelligent. I looked at someone else's solution (this is on another maths forum) and here it was:

"You have to randomly put the remaining objects into $7$ baskets. It is the same as dividing $7$ stars by $7$ bars. So, by stars and bars method, we can get the total number of ways in which this can be done = ${7+7-1\choose7-1} = {13\choose6} = 1716$ ."

I dont understand why this works- can someone please help me understand?- Combinatorics is so dangerously fickle with even the slightest change of information in the problem.
triskaidecahedron
Regular poster

Post Number: 32
 Posted on Tuesday, 31 December, 2013 - 09:11 pm:

You might like to look into something called 'delimiters'- just a hint.
Hope this helps.
However, there is also a very nice solution with generating functions. If you are not familiar with the theory of 'generatingfunctionology', then I suggest you learn about the theory first, and then tackle the problem yourself without looking directly at any hints.
~P
Arkan Megraoui
Frequent poster

Post Number: 151
 Posted on Tuesday, 31 December, 2013 - 09:27 pm:

"stars and bars" (as they called it) is basically this:

Given $n$ IDENTICAL objects to put into $r$ different regions, the number of ways you can do it is $\binom{n+r-1}{r-1}$.

This works because we can think of the identical objects and crosses, and the regions as empty spaces divided by bars. Consider the example of $5$ identical objects in $4$ distinct regions. One way to distribute them is:

xx | xxx | |

WHere the first region got 2 objects, the second one got 3 and the last 2 each got none. Another way to distribute them is:

x | | xxx | x

Where in this case, the first region got 1 object, second got none, third got 3 and fourth got 1.

Clearly there's a bijection (prove this) between the nmber of different "stars and bars" arrangements above, and the number of ways there are to split n identical objects into r distinct piles.

So going back to your problem (the one you posted), it remains to count the number of permutations of the "word":

xxxxxxx||||||

which is just $\binom{13}{6}$. (If you don't understand this part I'll explain. Also try and understand why we always have 1 less "bar" than there are regions. (So if there are $r$ regions we only need $r-1$ bars. I think the example I showed above with $5$ objects and $4$ bars should make this clear.)
triskaidecahedron
Regular poster

Post Number: 33
 Posted on Tuesday, 31 December, 2013 - 09:44 pm:

Just to save time- Arkan's Proof is essentially the idea of delimiters.
~P
nahomyemane
Frequent poster

Post Number: 107
 Posted on Wednesday, 01 January, 2014 - 01:14 am:

Firstly Happy New Year.

Secondly: Wow. That's absolutely ingenious. What a brilliant way to think about it.

Thanks to you both especially Arkan Megraoui for your post. I get it now.
Arkan Megraoui
Frequent poster

Post Number: 152
 Posted on Wednesday, 01 January, 2014 - 09:58 am:

Np, and happy new year!