# A combinatorial problem

1. Mar 29, 2013

### pennypenny

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?

2. Mar 29, 2013

### Staff: Mentor

Here is a possible way to solve this:
For N=1, how many strings ending with S are possible?
For N=1, how many strings ending with F or T are possible?
For N=2, how many strings ending with S are possible, and how does that follow from the previous values?
For N=2, how many strings ending with F or T are possible, and how does that follow from the previous values?
...

3. Mar 29, 2013

### pennypenny

Thank! This helps:)

4. Apr 3, 2013

### Sridhar96

Find total number of permutations first.
Now fix F and T together as 1 letter.Now total number of letters is 4 (in the case where N = 5).Find total number of cases for this (note that F and t can permute among themselves in 2 factorial ways so multiply your answer by 2) and subtract this from the total number of permutation you obtained the first case.

5. Apr 3, 2013

### Staff: Mentor

Can you show how you would do this in detail, to avoid double-counting of strings like TFSFT?