How many ways can we send X letter if we can use Y messenger and each messenger gets at least one of the letters 
We have 6 letters to distribute amongst 3 messengers. Assuming that each messenger gets at least one of the letters, how many ways are there to distribute the letters?

My attempt at solution is to consider a simpler case, such as how many ways to send 3 letters if there are 2 messengers and each messenger gets at least one of the letters.  In this case the answer is 6 because I have listed them all, but i have no idea to solve a question like this without listing them.
 A: There are, of course, $3^6 = 729$ possible messenger assignments if we don't care whether one's sitting at the office bored all day.
But quite a few of these assignments have some of the messengers bored.
There are $$\binom{3}{1}1^6 = 3$$ ways to have a single messenger of the three carry all six messages.
For two messengers, we can use a similar calculation, but we must exclude certain duplicates: if I distribute the messages all to Alice and Bob, there's a way to distribute them all to just Alice, and similarly I can distribute them all to just Alice if I say I'm distributing to both Alice and Charlie, so I have to exclude that possibility once so we don't count it twice.
$$\binom{3}{2}2^6-\binom{3}{1}1^6 = 189$$
For three messengers this works the same way: we must exclude the situations in which two or fewer people get all the messages.  Fortunately we just calculated that!
$$\binom{3}{3}3^6-\left(\binom{3}{2}2^6-\binom{3}{1}1^6\right) = \binom{3}{3}3^6-\binom{3}{2}2^6+\binom{3}{1}1^6=540$$
In the second version, you'll note that the sign on the one-working-messenger term is positive.  Another way of thinking about this is that now we've excluded "alice alone" twice, so it appears -1 times in the final count, so we have to include it again.  This alternation of including and excluding things is called the Inclusion-Exclusion Principle.  Using it, we can generate a general form for the answers to this type of problem:
If we have $m$ messengers and $\ell$ letters, then the number of ways we can distribute the letters to the messengers without any of the messengers getting no letters and becoming bored is $$\sum_{k=1}^{m}(-1)^{m-k}\binom{m}{k}k^\ell$$
It looks like this value is $m!\times S(n,m)$, where $S$ is the Stirling Number of the Second Kind.  OEIS has this sequence as A019538.
A: We apply the Principle of Inclusion and Exclusion.  There are $3^6$ ways to distribute the letters if we ignore the constraint. We seek to exclude the cases in which one or more messengers gets no letters.  First we exclude all those distributions in which one specified messenger gets no letters.  If, say, we exclude Messenger $A$ then there are $2^6$ ways to distribute.  As there are three messengers, we first subtract off $3\times 2^6$.  But now we've removed too much...to be precise, we have twice excluded the cases in which one messenger gets all the letters.  There are $3$ such cases.  Thus the answer is $$3^6-3\times 2^6+3=540$$
Sanity Check:  If we did your special case of $3$ letters and $2$ messengers by this method, we'd get $$2^3-2=6$$  as desired.
A: If you want to ensure that each messenger sends at least one letter, then you need to use inclusion/exclusion principle. For example, given $6$ letters and $3$ messengers:


*

*Include the number of ways in which at most $\color\red3$ messengers work: $\binom{3}{\color\red3}\cdot\color\red3^6=729$

*Exclude the number of ways in which at most $\color\red2$ messengers work: $\binom{3}{\color\red2}\cdot\color\red2^6=192$

*Include the number of ways in which at most $\color\red1$ messengers work: $\binom{3}{\color\red1}\cdot\color\red1^6=3$


Hence the answer is $729-192+3=540$.

For the general case of $M$ messengers and $L$ letters (assuming $M \geq L$):
$$\sum\limits_{n=0}^{M-1}(-1)^n\cdot\binom{M}{M-n}\cdot(M-n)^L$$
