Suppose there are N positions. For each position, one can fill it with S,F or T. There is one constraint that F and T cannot be next to each other. This means that a filling with FT in the sequence or TF in the sequence is not allowed. For example, if N = 5. We have FSSTT, SFSTT are valid sequences, but SFTFS is not. Can anyone help me with calculating the number of possible sequences?