1
$\begingroup$

$6$ letters are to be posted in three letter boxes.The number of ways of posting the letters when no letter box remains empty is?

I solved the sum like dividing into possibilities $(4,1,1),(3,2,1)$ and $(2,2,2)$ and calculated the three cases separately getting $90,360$ and $90$ respectively.

What I wanted to know is there any shortcut method to solve this problem faster?Can stars and bars be used?How?

Or can the method of coefficients be used like say finding coefficient of $t^6$ in $(t+t^2+t^3+t^4)^3$.Will that method work here?

$\endgroup$
  • $\begingroup$ This is not a combination with repetition since the letters are different. $\endgroup$ – N. F. Taussig Jan 13 '16 at 12:37
  • $\begingroup$ When did I say it is combination with repetition ? $\endgroup$ – user220382 Jan 13 '16 at 12:41
  • $\begingroup$ When you asked about using "stars and bars." $\endgroup$ – N. F. Taussig Jan 13 '16 at 12:43
3
$\begingroup$

Inclusion-Exclusion.

$3^6$ ways total.
$2^6$ ways if you only mail to $1\&2,2\&3$ or $1\&3$, subtract them off (3 alike cases).
$1^6$ way if you only mail to $1$, or to $2$, or to $3$, add them back in because they were subtracted twice (agai, 3 cases all alike).

$3^6 - 3 \cdot 2^6 + 3 \cdot 1^6$

$\endgroup$
2
$\begingroup$

Stirling numbers of the second kind: your particular example of six letters and 3 letterboxes has a solution of $3! \,S_2(6,3) = 6 \times 90 =540$ possible surjections, the same as the result you found

Using exponential generating functions, you could find the coefficient of $x^6$ in the expansion of $(e^x-1)^3$ and multiply that by $6!$ to get $\frac34 \times 720= 540$

$\endgroup$
  • $\begingroup$ Going over my head :-P! Anyway thanks $\endgroup$ – user220382 Jan 13 '16 at 12:34
0
$\begingroup$

Ways of dividing in 3 and 3 are 6!/3!3!=20. 3 are directly given in the letter box . 3 are left number of ways from that is 3*3*3=27 as there are three options for each letter. Total ways =27*20=540

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy