3 ms·
The set of sequences of length n ending in HH (and with no earlier HH) and beginning with a T are in bijection with the set of sequences of length n-1 ending in
by ihm 3y ago
The set of sequences of length n ending in HH (and with no earlier HH) and beginning with a T are in bijection with the set of sequences of length n-1 ending in HH (and with no earlier HH) by the bijection
def f(s):
assert(s[0] == 'T')
return s[1:]
whose inverse is
def f_inverse(s):
return 'T' + s
- hayd 3y agoAlso the bijection between sequence of length n ending in HH (and no earlier HH) and beginning with an H are a bijection with the set of sequences of length n-2 ending in HH (with no earlier HH) by the bijection: def f(s): assert(s[0] == 'H') assert(s[1] == 'T') # can't be another H! def f_inverse(s): return 'HT' + s Therefore, since sequences either begin with a T or an H, for n>=2 we see f(n) = f(n-1) + f(n-2).