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 [inline]7[/inline] baskets labelled [inline]1-7[/inline] and [inline]7[/inline] 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 [inline]7^7[/inline] 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 [inline]7[/inline] using non-negative integers since we only care that they add up to [inline]7[/inline]. Using each partition then you could sort out in how many ways you could arrange the numbers to go around [inline]7[/inline] baskets. Once you've done this for every partition you sum them all together.

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

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 [inline]7[/inline]

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

[inline]1 1 1 1 1 1 1[/inline]

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

So for an increase of [inline]1[/inline] being cancelled by a decrease of [inline]1[/inline]

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

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

For an increase of [inline]2[/inline] total cancelled by a reduction of [inline]2[/inline] baskets to [inline]0[/inline]

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

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

and added together to get [inline]1716[/inline] (including the one which is [inline]1 1 1 1 1 1[/inline] 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 [inline]7[/inline] baskets. It is the same as dividing [inline]7[/inline] stars by [inline]7[/inline] bars. So, by stars and bars method, we can get the total number of ways in which this can be done = [inline]{7+7-1\choose7-1} = {13\choose6} = 1716 [/inline] ."

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 [inline]n[/inline] IDENTICAL objects to put into [inline]r[/inline] different regions, the number of ways you can do it is [inline]\binom{n+r-1}{r-1}[/inline].

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 [inline]5[/inline] identical objects in [inline]4[/inline] 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 [inline]\binom{13}{6}[/inline]. (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 [inline]r[/inline] regions we only need [inline]r-1[/inline] bars. I think the example I showed above with [inline]5[/inline] objects and [inline]4[/inline] 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! :-)

Add Your Message Here
Posting is currently disabled in this topic. Contact your discussion moderator for more information.

Topics | Last Day | Last Week | Tree View | Search | Help/Instructions | Program Credits Administration