A coin is tossed repeatedly and the outcome is recorded as a sequence of H's and T's. We are interested in obtaining every possible n-bit string as contiguous subsequences of our coin tossing sequence in a minimum number of coin tosses. The subsequences are allowed to overlap. We want to know how many different minimal sequences there are.
For example, If n=1 then there are 2 such sequences: TH and HT.
For n=2 we want to obtain all four of the 2-bit subsequences TT, TH, HT, HH. There are 4 such sequences TTHHT, THHTT, HHTTH HTTHH.
Fro n=3 there are 16 such sequences: {T, T, T, H, H, H, T, H, T, T}, {T, T, H, H, H, T, H, T, T, T}, {T, H, H, H, T, H, T, T, T, T}, {H, H, H, T, H, T, T, T, T, T}, {H, H, T,H, T, T, T, T, T, H}, {H, T, H, T, T, T, T, T, H, H}, {T, H, T, T, T, T, T, H, H, H}, {H, T, T, T, T, T, H, H, H, T}, {T, T, T, H, T, H, H, H, T, T, T}, {T, T, H, T, H, H, H, T, T, T, T}, {T, H, T, H, H, H, T, T, T, T, T}, {H, T, H, H, H, T, T, T, T, T, T}, {T, H, H, H, T, T, T, T, T, T, H}, {H, H, H, T, T, T, T, T, T, H, T}, {H, H, T, T, T, T, T, T, H, T, H}, {H, T, T, T, T, T, T, H, T, H, H}.
According to Eric Weisstein's Math World article "Coin Tossing" the number of such sequences is 2^2^(n-1). I do not understand why this is true.
The problem might be reduced to a graph theory problem: see the Wikipedia article "DeBruijn Sequences".