Solution: 2019 Winter Midterm - 9
Author: Michiel SmidQuestion
Let $n \geq 4$ be an even integer and let $k$ be an integer with $1 \leq k \leq n/2$. Consider
strings consisting of $n$ characters, such that
- each character is an element of $\{a, b, c\}$,
- the number of $a$'s is equal to $k$, and
- each $a$ is at an even position.
(a)
${n/2 \choose k} \cdot 2^{n/2}$
(b)
${n \choose k} \cdot 2^{n/2}$
(c)
${n \choose k} cdot 2^{n-k}$
(d)
${n/2 \choose k} \cdot 2^{n-k}$
Solution
There are $ n/2 $ even positions.
We need to choose $ k $ of these positions to be $ a $‘s: $ \binom{n/2}{k} $
The remaining $ n - k $ positions must be $ b $‘s or $ c $‘s: $ 2^{n-k} $
Thus, there are $ \binom{n/2}{k} \cdot 2^{n-k} $ such strings.