-1
$\begingroup$

How many k-digit ternary strings are there in which no digit occurs exactly twice? The occurrences do not need to be consecutive.

  • 0
    Where did this arise?2012-07-01

2 Answers 2

1

This can be computed using an inclusion-exclusion argument. Let $s(k)$ be the number of such strings of length $k$.

There are $3^k$ strings altogether. In $\binom{k}22^{k-2}$ of them there are exactly two $0$’s. There are the same number with exactly two $1$’s and the same number again with exactly two $2$’s. However, there are $\binom{k}2\binom{k-2}2$ strings with exactly two $0$’s and exactly two $1$’s, the same number with exactly two $0$’s and exactly two $2$’s, and the same number with exactly two $1$’s and exactly two $2$’s. Finally, if $k=6$ there is one string with exactly two of each symbol; otherwise there are no such strings. For $k\ne 6$, therefore, the desired total is

$\begin{align*}s(k)&=3^k-3\binom{k}22^{k-2}+3\binom{k}2\binom{k-2}2\\ &=3^k-3k(k-1)2^{k-3}+\frac34k(k-1)(k-2)(k-3)\;;\end{align*}$

for $k=6$ this must be decreased by $1$, yielding $s(6)=3^6-3\cdot6\cdot5\cdot2^3+\frac34\cdot6\cdot5\cdot4\cdot3-1=278\;.$

The first few values, in tabular form (assuming that I’ve made no arithmetic errors):

$\begin{array}{r|cc} k:&0&1&2&3&4&5&6&7&8\\ \hline s(k):&1&3&6&9&27&93&278&801&2445 \end{array}$

  • 0
    @Brian: You’re absolutely right; somehow I slipped an extra factor of $2$ in there.2012-07-02
2

There are $3^k$ strings. We need to subtract the number of strings for which some digit, or more properly, trit, occurs exactly twice. We deal only with $k \gt 6$. Small $k$ can be done separately.

There are $\binom{k}{2}2^{k-2}$ strings in which $1$ occurs exactly twice, and also $\binom{k}{2}2^{k-2}$ strings in which $2$ occurs exactly twice, and also $\binom{k}{2}2^{k-2}$ strings in which $3$ occurs exactly twice. But if we add up, we will double count the strings in which $1$ and $2$ occur exactly twice, and also the strings in which $2$ and $3$ occur exactly twice, and the same for $1$ and $3$. The number of strings in which $1$ and $2$ occurs exactly twice is $\binom{k}{2}\binom{k-2}{2}$. The same holds for other combinations of two.

Thus for $k \ge 7$, the number of strings in which nothing occurs exactly twice is $3^k -3\binom{k}{2}2^{k-2}+3\binom{k}{2}\binom{k-2}{2}.$