How many words with non-consecutive letters

combinatoricscombinatorics-on-wordspermutations

Using the letters A,B,C,D,E,F,G only once, how many words can be generated such that alphabetically consecutive letters are not next to each other?

For the version with only the letters A,B,C,D,E, there are 14 such words: ACEBD, ADBEC, BDACE, BDAEC, BECAD, CADBE, CAEBD, CEADB, CEBDA, DACEB, DBEAC, DBECA, EBDAC, ECADB

For this version with seven letters, I wrote a brute-force program and confirmed that the answer is 646 (which is the correct answer). However, I would like to see how to calculate this mathematically.

Best Answer

Attacking the $7$ letter case, use Inclusion-Exclusion.

Care must be taken, re G is (apparently) not considered to be consecutive with A.

Let $S$ denote the set of all possible $7$ letter words, without any regard to the constraint.

Let $S_1$ denote the subset of words that has A and B next to each other. This can be either ...AB... or ...BA...

Let $S_2$ denote the subset of words that has B and C next to each other.

Let $S_3$ denote the subset of words that has C and D next to each other.

Let $S_4$ denote the subset of words that has D and E next to each other.

Let $S_5$ denote the subset of words that has E and F next to each other.

Let $S_6$ denote the subset of words that has F and G next to each other.

For any set $W$, let $|W|$ denote the number of elements in $W$.

Then, you want $|S| - |S_1 \cup S_2 \cup \cdots \cup S_6|.$

Let $T_0$ denote $|S|.$

Let $T_1$ denote $\displaystyle \sum_{k=1}^6 |S_k|.$

Let $T_2$ denote $\displaystyle \sum_{1 \leq i_1 < i_2 \leq 6} |S_{i_1} \cap S_{i_2}|.$
That is, $T_2$ represents the sum of $~\displaystyle \binom{6}{2}~$ terms.

For $3 \leq r \leq 6$,
let $~\displaystyle T_r = \sum_{1 \leq i_1 < \cdots < i_r \leq 6} |S_{i_1} \cap S_{i_2} \cap \cdots \cap S_{i_r}|.$
That is, $T_r$ represents the sum of $~\displaystyle \binom{6}{r}~$ terms.

Then, per Inclusion-Exclusion, the desired computation is

$$\sum_{r=0}^6 (-1)^r |T_r|. \tag1 $$

Therefore, the problem is reduced to computing
$T_0, T_1, \cdots, T_6.$

Clearly,

$$T_0 = 7! = 5040.$$

To compute $S_1$ you can pretend that the A and B are fused together into $(1)$ unit.

Therefore, you have $(6)$ units to permute. Further, within the fused unit, the A and B can be permuted in $(2!)$ ways.

Therefore, $|S_1| = 2 \times 6!.$

Clearly, symmetrical considerations apply to the computations of
$|S_2|, \cdots, |S_6|.$

Therefore

$$T_1 = 6 \times 2 \times 6! = 8640.$$

When computing the $~\displaystyle \binom{6}{2}~$ terms in $T_2$, you have to distinguish between the $5$ terms represented by $|S_1 \cap S_2|$, and the $(10)$ terms that are represented by $|S_1 \cap S_3|$.

For $|S_1 \cap S_2|$, you have $5$ units to permute.
Further, in the ABC fused unit, the B must be the middle term.

Therefore, $|S_1 \cap S_2| = 2 \times (5!).$

With $|S_1 \cap S_3|$, you have $5$ units, two of which are fused.

Therefore, $|S_1 \cap S_3| = (2!) \times (2!) \times (5!).$

Thus, $$T_2 = [5 \times 2 \times (5!)] + [10 \times (2!) \times (2!) \times (5!)] = 6000.$$

When computing the $~\displaystyle \binom{6}{3}~$ terms in $T_3$, you have to distinguish between :

  • the $4$ terms represented by $|S_1 \cap S_2 \cap S_3|$.
  • the $12$ terms represented by $|S_1 \cap S_2 \cap S_4|$.
  • the $4$ terms represented by $|S_1 \cap S_3 \cap S_5|$.

