**PROBLEM:** Count the number of ways in which atomic operation(s) of **n** different processes can be interleaved. A process may crash mid way before completion.

Suppose there are a total of **n** different processes – P1, P2, P3 …. , Pn.

Each process can have a variable number of atomic operation(s) that constitutes that process, but it should have at least one operation.

**EXAMPLE**

Consider two processes, P1 and P2

- P1: 1o1; 1o2; 1o3; 1o4; 1o5; 1o6;
- P2: 2o1; 2o2; 2o3;

where 1o1 denotes first operation of process P1.

**Attempt**:

Fix position of all operations of process P1, then count the number of ways in which the operations of process P2 can be placed in empty positions( __ ) created between operations of process P1, as shown below:

`__ 1o1 __ 1o2 __ 1o3 __ 1o4 __ 1o5 __ 1o6 __`

There are seven empty positions numbered 1 to 7.

Counting: (*Note that the numbers below (like *`1 2 3`

) denote the empty position number.)

`> Case1: When all three operations of P2 are placed in consecutive empty positions. 1 2 3 2 3 4 3 4 5 4 5 6 5 6 7 We have a total of 5 ordering possible for empty positions. > Case2: When operations of P2 are placed in two consecutive empty positions taken together. 1 2 3 2 3 4 3 4 5 4 5 6 5 6 7 1 2 4 2 3 5 3 4 6 4 5 7 1 2 5 2 3 6 3 4 7 1 2 6 2 3 7 1 2 7 First cell in every column has already been counted in previous case. We have a total of (5 - 1) + (4 - 1) + (3 - 1) + (2 - 1) + (1 - 1) = 10 ordering possible for empty positions. A similar argument can be made for last two consecutive empty positions taken together, that gives us a total of another 10 ordering possible for empty positions. > Case3: These are those cases that do not have empty positions numbered 8 and 9 for them. 6 7 8 7 8 9 > Case4: When operations may crash mid way before completion. An 'x' denotes position where a crash is possible and process (here P2) terminates. 1x 2x 3 2x 3x 4 3x 4x 5 4x 5x 6 5x 6x 7 6x 7x 8 7x 8x 9 There is a total of 14 'x's possible. Note: I have not put a cross after last empty position number because I am assuming that a process will complete at this stage. You may correct my assumption if this is wrong and should not be assumed in the first place. `

Adding all 4 cases: `5 + 2*10 + 2 + 14 = 41`

. There are 41 possible ways to interleave operations processes P1 and P2.

As you can see, counting like this is cumbersome and error prone. I have missed cases.

**How can this counting problem be generalised?** *Please see the problem statement at the top of the question.*