Part 1 and Part 2 can also be read individually though it's advisable to read them in order just to maintain the flow. We discussed two of the cases in part 1 in detail and now we move further along to the remaining cases. Let's begin..
Case 3 : When letters(objects) are DISTINCT and envelopes(groups) are IDENTICAL
Let's assume there are 5 distinct letters and 3 identical envelopes for our illustration.
Here we have several different approaches, each being a concept in its own right. So let's take two of the most utilized ones individually.
Method 1 : Manual Case Making
You form different cases distributing the total number of letters in the given number of segments(envelopes)
and count the permutations. Here, selection of distinct letters is important while the order in which they picked is not since the groups(envelopes) are identical. Hence, we calculate as following :
5,0,0 : C(5,5) = 1 way
4,1,0 : C(5,4) * C(1,1) = 5 ways
3,2,0 : C(5,3) * C(2,2) = 10 ways
3,1,1 : C(5,3) * C(2,1) * C(1,1) /2 = 10 ways [ We divide by 2 as envelopes are identical so the selection amongst last two letters is nullified as it doesn't matter whether letter L4 goes into envelope 2(E) and L5 in envelope 3(E) OR letter L4 goes into envelope 3(E) and so on..as all envelopes are identical i.e. E(say)]
2,2,1 : C(5,2) * C(3,2) * C(1,1) /2 = 15 ways [ Similar explanation as above case ]
So, in total we get 41 different permutations.
Method 2 : Stirling Number of second kind
Without going into unnecessary details, I will directly get to the general expansion of a Stirling number of second kind in context with our discussion and the formula for our topic.
S(n,r) = [r^n - C(r,1)*(r - 1)^n + .... up till term equivalent to zero]/r!
where n is the number of objects(letters) and r is the number of groups(envelopes).
and the total arrangements of n distinct objects into r identical groups is given by :
S(n,1) + S(n,2) + ... + S(n,r) = S(5,1) + S(5,2) + S(5,3)
= [1^5]/1! + [2^5 - C(2,1)*1^5]/2! + [3^5 - C(3,1)*2^5 + C(3,2)*1^5]/3!
= 1 + 30/2! + 150/3! = 1 + 15 + 25 = 41 ways
Case 4 : When letters(objects) are IDENTICAL as well as the groups(envelopes) are IDENTICAL
You simply count the number of ways in which the n objects can be segregated in r groups. So basically the number of cases in your method 1 of Case 3 becomes the answer to this situation of distribution.
Hence, simply , (5,0,0) ; (4,1,0) ; (3,2,0) ; (3,1,1) ; (2,2,1) i.e there are 5 such permutations possible and this becomes your answer.
Case 5 : When both envelopes and letters are distinct and no envelopes can be left empty
This is a classic example of the Inclusion-Exclusion principle.
Let's say we have the 4 distinct envelopes and 6 distinct letters again as in Case 1[described in Part 1].
Now when we take 4^6 arrangements giving each letter a choice of 6 envelopes then there would be a case when we include amongst these, the cases when one of the envelopes stays empty. So we need to remove these cases for our Case 5 requirement. How do we do that?
We select 1 out of the 4 envelopes and arrange the 6 letters in the remaining 3 envelopes normally. So, that becomes C(4,1)*3^5.
But what happened here is when you did 3^5 you had those cases where 1 of those 3 envelopes were empty and you already had 1 selected empty giving you two empty envelopes while intent was to remove the cases where 1 envelope had stayed empty. So you need to add them back.
Again, how do you do that? --> C(4,2)*2^6
With the same process of thought, you realize that now you need to remove the cases with 3 empty..and so on until the whole set is exhausted leaving no such duplicate removals.
Hence, what we get as a result for this situation is the following formula :
r^n - C(r,1)*(r - 1)^n + C(r,2)*(r - 2)^n - ... till the 0 value term.
So, for our example, feeding in the values we ll get :
4^6 - C(4,1)*3^6 + C(4,2)*2^6 - C(4,3)*1^6
That ends the various possibilities that exist in questions of distribution of n items into r groups and I hope you were able to gain the maximum and now could move onto practicing problems on this topic domain. Leave in comments in case of doubts or reviews as to how I could make this better for you.
Rate,Like & Share the posts and the blog if you like the work here.
Cheers!
AS
Case 3 : When letters(objects) are DISTINCT and envelopes(groups) are IDENTICAL
Let's assume there are 5 distinct letters and 3 identical envelopes for our illustration.
Here we have several different approaches, each being a concept in its own right. So let's take two of the most utilized ones individually.
Method 1 : Manual Case Making
You form different cases distributing the total number of letters in the given number of segments(envelopes)
and count the permutations. Here, selection of distinct letters is important while the order in which they picked is not since the groups(envelopes) are identical. Hence, we calculate as following :
5,0,0 : C(5,5) = 1 way
4,1,0 : C(5,4) * C(1,1) = 5 ways
3,2,0 : C(5,3) * C(2,2) = 10 ways
3,1,1 : C(5,3) * C(2,1) * C(1,1) /2 = 10 ways [ We divide by 2 as envelopes are identical so the selection amongst last two letters is nullified as it doesn't matter whether letter L4 goes into envelope 2(E) and L5 in envelope 3(E) OR letter L4 goes into envelope 3(E) and so on..as all envelopes are identical i.e. E(say)]
2,2,1 : C(5,2) * C(3,2) * C(1,1) /2 = 15 ways [ Similar explanation as above case ]
So, in total we get 41 different permutations.
Method 2 : Stirling Number of second kind
Without going into unnecessary details, I will directly get to the general expansion of a Stirling number of second kind in context with our discussion and the formula for our topic.
S(n,r) = [r^n - C(r,1)*(r - 1)^n + .... up till term equivalent to zero]/r!
where n is the number of objects(letters) and r is the number of groups(envelopes).
and the total arrangements of n distinct objects into r identical groups is given by :
S(n,1) + S(n,2) + ... + S(n,r) = S(5,1) + S(5,2) + S(5,3)
= [1^5]/1! + [2^5 - C(2,1)*1^5]/2! + [3^5 - C(3,1)*2^5 + C(3,2)*1^5]/3!
= 1 + 30/2! + 150/3! = 1 + 15 + 25 = 41 ways
Case 4 : When letters(objects) are IDENTICAL as well as the groups(envelopes) are IDENTICAL
You simply count the number of ways in which the n objects can be segregated in r groups. So basically the number of cases in your method 1 of Case 3 becomes the answer to this situation of distribution.
Hence, simply , (5,0,0) ; (4,1,0) ; (3,2,0) ; (3,1,1) ; (2,2,1) i.e there are 5 such permutations possible and this becomes your answer.
Case 5 : When both envelopes and letters are distinct and no envelopes can be left empty
This is a classic example of the Inclusion-Exclusion principle.
Let's say we have the 4 distinct envelopes and 6 distinct letters again as in Case 1[described in Part 1].
Now when we take 4^6 arrangements giving each letter a choice of 6 envelopes then there would be a case when we include amongst these, the cases when one of the envelopes stays empty. So we need to remove these cases for our Case 5 requirement. How do we do that?
We select 1 out of the 4 envelopes and arrange the 6 letters in the remaining 3 envelopes normally. So, that becomes C(4,1)*3^5.
But what happened here is when you did 3^5 you had those cases where 1 of those 3 envelopes were empty and you already had 1 selected empty giving you two empty envelopes while intent was to remove the cases where 1 envelope had stayed empty. So you need to add them back.
Again, how do you do that? --> C(4,2)*2^6
With the same process of thought, you realize that now you need to remove the cases with 3 empty..and so on until the whole set is exhausted leaving no such duplicate removals.
Hence, what we get as a result for this situation is the following formula :
r^n - C(r,1)*(r - 1)^n + C(r,2)*(r - 2)^n - ... till the 0 value term.
So, for our example, feeding in the values we ll get :
4^6 - C(4,1)*3^6 + C(4,2)*2^6 - C(4,3)*1^6
That ends the various possibilities that exist in questions of distribution of n items into r groups and I hope you were able to gain the maximum and now could move onto practicing problems on this topic domain. Leave in comments in case of doubts or reviews as to how I could make this better for you.
Rate,Like & Share the posts and the blog if you like the work here.
Cheers!
AS
No comments:
Post a Comment