I have the following letters:
A, B, C, D and E
and these have to be combined with:
F, G, H, I and J.
An example of a possible combination is (A, F), (B, H), (C, G), (D, J), (E, I).
Now, the following restrictions are given:
F can't be with A and E, G can't be with C and D, H can't be with A and E, I cant' be with B and J cant't be with C. I want to calculate the amount of possible combinations and I think I have to use the principle of inclusion and exclusion.
The total number of pairs $T$ is $5!$, I think, because I first want to permutate A-E.
Now my idea is this: $T - F(A, E) - G(C,D)-H(A,E)-I(B)-J(C)$, where $F(A, E)$ is the total number of pairs where $F$ is paired with $A$ or $E$. I'm obiously counting way too much right now, so could anybody point out how I can keep track of what I'm counting? That would help me solve this problem.
Thanks in advance!
No question that Inclusion-Exclusion, which generalizes well, is the 1st port of call, for a problem like this. Here, I reject Inclusion-Exclusion, in favor of the direct approach, for two reasons:
Ignoring permutations, there are only $5!$ candidate combinations to consider. Further, once the number of satisfying combinations are computed, it is a simple matter to multiply this number by $5!$ to obtain the number of satisfying permutations.
The restrictions are convoluted.
Thus, we have to consider : [C-k denotes Constraint #k]
C-1 - (F:BCD)
C-2 - (G:ABE)
C-3 - (H:BCD)
C-4 - (I:ACDE)
C-5 - (J:ABDE)
This is the turning point. Inclusion-Exclusion might still be the best way to attack this problem. It depends on the interactions between the constraints.
Here, I will go with the direct approach, rather than Inclusion-Exclusion, specifically because of the dovetailing interaction between C-1 and C-3.
Case-1
(F,H) = (B,C) or (F,H) = (C,B)
What the above syntax means is that F:B, H:C or vice-versa. The reason that these two possibilities are examined together is because, it is immediate, from the constraints, that the number of satisfying combinations that involve (F,H)=(B,C) will equal the number of satisfying combinations that involve (F,H) = (C,B).
The remainder of the analysis of Case-1 will assume (F,H) = (B,C).
Then, at the end of Case 1, I will simply take the computation and multiply by $2$.
At this point, you know [within Case 1], by C-2, that (G:AE).
If (G:A), then (I,J) must link with (D,E), with C-4,C-5 obeyed.
2 ways.
If (G:E), then (I,J) must link with (A,D), with C-4,C-5 obeyed.
2 ways.
Total # of ways = 4, assuming (F,H) = (B,C).
Total # of ways for Case 1 $= (4 \times 2) = 8.$
Case-2
(F,H) = (B,D) or (F,H) = (D,B)
Assume (F,H) = (B,D).
By C-2, (G:AE)
If (G:A), then (I,J) must link with (C,E), with C-4,C-5 obeyed.
Only 1 way, since J can't link with C.
If (G:E), then (I,J) must link with (A,C), with C-4,C-5 obeyed.
Similar to (G:A), only 1 way.
Final case 2 computation : $(1 + 1) \times 2 = 4.$
Case-3
(F,H) = (C,D) or (F,H) = (D,C)
With (C,D) removed, C-2,C-4,C-5 are adjusted to:
C-2 (G:ABE)
C-4 (I:AE)
C-5 (J:ABE)
You can tell at a glance that there are two ways of satisfying the adjusted C-4, and for each way, there are then two ways of satisfying the adjusted C-2,C-5.
Therefore, in Case 3, (F,H) = (C,D) will generate 4 possibilities.
Thus, for Case-3: $(4\times 2) = 8.$
Adding: the total number of combinations of Cases 1 through 3 combined are $(8 + 4 + 8) = 20.$
Since each combination yields $(5!)$ permutations, there are $20 \times (5!)$ satisfying permutations.
Addendum
I should probably examine the challenges inherent in applying Inclusion-Exclusion to this problem. This will explain that even absent the dovetailing of constraints C-1, C-3, for this problem, the alternative of Inclusion-Exclusion is no walk in the park.
This Addendum will be much easier to understand, if you first read this Inclusion-Exclusion article.
Consider the following chart:
D-1 - (F:AE)
D-2 - (G:CD)
D-3 - (H:AE)
D-4 - (I:B)
D-5 - (J:C)
The above chart represents the violations of the constraints. For example, if constraint C-1 is violated, then D-1 occurs, which means that either (F:A) or (F:E).
Then, suppose that you wanted to examine the situation where at least two constraints are being violated. This is distinct from the situation where exactly two constraints are being violated. There are $\binom{5}{2} = 10$ ways of selecting 2 of the constraints out of 5, and then computing the number of ways (i.e. combinations) that represent that at least these two specific constraints are being violated.
As a further illustration, suppose that you are examining the specific situation where constraints C-1 and C-4 were violated. This means that you are examining how many different ways that D-1 and D-4 could have simultaneously occurred. There are two ways that D-1 could have occurred, either (F:A) or (F:E). Coupled with D-4, you have (F:A, I:B) or (F:E, I:B).
Examining (F:A, I:B) you observe that this makes no restriction on how (G,H,J) are to be coupled with (C,D,E). Clearly, there are $(3!)$ such couplings. This means, that the number of ways that D-1,D-4 could simultaneously occur is $(3!) \times 2.$
This type of analysis leads to the following chart:
$(T_0) ~:~ (5!) \times (1).$
$(T_1) ~:~ (4!) \times (2 + 2 + 2 + 1 + 1).$
$(T_2) ~:~ (3!) \times (4 + 2 + 2 + 2 + 4 + 2 + 1 + 2 + 2 + 1).$
$(T_3) ~:~ (2!) \times (4 + 4 + 2 + 2 + 2 + 2 + 4 + 2 + 1 + 2).$
$(T_4) ~:~ (1!) \times (4 + 2 + 2 + 2 + 2).$
$(T_5) ~:~ (0!) \times (2).$
It is not a coincidence that
$T_0 - T_1 + T_2 - T_3 + T_4 - T_5 = 20.$
Things to note about the above chart:
All of the above analysis is merely a backdrop for the real issue: for any such problem, what is the best approach? Is the best approach the direct approach that I actually used, or is it the indirect approach of Inclusion-Exclusion?
Examining the Inclusion-Exclusion chart of $T_0, \cdots, T_5$, since $\binom{5}{0} + \cdots + \binom{5}{5} = 2^5$, the 5 constraints force the computation of $(2^5)$ separate terms. This means that when there are $n$ constraints, Inclusion-Exclusion is going to force the computation of $(2^n)$ terms.
Personally, when considering Inclusion-Exclusion for a problem of this nature, which has $(n)$ constraints, I would regard $(n=4)$ as iffy, $(n > 4)$ as perhaps too much, and $(n < 4)$ as do-able. An exception might be if the constraints had symmetrical properties, so that the $(2^n)$ terms did not have to be computed 1-at-a-time, but instead, some of the computations could be inferred from some of the other computations.
Now you have to examine the other side of the ledger. When considering the direct approach, how difficult will it be to take off your shoes and count out each possibility? How unwieldy will it be to manage the $(n)$ constraints? In the specific problem, with the $(n=5)$ constraints rendering Inclusion-Exclusion problematic, I fortunately was able to capitalize on the dovetailing of constraints C-1,C-3.