Division and distribution of distinct objects.
Permutation and combination Formula
(1) Distribution of n distinct objects into m groups is $m^n$
(2) Distribution of n distinct objects into m groups where group size is fixed $$=(\frac{n!}{(r_1!)(r_2!)(r_3!)…..(r_m!)})$$
(3) Distribution of (mn) distinct objects into m groups such that each group gets n objects if group are marked is $\frac{(mn)!}{(n!)^m}$ , when groups are unmarked is $\frac{(mn)!}{(n!)^m.m!}$
One of very important concept of permutation and combination is division and distribution of distinct of objects into groups.
There are many questions which are applications of distribution of objects into groups few of these which we have in discussion forum .
Objects can be identical or distinct , based on that the distribution of objects are classified as :-
(1) Distribution of distinct objects.
(2) Distribution of identical objects.
Lets discuss the derivation of permutation and combination formula for Distribution of distinct object
(1). Distribution of n distinct objects into m distinct groups , such that any group can get any number of objects ( i.e from 0 to all n objects ).
Let $a_1,a_2,a_3,……,a_n$ be distinct objects to be distributed into m distinct (marked ) groups .
Number of ways in which a particular object $a_i$ can be distributed in any one of the group is m ways.
Hence for all different i = 1,2,3,….,n each of the object $a_i$ can be distributed into one of the group in m ways
Thus all n distinct objects can be distributed into m distinct ( marked ) groups in $$=\,\,\,\underbrace{ m.m.m……..m}_{n\,\text{times}}$$
Hence Number of ways in in which n distinct objects can be distributed into m distinct ( marked ) groups is $ m^n $
Illustration 1 :- The number of ways in which 10 different toy can be distributed into 5 children such that any child can get any number of toys.
Solution : – In the given Illustration toys are 10 distinct objects and groups are children.
1st toy can be given to one of the child in 5 ways , Also 2nd toy can be given to one of child in 5 ways since any child can get any number of toys, similarly each one of 10 can be distributed in 5 ways.
Hence all 10 toy can be distributed to 5 children in $\underbrace{5.5.5…5}_{10\,times}\,=\,5^{10}$
For more Illustration refer to questions in discussion forum
(2) Number of ways in which n distinct objects can be distributed to m distinct ( marked ) groups , such that each group gets a fixed number of objects ( let $i^{th}$ group gets $r_i$ number of objects and $\sum {r_i}=n$ )
The distribution will that first from n distinct objects $r_1$ will be selected and given to group 1 , from rest i.e ( n – $r_1$ ) distinct objects $r_2$ are selected , given to group 2 and from rest $r_3$ will be selected and given to group 3 and it go on this way till all the objects are distributed in all m groups.
Hence number of ways is $={n \choose r_1}{{n-r_1} \choose r_2}{{n-r_1-r_2} \choose r_3}…….{r_m \choose r_m}$
$$=(\frac{n!}{r_1!(n-r_1)!}).(\frac{(n-r_1)!}{r_2!(n-r_1-r_2)!})…..(\frac{(n-r_1-r_2…r_{m-1})!}{r_m!(r_m)!})$$
$$=(\frac{n!}{(r_1!)(r_2!)(r_3!)…..(r_m!)})$$
Illustration 2 :- Find number of ways in which 10 different toy can be distributed to 4 children $A_1 , A_2,A_3,A_4$ such that child $A_i$ is gets i number of toys $\forall i=1,2,3,4 $ .
Solution : In above illustration objects are toys and groups are children be groups i.e n = 10 and m = 5 .
From 10 toys one is selected in ${10 \choose 1}$ ways and given to child $A_1$, and from rest 9 toys two are selected in ${9 \choose 2}$ and given to second child $A_2$ , Similarly it will go on for all four children.
Hence total number ways in which 10 different toys can be distributed into 4 children are =${10 \choose 1}{9 \choose 2}{7 \choose 3}{4 \choose 4}$
$$=(\frac{10!}{1!.2!.3!.4!})$$
(3) Number of ways in which (mn) distinct objects be distributed into m number of groups such that each group gets n objects.
(a) Groups are distinct ( marked )
In this case $r_1=r_2=r_3=……=r_m=n$
Hence number of distributions are = $\frac{(mn)!}{(n!)^m}$
(b) Groups are identical ( Unmarked )
Since groups are identical hence if same set of objects in group are interchanged between groups are then distribution remain same.
Hence number of distribution = $\frac{(mn)!}{(n!)^m.m!}$
Illustration 3 :- Find number of ways in which 52 cards from a pack of card be distributed. $$ $$ (a) To 4 players such that each gets 13 cards. $$ $$ (b) Into 4 parts such that each part has 13 cards.
Solution :- (a) Distribution to players is a case of distribution into distinct groups.
Hence number of distributions = $\frac{52!}{(13!)^4}$
(b) Distribution into four parts is a case of distribution of objects into four identical groups.
Hence number of distribution = $\frac{52!}{(13!)^4.4!}$
For more Illustration refer to questions in discussion forum
(4) (a) Distribution of distinct objects into distinct group in which the order of distribution of object is considered.
Number of ways in which ‘n’ distinct object be distributed into ‘m’ groups such that order of objects in distribution in any group is considered and any group can have any number of objects.
Let $a_1,a_2,a_3,….,a_n$ be distinct objects to be distributed into m groups , order in which objects go into any group is considered.
The method we adopt is cutting the array of arrangement of n distinct object at (m-1) places , such that number objects in that order between $i^{th}$ cut and $(i+1)^{th}$ cut are put into $(i+1)^{th}$ group where $1\le i \le (m-2)$ and number of object in that order after $(m-1)^{th}$ cut is put into $m^{th}$ group.
Multiple cut can be done at a place in an array then those group remain empty.
Hence along with n distinct objects considered (m-1) identical C.
Number of distribution is = Number of arrangements of (n+m-1) objects of which n are distinct and (m-1) are identical C $=\frac{(n+m-1)!}{(m-1)!}$
Illustration 4 :- Find number of ways in which 10 people can enter into a room through 3 different doors.
Solution :- 10 people entering through 3 doors , where even if same people enter through each door but if through any door same people enter in different order will be different entry .
Hence number of ways are $=\frac{(10)!}{2!}=5.9!$
(4) (b) Number of ways in which n distinct objects into m distinct group such that order of distribution of object is considered and any group can get any number of objects and each group get atleast one object .
Let $a_1,a_2,a_3,….,a_n$ be distinct objects to be distributed into m groups , order in which objects go into any group is considered.
Like distribution discussed in case (a) , we arrange n objects at n places and from (n-1) spaces between objects select any (m-1) to insert identical C such that no two C is together.
Therefore Number of distribution is $=n!{{n-1} \choose {m-1}}$
Illustration 5 :- Find number of ways in which 10 people enter into room through 3 doors such that at least one person enter trough each door.
Solution :- Total number of ways in which 10 people can enter through 3 doors is $=(10)!{9 \choose 2}=36.(10)!$
For permutation and combination formula of distribution of identical objects.