How many orderings of the digits from 1 to 8 contain the sub

How many orderings of the digits from 1 to 8 contain the sub-strings 12, 23 or 34? For example, 57238614 is one such ordering since 23 appears, and 12345678 works, too, since it has 12, 23, and 34, because this is the logical \"OR\" not the exclusive or. However, 73184625 is NOT such an ordering. No repeated digits allowed

Solution

I\'m considering [12] [23] and [34] as numbers that must be chosen individually. Therefore,

[12] _ _ _ _ _ _ gives us 6 options for the 1st digit, 5 options for the 2nd, 4 for the 3rd, etc... Therefore, we end up with 6! * 7 positions that the [12] can be in. Therefore, there are 7! permutations for this group.

[23] _ _ _ _ _ _ Similar logic as above, we end up with 7! permutations.

[34] _ _ _ _ _ _ Similar logic as the first, 7! permutations.

[12][34] _ _ _ _ is another such situation, it is also same logic, it gives us 4 options for the 1st digit, 3 options for the 2nd, 2 for the 3rd, 1 for the 4th.. Therefore, we end up with 4! * 6 * 5 positions that the [12] and [34] can be in. (Arrange the two numbers [12], [23] in 6 places is 6p₂ = 30 =6 * 5). Therefore, there are 6! permutations for this group.

[12][23] _ _ _ _Similar logic as the first, 6! permutations.

[23][34] _ _ _ _Similar logic as the first, 6! permutations.

[12][23][34] _ _ is another such situation, it is also same logic, it gives us 2 options for the 1st digit, 1 options for the 2nd digit. Therefore, we end up with 2! * 5 * 4 * 3 positions that the [12], [34] and [23] can be in. (Arrange the three numbers [12], [23] and [34] in 5 places is 5p₃ = 60 =5 * 4 *3). Therefore, there are 5! permutations for this group.

The total number of arrangements with 8 digits is 8! ways.

The required number of substrings is 8! - 7! - 7! - 7! + 6! + 6! + 6! - 5! = 27240