# How many ways can you form a string with these constraints?

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}$

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