1
$\begingroup$

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

  • 0
    The formula you have written down is going to give you a negative number, so there is probably room for improvement.2012-02-23

3 Answers 3

0

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.

1

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.

1

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