title: How can I count sequences that meet these constraints?
body: <p>I am trying to count permutations of a sequence of <code>I</code> and <code>O</code> symbols, representing e.g. people entering (<code>I</code> for &quot;in&quot;) and leaving (<code>O</code> for &quot;out&quot;) a room. For a given <code>n</code> many <code>I</code> symbols, there should be exactly as many <code>O</code> symbols, giving a total length of <code>2*n</code> for the sequence. Also, at any point in a valid permutation, the number of <code>O</code> symbols must be less than or equal to the number of <code>I</code> symbols (since it is not possible for someone to leave the room when it is empty).</p>
  <p>Additionally, I have some initial prefix of <code>I</code> and <code>O</code> symbols, representing people who previously entered or left the room. The output should only count sequences starting with that prefix.</p>
  <p>For example, for <code>n=1</code> and an initial state of <code>''</code>, the result should be <code>1</code> since the only valid sequence is <code>IO</code>; for <code>n=3</code> and an initial state of <code>II</code>, the possible permutations are</p>
  <pre><code>IIIOOO
  IIOIOO
  IIOOIO
  </code></pre>
  <p>for a result of <code>3</code>. (There are five ways for three people to enter and leave the room, but the other two involve the first person leaving immediately.)</p>
  <p>I'm guessing the simplest way to solve this is using <code>itertools.permutations</code>. This is my code so far:</p>
  <pre><code>n=int(input())  ##actual length will be 2*n
  string=input()
  I_COUNT=string.count(&quot;I&quot;)
  O_COUNT=string.count(&quot;O&quot;)
  if string[0]!=&quot;I&quot;:
   sys.exit()
  if O_COUNT&gt;I_COUNT:
   sys.exit()
  perms = [''.join(p) for p in permutations(string)]
  print(perms)
  </code></pre>
  <p>the goal is to get the permutation for whatever is left out of the string and append it to the user's input, so how can I append user's input to the remaining length of the string and get the count for  permutation?</p>