For this question, a block is a sequence of 20characters, where each character is one of the 26 lowercase lettersa-z. For example, these are blocks:
iwpiybhunrplsovrowytrpulxfsqrixjhrtjmcrrfxfpwdhwgxtdaqtmxmlf
- How many different blocks are there?
- A block is squarefree if no character appears twotimes consecutively. The first and third example above aresquarefree, but the second example is not because of the twoconsecutive occurrences of r. How many squarefree blocks arethere?
- A block is non-local if the number of charactersbetween any two occurrences of the same character is at least 2.The first example above is non-local. The second example is not,because there are two occurrences of r with no characters betweenthem. The third example is not because there are two occurrences ofm with only one character between them. How many non-local blocksare there?
- A block is k-non-local if the number ofcharacters between any two occurrences of the same character is atleast k. Write a formula for the number ofk-non-local blocks that is valid for anyk∈{0,…,20}.
Sanity check: The formula you get for 2.4 gives the answer to2.2 when k=1 and gives the answer to 2.3 whenk=2.