In computing $|S_1 \cap S_2 \cap S_3|$, you have $4$ units to permute.

Further, the fused unit is constrained to either ...ABCD... or ...DCBA...

Therefore $|S_1 \cap S_2 \cap S_3| = (2!) \times (4!).$

In computing $|S_1 \cap S_2 \cap S_4|$, you have $4$ units to permute, $(2)$ of which are fused.

The ABC fused unit has $(2!)$ permutations, since B must be the middle element. The DE fused unit also permits (2!) internal permuations (i.e. between the D and E).

Therefore $|S_1 \cap S_2 \cap S_4| = (2!) \times (2!) \times (4!).$

In computing $|S_1 \cap S_3 \cap S_5|$, you have $4$ units to permute, $(3)$ of which are fused.

Therefore $|S_1 \cap S_3 \cap S_5| = (2!) \times (2!) \times (2!) \times (4!).$

The partial sums are:

  • $|S_1 \cap S_2 \cap S_3|$
    $4 \times 2! \times 4! = 192.$
  • $|S_1 \cap S_2 \cap S_4|$
    $12 \times 2! \times 2! \times 4! = 1152.$
  • $|S_1 \cap S_3 \cap S_5|$
    $4 \times 2! \times 2! \times 2! \times 4! = 768.$

$$T_3 = 192 + 1152 + 768 = 2112.$$

When computing the $~\displaystyle \binom{6}{4}~$ terms in $T_4$, you have to distinguish between :

  • the $3$ terms represented by $|S_1 \cap S_2 \cap S_3 \cap S_4|$.
  • the $6$ terms represented by $|S_1 \cap S_2 \cap S_3 \cap S_5|$.
  • the $3$ terms represented by $|S_1 \cap S_2 \cap S_4 \cap S_5|$.
  • the $3$ terms represented by $|S_1 \cap S_2 \cap S_4 \cap S_6|$.

The partial sums are:

  • $|S_1 \cap S_2 \cap S_3 \cap S_4|$
    $3 \times 2! \times 3! = 36.$

  • $|S_1 \cap S_2 \cap S_3 \cap S_5|$
    $6 \times 2! \times 2! \times 3! = 144.$

  • $|S_1 \cap S_2 \cap S_4 \cap S_5|$.
    $3 \times 2! \times 2! \times 3! = 72.$

  • $|S_1 \cap S_2 \cap S_4 \cap S_6|$.
    $3 \times 2! \times 2! \times 2! \times 3! = 144.$

$$T_4 = 36 + 144 + 72 + 144 = 396.$$

When computing the $~\displaystyle \binom{6}{5}~$ terms in $T_5$, you have to distinguish between :

  • the $2$ terms represented by $|S_1 \cap S_2 \cap S_3 \cap S_4 \cap s_5|$.
  • the $2$ terms represented by $|S_1 \cap S_3 \cap S_4 \cap S_5 \cap s_6|$.
  • the $2$ terms represented by $|S_1 \cap S_2 \cap S_4 \cap S_5 \cap s_6|$.

The partial sums are:

  • $|S_1 \cap S_2 \cap S_3 \cap S_4 \cap s_5|$
    $2 \times 2! \times 2! = 8.$

  • $|S_1 \cap S_3 \cap S_4 \cap S_5 \cap s_6|$
    $2 \times 2! \times 2! \times 2! = 16.$

  • $|S_1 \cap S_2 \cap S_4 \cap S_5 \cap s_6|$.
    $2 \times 2! \times 2! \times 2! = 16.$

$$T_5 = 8 + 16 + 16 + 16 = 40.$$

$T_6$ is represented by $|S_1 \cap \cdots \cap S_6|.$

$$T_6 = 2! = 2.$$

Final Computation:

$$\sum_{r=0}^6 (-1)^r T_r = (T_0 + T_2 + T_4 + T_6) - (T_1 + T_3 + T_5)$$

$$ = (5040 + 6000 + 396 + 2) - (8640 + 2112 + 40) = 646.$$

Related Question