Calculate total number of words possible using alphabets A-Z having length 26 with following restrictions(Repetition not allowed)
- A and B should not occur adjacently (AB is not possible neither BA)
- D and E should not occur adjacently
- B and F should not occur adjacently
- L and M should not occur adjacently
- M and B should not occur adjacently
- K and A should not occur adjacently
- X and B should not occur adjacently
My first thought is to use Inclusion-Exclusion Principle.
My thought process so far: Total number of words possible=26!
Total number of words possible taking each cases independently =25!*2 (multiplying by 2 because of AB and BA)
But after this I don't know how to proceed. Can someone give me detail explanation. I am looking for explanation rather than answer in such a way that this question can be generalized.
Here is a formula to compute the answer.
There are 7 conditions. (I will actually consider the negation of each condition.) According to the inclusion-exclusion principle, the total number of words satisfying none of the conditions is the sum, for each subset of the conditions (of which there are 128, ranging between 0 and 7 conditions), of $(-1)^{\text{(number of conditions in the subset)}} \times \text{(number of words satisfying all the conditions in the subset)}.$
I will give an example to illustrate how the number of words can be calculated. If the conditions are "A and B adjacent", "B and M are adjacent", "D and E are adjacent", then the words will be formed from blocks ABM/MBA, DE/ED, C, F, G, ... There are 23 blocks in all, and two ways to order the multi-letter blocks, so the corresponding number of words is $2^2 \times 23!$. If we get a cycle, such as BMAB, then there are no corresponding words. If we have a single letter connected to three different letters, e.g., BF, BA, BM, then there are no corresponding words.
More formally (this answer generalizes), let $\Gamma$ be the graph on the set of 26 vertices $\{A, B, C, \dots, Z\}$ with seven edges AB, DE, BF, LM, MB, KA, XB. Then the required number of words is $$\sum_{S} (-1)^{|S|} 2^{b_s} a_S!,$$ where the sum is extended over all subgraphs $S$ of $\Gamma$ without cycles such that any vertex has degree at most 2, and where $|S|$ is the number of edges in $S$, $a_S$ is the number of connected components of $S$, and $b_S$ is the number of connected components consisting of more than one vertex. (The condition on $S$ says that it can be broken into disjoint line segments and isolated points. $a_S$ is the number of line segments plus the number of isolated points, and $b_S$ is just the number of line segments. $S$ could in principle have anywhere between 0 and $|\Gamma| = 7$ edges, although 7 is impossible with the particular conditions in this problem.)
I'm not sure whether this can be further simplified. In your case, there are no cycles, and the only vertex possibly of degree $> 2$ is $B$. There are 88 subgraphs $S$ satisfying the conditions to appear in the sum.