Combinatorics, Ternary strings
A ternary string is a sequence of 0s, 1s, and 2s. How many ternary strings of length 15 are there? How many of those strings contain exactly seven 0s, five 1s, and three 2s? How many ternary strings of length 15 have even weight, i.e., contain an even number of 1s?
(1) there are 3^(15) of length 15. The second two parts I'm not sure about I know for a binary string (n choose w) will give you the number of strings of length n and weight w but I'm not sure how to apply this to ternary strings. Any help would be appreciated
$\endgroup$3 Answers
$\begingroup$For the balanced strings, it may be worthwhile to experiment, and find how many balanced strings have length $1$, length $2$, and length $3$. You should get $2$, $5$, $14$.
Let $a_n$ be the number of balanced strings of length $n$. We find a recurrence for the $a_n$.
There are two types of balanced string of length $n+1$: (i) the ones that end with $0$ or $3$ and (ii) the ones that end in $1$.
The Type (i) strings are obtained by appending a $0$ or $3$ to a balanced string of length $n$. So there are $2a_n$ of these.
The Type (ii) strings are obtained by appending a $0$ or $3$ to an unbalanced string of length $n$. So there are $3^n-a_n$ of these. Thus $$a_{n+1}=2a_n+3^n-a_n=a_n+3^n.$$ Now we can rapidly find $a_{15}$. We can even get a nice general formula for $a_n$.
$\endgroup$ 0 $\begingroup$For the second part, first you choose seven locations for the $0$'s. How many ways to do that? For each one, you have eight locations left and need to choose five for the $1$'s. For the last, if you want the number of strings with exactly $6\ 1$'s, you choose the locations for the ones, then have $2^9$ ways to fill the rest. Sum over the even numbers.
$\endgroup$ 5 $\begingroup$How many of those strings contain exactly seven 0s, five 1s, and three 2s?
The function $ {n \choose k} $ tells you how many subsets of size $ k $ you can choose from a set of size $ n $. So you can choose $ {15 \choose 7} $ configurations for $ 0 $'s - then, from the remaining $ 8 $, you can choose $ {8 \choose 5} $ for the $ 1 $'s. There are three remaining spots, so we're done.
How many ternary strings of length 15 have even weight, i.e., contain an even number of 1s?
There can be $ 0, 2, 4, \dots, 14 $ ones. So, for each $ k = 1 \dots 7 $ you need to compute how many strings there are containing exactly $ 2k $ ones.
$\endgroup$
