Concurrency Combination

[sahueso]

I decided to learn concurrency and wanted to find out in how many ways machine instructions from two different threads/processes could overlap in a theoretical setting where they are executed linearly. The code for both processes is a 10 iteration loop with 3 instructions performed in each iteration. I figured out the problem consisted of leaving X instructions fixed and then fit the other X instructions from the other process between the spaces taking into account that they must be ordered (eg.instruction 4 of process B must always come before instruction 20).

I wrote a program to count this number, looking at the results I found out that the solution is n Combination k, where k is the number of instructions executed throughout the whole life of one process, so for 10 iterations it would be 30, and n is nº instructions * 2 (2 processes), 60. In other words, the problem is the same as having n number of objects with n/2 fixed and having to fit n/2 among the spaces without the latter n/2 losing their order.

I have no idea why n C k works, I understand that the definition of a combination is, in how many ways can you take k elements from a group of n elements such that all the groups are different but the order in which you take the elements doesn't matter. In this case we have n elements and we are actually taking them all, because all the instructions are executed, so I don't see how it can be a combination where we are taking only k instructions from this set of size n, leaving the other k without being executed.

Could someone please explain to me how it works?

Thanks in advance.

[tychonoff]

Line up 60 boxes in order, each representing a time slot for one instruction. Selecting any 30 of them would represent one way the 60 instructions could be interleaved, if those 30 selections represent the first loop. A different selection of 30 boxes for the first loop would represent a different arrangement for the 60 instructions, and all arrangements may be obtained this way. So 60 choose 30 would be all possible arrangements.

[sahueso]

Understood. Thank you.