Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A combinatorial problem

  1. Mar 29, 2013 #1
    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. jcsd
  3. Mar 29, 2013 #2

    mfb

    User Avatar
    2016 Award

    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?
    ...
     
  4. Mar 29, 2013 #3
    Thank! This helps:)
     
  5. Apr 3, 2013 #4
    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.
     
  6. Apr 3, 2013 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Can you show how you would do this in detail, to avoid double-counting of strings like TFSFT?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A combinatorial problem
  1. Combinatorial Problem (Replies: 1)

Loading...