Combinatorics : Multinomial Coefficients

Question

What's the relationship between combination and polynomial equation? I mean, I am not able to grasp certain points here or let's say connect them into a whole:

1. Take a question where it's asked that we have to arrange 10 books : 4 of A, 3 of B, 2 of C, and 1 of D in such a way that each book of similar type remain with its own type so like AAAABBBDCCC, etc. Here we are doing 4!*4!*3!*2!*1!.

2. When we take a question of dividing 10 police officers into 3 groups: 10 -> 5,3,2. Here we use 10!/*5!*3!*2!).

3. How many solutions of $x1+x2+x3+...+xn=300$ are possible?

Doubt: What's the difference between 1 & 2? Isn't two equivalent to saying arrange 10 officers like manner of AAAAABBBCC? If we are grouping 10 distinct elements into 3 groups where each group is of same type, then what's the catch here?

Second is what's the similarity between 2 and 3? Isn't three equivalent to saying group 300 distinct element into 3 bags/groups?

I am totally confuse here and I think I cannot move ahead with my GATE preparation if I cannot clear my doubt on combinatorics which in turn would mean no way of doing probability's tricky questions.

EDIT: Here's the images of different questions. How do I differentiate between them?

Comments

1) is not right way of arrangement, 2) is correct

---

Check the edited post.

---

In the first problem, all books are distinct, so instead of A, B, C and D you should denote them by A1, A2, A3, A4, B1, B2 and so on. Now, one valid arrangement is A1A2A3A4C1C2D1B1B2B3. Here if you swap any two books of the same subject, you get a different arrangement. (If the books were not distinct, then the number of arrangements would have been just 4!)

In the second problem let the officers be P1, P2, P3 and so on. One possible grouping is P1P2P3P4P5(group1) P6P7P8(group2) P9P10(group3). Here if you swap any two officers of the same group, you'll still get the same group. Group P1P2P3 is the same as group P3P1P2. Here we are counting groups. So order does not matter. Whereas while counting arrangements, order does matter. 

Isn't three equivalent to saying group 300 distinct element into 3 bags/groups? 
 

Yes thats correct. The difference between 2) and 3) is that in the former you are already given the number of elements each group must have whereas in the latter there's no such restriction. The number of elements in any group can be 0, 1, 2 or even 300.

---

So how did the answer is 4!4!3!2! for first question? Shouldn't it be 10!/(4!3!2!) instead? Isn't the first question exactly similar to second in a sense as if we replace officers with book and patrolling with maths and so on in the second question?

And how to solve the third?

---

First select an ordering of the 4 subjects. This can be done in 4! ways.
Now for each subject, you can arrange the books in x! ways where x is the number
of books of that subject. So total arrangements are 4! * 4! (maths) * 3! (chemistry) * 2! (hisotry) * 1! (other)

Here we count arrangements where order of the elements does matter. So (MATHS1, MATHS2, MATHS4, MATHS3), (CHEMISTRY1, CHEMISTRY2, CHEMISTRY3), (HISTORY1, HISTORY2), (LANGUAGE1)
and (MATHS1, MATHS2, MATHS3, MATHS4), (CHEMISTRY1, CHEMISTRY2, CHEMISTRY3), (HISTORY1, HISTORY2), (LANGUAGE1) are different arragements.
The answer would be 10!/(4!*3!*2!*1!) if the books of a particular subject were all same AND there was no restriction of placing books of same subject contiguously.

In the second problem we are counting groups. Groups are like sets. Set {A, B, C} and set {C, A, B} are the same even though the order of elements is different.
The formula given in the second solution is same as the formula for counting permutations with repititions.
If you still dont understand, try this.
One solution for first problem is M1M2M3M4 C1C2C3 H1H2 L1
Now swap M1 and M4, so it becomes M4M2M3M1 C1C2C2 H1H1 L1
Is this arrangement different? Yes it is.

Now do the same for the second problem one solution is:
    P1P2P3P4P5 P6P7P8 P9P10
Swap P1 and P4, so it becomes P4P2P3P1P5 P6P7P8 P9P10.
Is this different from the above solution? No. all the 3 sets are still the same. Here order does not matter.
The denominator in the expression 10!/(5!*3!*2!) is to count groups obtained by swapping officers from the same group only once.

For the third problem read this and remember the formula. You'll need it very often.
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

---

Thanks. But just one more doubt:

The answer would be 10!/(4!*3!*2!*1!) if the books of a particular subject were all same AND there was no restriction of placing books of same subject contiguously.

How did you figured out that books of particular subjects are not same? The same question for the second question except how the police officers within one group are not different?

---

How did you figured out that books of particular subjects are not same?

Usually it's given in the problem if the objects are identical. If not, just assume they are all different. 

how the police officers within one group are not different?

All 10 police officers are different that's why I have denoted them as P1, P2, P3, ..., P10.

---

I think I kind of figured it out. Tell me if it's correct.

In the first question, the books are not the real category but Maths book, Language book, etc. are 4 different categories, each having their own set of different type of books. So they are taken as separate blocks, hence 4!, and each of those blocks can be arranged in different factorial ways.

In the second question, the real category is one: Police officers, and the each group can be filled any police officer unlike in the above question where math book cannot be put into language group/block but the officers can be put into any 3 category. Hence 10! ways to arrange them and since 5 officers, 3 officers, etc. are in one group; their inner order doesn't matter because they'll be doing the same thing anyway, so doesn't matter who does where.

The same with the third question where the real categories are nationalities not the people. Like a Russian cannot be put into another nationality; hence can be arranged within themselves only to lose their individuality in the name of collectivism, thus no order matters. Maybe I am getting this one wrong as the question is from permutation not combination. Basically it becomes UUURRRR...instead of U1U2U3R1...as they are listed by collective identity; hence doesn't matter if it's R1R2R3 or R2R1R3 as it will still be RRR? Also in this question and the first one, the difference is that here the arrangement like URUR is allowed whereas in the first one, M1L1M2 is not but only M1M2L1. Hence in the first it's 2!*2!*1! whereas here it's 4!/(2!*2!). If in case the first question has the same condition with the fact that the books are same within the category, then it would have been 2!*(2!*1! / 2!).

Did I get it?

 

And if you can tell me which topic within Engineering Mathematics has more score?

---

In the first problem, books of the same subject should be placed together.
So you can consider books from a particular subject as a single entity.
So instead of M1M2M3M4 and C1C2C3, consider them as just M, C, H and L.
This is done to ensure that books from same subject are always together.
So you have 4 objects (4 subjects) and these can be arranged in 4! ways.
Now suppose one of these arrangement is CHML (Chem, History, Maths, Language).
In this arrangement, the Chemistry block can have 3! permutations (arrangements).
Maths block can have 4! permutations (all maths books are different, if they were same there would be only 1 permutation) and so on.
Similarly for other subject arrangements like MHLC, MLCH and others.
So totally there will be 4!(No of Math permutations * No of Chem permutations * No of History permutations * No of Language permutations)
ie, 4!(4!*3!*2!*1!)

Now consider the case where the books of the same subject are identical, so now you have the books as M, M, M, M, C, C, C, H, H and L.
Books of same subject have to be together, s again consider books of each subject as a single entity. So again we have 4 objects M, C, H
and L. You can arrange these 4 objects in 4! ways. This ensures same subject books are together. But consider any subject block, for eg take the Maths block. There are 4 Maths books but they are all the same. So only one arangement is possible, ie, MMMM. So here there's no need to multiply the answer b 4!*3*2!*1!. So the answer in this cae is just 4!.

Now consider the case where the books of same subject are identical AND there's no restriction on the placement of books (same subject books can be away from each other). We have total 10 books so they can be arranged in 10! ways. But since all books of a subject are same, we can have just 1 arrangement for each subject. But here we have counted many arragements more than once.
Consider these 2 arrangements out of the 10! ways we have counted.

MMMM C1CC3 HH L  and MMMM C3CC1 HH L (C1 and C3 are same but they are marked to show difference in their position in the 2 arragements)
They are both included in the 10! ways but only 1 should be included as they are the same.
So to account for this overcounting we have to divide 10! by the number of ways the individual books can be permuted.
So answer is 10!/(4!*3!*2!*1!)

Now try to solve the third problem and ask again if you have some doubts.

 

Second one is correct.

 

Check subjectwise weightage here: http://gatecse.in/mark-distribution-in-gate-cse/

---

I meant the same thing with the first. It's just that I happen to write it as soon as I woke up for I figured it out in my dream.

And thanks.