counting number of surjections when order matters with in each subset Question: On a ship, signals are transmitted by putting flags on flagpoles (the order of the flags on each pole is important). There are 10 different flags and 3 different flagpoles. All of the flags are used. Each flagpole must have at least one flag. How many orderings are there?
 A: Let's first calculate the number of ways to do this problem when the order of the poles matters. 
In this case, we order the 3 poles in some way, and thus each signal corresponds to one permutation of the 10 flags: First the first flag from the first pole, then the second flag from the first pole, until the last flag from the first pole, then the first flag from the second pole a.s.o.
However, each permutation of the 10 flags corresponds to multiple signals, because to get back the signal from the permutation one needs to decide after which flag  the first and second pole end. Since each pole cannot be empty, the last flag of each pole is well defined, and the second pole cannot end after the 10th flag. So we have $9 \choose 2$ ways to choose the unorderd pair of ending flags for the first and second pole from the 1st to 9th flag.
That means, if pole order matters, there are exactly ${9 \choose 2}10!$ possible signals. 
But since all flags (and thus the flags on each pole) are different, finding the number of signals when pole order doesn't matter means just deviding the above number by $3!=6$.
That means the answer to the stated problem is that ${{9 \choose 2}10! \over 3!} = 19353600$ different signals exist.
A: First, answer the question without the "all flagpoles must be used" restriction. Edit: I will also first assume that the order of the poles does matter.
Imagine placing the flags one at a time. 


*

*There are $3$ places you can put the first flag, on any pole. 

*There are then $4$ places you can put the second flag: either you can put it on top of any of the three poles, or just below the first flag. 

*There are then $5$ places you can put the third flag.

*$\vdots$
In general, there are  $3+i-1$ places you can put the $i^{th}$ flag; either on top of any of the three poles, or just below any of the $i-1$ previous flags. Therefore, the number of ways to place the flags is
$$
3\cdot 4\cdot 5\cdots \cdot 12. 
$$
What if all flagpoles must be used (and the order of the poles still matters)? There are two ways to reduce this to the previous case:


*

*Choose the flags on the bottom of the poles first, then place the remaining $7$ flags without restriction.

*Use principle of inclusion exclusion, taking all arrangements, and subtracting the bad ones where some flagpole is empty, then adding back in the doubly subtracted arrangements, etc. 
Edit: I leave the details of carrying out either of the last two bullets to you. Finally, since we want the order of the poles to not matter, we must divide by $6!$. 
