Part 2 - Distribution and Arrangement

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

0

Part 1 : Distribution and Arrangement

Today's topic forms the base of a chunk of problems in Permutations and Combinations. We will break it down into distinct cases and divulge into each one separately. So for an effective learning the topic will be presented in 2 parts. Let's start right away with the part 1.

Case 1 : Objects(Letters) are IDENTICAL while the Groups(Envelopes) are DISTINCT.

Consider 4 distinct envelopes having E1,E2,E3,E4 letters in them with distinct notation used to represent distinct envelopes(while number of letters in them may be same) and 6 identical letters.
                         
We know that :

E1 + E2 + E3 + E4 = 6 = which can be seen as 1 + 1 + 1 + 1 + 1 + 1, six identical objects.
For such an equation,
[When envelopes may be empty]

Number of integral non negative solutions = C(6 + 4 - 1, 4 - 1) = C(9,3) and,
[When envelopes can't be empty]

Number of integral positive solutions = C(6 - 1,4 - 1) = C(5,3)

Case 2 : Objects are DISTINCT as well as groups are DISTINCT.

Consider the case of 4 different envelopes to be filled with 6 distinct letters. Each letter distinctly possesses the option to choose from 4 distinct envelopes.

Hence, total number of permutations possible are : 4*4*4*4*4*4 = 4^6 ways.

"NOTE : We do not restrict the possibility of some of the envelopes being empty in this case. We look at that restrictive arrangement in part 2 as it involves a different concept when both objects and groups are different.
Also,
Here the order in which letters(objects) are put into envelopes(groups) wasn't of any significance.
But what happens when it is of significance? Let's find out with a suitable example.."

Consider the case of 6 rings to be put on your 4 fingers(excluding your thumb). Now the order in which the rings are put on your fingers would hold significance as some of fingers are bound to have more than 1 rings on them. Hence, relative positioning of rings does matter here. Now this can be viewed with 2 perspectives :

                                   
Outlook 1 : Look it as the first ring R1 will have 4 options(any of the fingers). The second ring will have 5 options(3 fingers plus two above or below the already occupied finger) and third ring will have 6 options..and so on.
So we get, for 6 rings, total permutations as : 4*5*6*7*8*9.

Outlook 2 : Consider it as the Case 1 only where order of arrangement matters and the 6 rings(objects,letters) are no more identical. So we need to permute the rings in 6! ways.
Hence we would get total permutations as : C(6 + 4 - 1,4 - 1) * 6! = C(9,3) * 6! = P(9,6)

Doesn't matter how you look at it, both would produce same results as should have been the case.

This brings us to the close of Part 1 of this topic. In part 2, we will look at the other possibilities when it comes down arranging objects into groups that have not yet been explored.


Cheers!
AS

0