Suppose there were three events that could be done in any order. Let these events be A, B and C. There are a total of 6 possible ways the events can be performed.

However, this time, there is a restriction. B can only be performed after A. In other words, A must be performed before B can, and ACB is also accepted.

Your task is to find a general formula for X number of events, and Y number of restrictions.

None of the events is mentioned in more than one restriction.

This puzzle would be more interesting in cases where events can be mentioned in more than one restriction.  As such, though, it would not be a simple matter of counting the number of restrictions, Y. Rather, after taking X!, that would have to be adjusted specifically for each restriction.

The simplest way of including given events in more than one restriction is a linear sequence: A before B before C before D. That is A must happen before B, B before C etc.   For every such restriction you'd divide the number of ways by the number of ways each set can be rearranged.  So for example, if there are 10 events, A through J, and A must be before B and B before C, while E must be before F and F before G and G before H, there are 10!/(3!*4!) ways of arranging them, as there are 3 members of A before B before C and 4 members of E before F before G before H.

More complex types of multiple inclusion would call for other calculations.  For example, if A must occur before B and also before C, but it doesn't matter what order B and C are done, then after dividing by 3! (for the three members of the compound restriction), you'd have to multiply by 2 (that is, 2!) to allow all (both, that is) permutations of B and C.  So, for example, if you have 10 events, A through J, and both A and B must be completed (in either order) before any of C, D or E can be completed (in any order), while F, G and H must be completed before either of I or J, then you'd have (10!/(5!*5!))*2!*3!*3!*2!. The two 5!'s represent the 5 members of each compound restriction; the first 2! represents A and B being in either order; the first 3! represents C, D and E being in any order; the second 3! represents the F, G and H being in any order and the final 2! represents the I and J being in either order.

It can certainly get more complicated than that, and each case must be considered  individually.

Posted by Charlie on 2005-02-10 15:41:28