How many ways can the statements of 2 processes be interleaved

Question

I would like to know, how many ways can the statements of 2 processes be interleaved? I know what interleaving is but I can't seem to derive a formula.

Answer 1

It's the Binomial Coefficient and it is responsible for the combinatorial explosion of possible interleavings that makes analysis of multithreaded code very challenging if not impractical.

So given process P1 with N instructions and process P2 with M instructions you get N+M over N, i.e. (N+M)! / N!M!, interleavings, which grows exponentially even for relatively small number of instructions per process. For instance, if you have two processes with five instructions each, the number of possible interleavings is 252. Most real-world applications have, however, millions of instructions, and often more than merely two processes (or threads) involved.