Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the number of strings of length $235$ which can be made from the letters A, B, and C, such that the number of A's is always odd, the number of B's is greater than $10$ and less than $45$ and the Number of C's is always even?

What I can think of is

$$\left(\binom{235}{235} - \left\lfloor235 - \frac{235}2\right\rfloor\right) \binom{235}{35} \binom {235}{ \lfloor 235/2\rfloor}\;.$$

Thanks

share|improve this question
    
The formula you have written down is going to give you a negative number, so there is probably room for improvement. –  Gerry Myerson Feb 23 '12 at 6:19

3 Answers 3

up vote 1 down vote accepted

If there is an odd number of A's and an even number of C's, it follows that there must be an even number of B's.

Therefore, to construct a string of length 235, satisfying the properties above, it is sufficient to specify the position of the A's and the B's, because then the C's will be forced.

There are ${235 \choose n}$ ways to specify the position of the B's, where $n\in\{12,14,\dots,44\}$.

After we have placed the B's, there are $235-n\choose m$ ways to place the A's, where $m \in \{1,3,5,\dots,\frac{(235-n-1)}{2}\}$.

Hence, the number of possible strings is:

$$\displaystyle\sum_{n\in\{12,14,\dots,44\}}_{m\in\{1,3,\dots,(235-2n-1)/{2}\}} {235 \choose n} {235-n\choose m}$$

share|improve this answer

It's the coefficient of $x^{235}$ in $$(x+x^3+x^5+\cdots)(x^{11}+x^{12}+\cdots+x^{44})(1+x^2+x^4+\cdots)$$ Use the formula for sum of a geometric progression, then use the binomial theorem, it should fall right out.

share|improve this answer

Hint: I would do it with a program. You have 44*2*2 allowable states-number of B's, parity of A's and parity of C's. Write the recurrence relations and note that the empty string has even C's and no B's.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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