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