Suppose we have a string composed of $a$ $1$'s, $b$ $0$'s, and $c$ $-1$'s. Also suppose that $-1$ cannot be in the first, or last two positions of the string. Then we know that the number of unique strings we can have with this constraint is:

$$S = \dbinom{a+b+c-3}{c}\dfrac{(a+b)!}{a!b!}$$

Now I'm interested to know how many strings there will be if $-1$ cannot be in the first or last two positions as well as the following two additional constraints:

  1. A $1$ must come sometime before a $-1$.
  2. There must be a $1$ between two $-1$'s.

So I know we need to subtract constraints 1. and 2. from $S$, but I'm not sure how to actually generally calculate them.

It will always be the case that the number of $1$'s is greater than the number of $-1$'s and there are an arbitrary number of $0$'s.


It is best to start denovo.

First imagine there are $(a+b) 1's,$ $1\;1\;1 .......1\;[11]$ [The last two are protected.]

Insert $-1's$ in the $(a+b-2)$ gaps in $\dbinom{a+b-2}{c}$ ways

Protect the $c\;$ $1's$ immediately preceding $-1's$,

Any of the $a+b-c$ "unprotected" $1's$ can now be replaced by $0's$ in $\dbinom{a+b-c}{b}$ ways

Thus # of permissible strings = $\dbinom{a+b-2}{c}\dbinom{a+b-c}{b}$

  • $\begingroup$ You're a saint! $\endgroup$ – Jane Elenor Nov 3 '15 at 12:31
  • $\begingroup$ You're welcome ! $\endgroup$ – true blue anil Nov 3 '15 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.