number of instruction interleaving If there are n threads with m instructions in each thread, when these threads are run concurrently how many possible interleavings in instruction execution are possible?
 A: There are altogether $nm$ instructions. There are $\binom{nm}m$ ways to pick which $m$ slots in the sequence of $nm$ instructions are occupied by the $m$ instructions in thread $1$. Once those are chosen, there are $\binom{nm-m}m$ ways to pick which of the $m$ remaining slots are filled by the instructions in thread $2$, then $\binom{nm-2m}m$ ways to pick the $m$ slots for thread $3$, and so on. In general, for thread $k$ you’ve already filled $(k-1)m$ slots, so there are $\binom{nm-(k-1)m}m$ ways to pick the slots for thread $k$. The total number of interleavings is the product of these numbers, $$\begin{align*}
&\binom{nm}m\binom{nm-m}m\binom{nm-2m}m\dots\binom{2m}m\binom{m}m =\\\\
&\frac{(nm)!}{m!(nm-m)!}\cdot\frac{(nm-m)!}{m!(nm-2m)!}\cdot\frac{(nm-2m)!}{m!(nm-3m)!}\cdot\dots\cdot\frac{(2m)!}{m!m!}\cdot\frac{m!}{m!}=\\\\
&\frac{(nm)!}{(m!)^n}.
\end{align*}$$
This multinomial coefficient is also written $${nm \choose m,m,\ldots,m},$$ where there are $n$ entries in the bottom row.
A: There are $(nm)!$ ways to order the full set of $nm$ instructions.  This is a product of $m!$ ways to order the instructions in each individual thread (i.e., a factor of $(m!)^n$), times the requested number of ways to interleave the threads.  We conclude that there are
$$
\frac{(nm)!}{(m!)^n}
$$
ways to interleave the threads.
An alternate derivation is to start with $nm$ slots for the instructions, then choose $m$ in which to place the first thread's instructions, $m$ of the remaining slots in which to place the second thread's instructions, and so on.  This gives the result
$$
{{nm}\choose{m}}\times{{nm-m}\choose{m}}\times {...} \times{{2m}\choose{m}},
$$
or
$$
\frac{(nm)!}{m!(nm-m)!}\times\frac{(nm-m)!}{m!(nm-2m)!}\times{...}\times\frac{(2m)!}{m!m!},
$$
which is the same as before: the only terms that don't cancel are the $(nm)!$ in the numerator and the $n$ copies of $m!$ in the denominator.
