State the inclusion-exclusion principle.
Let be a string of digits, where . We say that the string has a run of length if there is some such that either for all or for all . For example, the strings
all have runs of length 3 (underlined), but no run in has length . How many strings of length 6 have a run of length ?