How many ways can we write a word of 4 letters from the group of {1,2,3,4} without the sequence 12 and 23?

Question

How many ways can we write a word of 4 letters from the group of {1,2,3,4} without sequence 12 and 23? the options are:

1. 16 2.256 3.172 4.24

I think we can repeat on the same letter so I tried to this: count all of the words without any constraint: $4^4$ count the illegal words and then to do: $4^4$- illegal--> to get what I want. but I didn't get any of these options. thank you for your help!

Answer 1

In retrospect, this response is nothing but a re-hash of the comments of J Moravitz, which preceded it.

---

Hints:

When employing Inclusion-Exclusion in this problem, things to note:

1. Superficially, you would surmise that the number of ways that the sequence "12" can occur at least once is $\binom{3}{1} \times 4^2 = 48.$ This is wrong, since it over-counts the sequence "1212". Therefore, the correct enumeration here is $47.$

2. When enumerating the number of ways that the sequences "12" and "23" can both occur, for the add-back, re Inclusion-Exclusion, you have to count separately : "X123", "123X", "1223", and "2312".