This seems like something I should know, but I’ve been struggling with it and it’s driving me nuts. If you have *p* processes each involving *s* steps, how do you calculate the number of possible orderings for all steps across all processes? Any formula or algorithm requiring no more than *p*s* steps (factorial counts as one step) would be appreciated.

I found what I think is an answer by means of what amounts to genetic programming – i.e. experimentation with different algorithms involving p and s, factorials and exponents, tested against a set of known results calculated by brute-force enumeration. It is:

fact(p*s) / fact(s)**p

I don’t even pretend to understand why this seems to yield correct results, but so far it does

Discussing the problem with Mr. Packer helped to clarify why this formula works. You start with (p*s)! possible orderings of the process/step tuples – including illegal orderings. The requirement to execute steps for one process eliminates all but one of each s! possibilities out of whatever existed before the constraint was applied. The important thing is that the constraint imposed by each process is totally orthogonal to that imposed by each other process (they apply to disjoint sets of tuples). Therefore, dividing by s! for each node makes sense.