How many ways to put n elements into k sets, plus in each set the elements orders matter?

Question

I tried to generalize the question, but I have a concrete example to help specify the problem.

So let's say there's a group of tourists who like to visit 20 monuments of a city under 4 days. How many different ways can they do this, if they're able to visit all monuments in a day if they want so, and it matters, that on a given day in what order they visit them?

Answer 1

The problem reduces to partitioning of n elements into $k$ parts, which is by stars and bars $$ \binom{n+k-1}{n}. $$ The order can be imposed by all possible permutations of the $n$ elements. Thus the final answer is: $$ n! \binom{n+k-1}{n}. $$

Answer 2

You can reduce this to a stars and bars problem, where you have $n$ stars or $n$ monuments and $k$ bars or $k$ days. Then, the ways you could partition your $n$ monuments into $k$ days is ${n + k -1}\choose{k-1}$. If you care about the order in which you visit the monuments in any given day, then count the possible ways you can arrange $n$ monuments: $n!$. By the multiplication rule, you have $n!{{n + k -1}\choose{k-1}}$. That is, you can first decide the order in which to visit monuments, and then decide on which days you want to visit them.