Free help with homework

Why join Brainly?

  • ask questions about your assignment
  • get answers with explanations
  • find similar questions

How many ways are there to distribute 20 district object into 10

distinct boxes with:
i) At least three empty box.
ii) No empty box.



This Is a Certified Answer

    This is not as straight forward as it seems.  We cannot solve like,  distribute first one object into each box and then the remaining 10 objects as we like with all possibilities among the boxes.

     The way of partitioning given n distinct objects into k identical (unlabeled) bins is given by Sterling numbers of second kind.    We have to put at least one object in one box.
                   {  n  }
     S(n, k) = {      }      n>=1,   k>=1,    n>=k
                   {  k  }

S_n^{(k)}=S(n,k)=\frac{1}{k!}\Sigma_{j=0}^{k}\ (-1)^{k-j}\ {}^kC_j\ j^n 

    The number of ways to distribute n distinct objects into k distinct labeled boxes (at least one object in each box) is given by  k! * S(n, k).   This is because  we can permute the k boxes in k! ways.  let us call these numbers as :  f(n, k) = k! * S(n, k)

We can compute these sterling numbers for different n and k.
  S(0,0) = 0.  S(1,1) =1,    S(n,1) = 1      S(n, n) = 1

   f(0,0) = 0    f(1,1) = 1      f(n , 1) = 1     f(n, n) = n !
   f(n, 2)  = 2^n  - 2
There is a recurrence relation among these numbers.

  S(n+1, k) =  k S (n, k) + S(n, k-1)

  f(n+1, k) = k [ f(n, k) + f(n , k-1) ]

Thus we can find their values. with at least one object in each of 10 boxes:

f(20,10)=-{}^{10}C_1*1^{20}+{}^{10}C_2*2^{20}-{}^{10}C_3*3^{20}+{}^{10}C_4*4^{20}\\.\&#10; \ \ \ \ -{}^{10}C_5*5^{20}+{}^{10}C_6*6^{20}-{}^{10}C_7*7^{20}\\. \ \ \&#10; \ \ \ \ &#10;+{}^{10}C_8*8^{20}-{}^{10}C_9*9^{20}+10^{20}\\\\=21473732319740100000\\=2.1473*10^{19}

The result should actually be a multiple of 10!..
For part 1 of the question:  with at least 3 empty boxes.

Number of the ways with all distinct objects being distributed in any fashion, with any number of objects in any distinct box.  = 10^20
   as for each object there are 10 ways, by putting it in any of the boxes.

Ways of 20 distinct objects being put in 10 distinct boxes, with one box empty:
    10C1  * f(20, 9)  = 10 * f(20, 9)

Ways of 20 distinct objects being put in 10 distinct boxes, with two boxes empty:
    10C2  * f(20, 8)  = 45 * f(20, 8)
So the answer for distribution of 20 objects in 10 boxes (distinct) with at least 3 boxes empty will be =   10^20 - 10 f(20, 9) - 45 *f(20,8)

This number will also be in the range of 10^19.
1 5 1
click on thanks button above;;select best answer
The Brain
  • The Brain
  • Helper
Not sure about the answer?
Learn more with Brainly!
Having trouble with your homework?
Get free help!
  • 80% of questions are answered in under 10 minutes
  • Answers come with explanations, so that you can learn
  • Answer quality is ensured by our experts