1
$\begingroup$

Find the number of nine-digit strings that contain each of the odd digits $1, 3, 5, 7, 9$. We can use any digit from $0,1,...,9$ but it is must include all odd digits. Repetitions are allowed.

I tried to solve it by the principle of inclusion-exclusion and took the sum of all strings not containing one or more of these digits. Let $k$ be the number of odd digits not present in the string. Then the answer would be $$\sum_{k=0}^{5}(-1)^k (10-k)^9{5 \choose k}$$ because any $k$ digits out of the five odd numbers can be chosen first then out of the rest $10-k$ digits, any can be chosen any number of times. Can someone help me check if this answer is correct considering repetition and exhaustiveness by pointing out mistake if present or rewording the answer in another way?

$\endgroup$
  • $\begingroup$ Are these the only digits to be used? Or can we use $2,4..$ as well. $\endgroup$ – Anurag A Oct 6 '18 at 16:25
  • $\begingroup$ I've edited the question to clear up some confusion $\endgroup$ – Krishna Oct 6 '18 at 16:35
  • 1
    $\begingroup$ The terms from inclusion-exclusion principle should have alternating signs. $\endgroup$ – peterwhy Oct 6 '18 at 17:07
2
$\begingroup$

Let's confirm your solution.

There are $10^9$ strings of length $9$ that can be formed by using the ten decimal digits with repetition. From these, we must exclude those strings in which at least one odd digit is missing.

Let $A_i$ be the set of outcomes in which the digit $i$ is excluded, where $i \in \{1, 3, 5, 7, 9\}$.

Then, by the Inclusion Principle, the number of strings in which at least one odd digit is missing is $$\sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - \sum_{i < j < k < l} |A_i \cap A_j \cap A_k \cap A_l| + \sum_{i < j < k < l < m} |A_i \cap A_j \cap A_k \cap A_l \cap A_m|$$

$|A_1|$: Since $1$ is excluded each of the nine positions in the string can be filled in nine ways. Hence, $|A_1| = 9^9$. By symmetry, $$|A_1| = |A_3| = |A_5| = |A_7| = |A_9|$$

$|A_1 \cap A_3|$: Since both $1$ and $3$ are excluded, each of the nine positions in the string can be filled in eight ways. Hence, $|A_1 \cap A_3| = 8^9$. By symmetry, $$|A_1 \cap A_3| = |A_1 \cap A_5| = |A_1 \cap A_7| = |A_1 \cap A_9| = |A_3 \cap A_5| = |A_3 \cap A_7| = |A_3 \cap A_9| = |A_5 \cap A_7| = |A_5 \cap A_9| = |A_7 \cap A_9|$$

$|A_1 \cap A_3 \cap A_5|$: Since $1$, $3$, and $5$ are all excluded, each of the nine positions in the string can be filled in seven ways. Hence, $|A_1 \cap A_3 \cap A_5| = 7^9$. By symmetry, $$|A_1 \cap A_3 \cap A_5| = |A_1 \cap A_3 \cap A_7| = |A_1 \cap A_3 \cap A_9| = |A_1 \cap A_5 \cap A_7| = |A_1 \cap A_5 \cap A_9| = |A_1 \cap A_7 \cap A_9| = |A_3 \cap A_5 \cap A_7| = |A_3 \cap A_5 \cap A_9| = |A_3 \cap A_7 \cap A_9| = |A_5 \cap A_7 \cap A_9|$$

$|A_1 \cap A_3 \cap A_5 \cap A_7|$: Since $1$, $3$, $5$, $7$, and $9$ are all excluded, each of the nine positions in the string can be filled in six ways. Hence, $|A_1 \cap A_3 \cap A_5 \cap A_7| = 6^9$. By symmetry, $$|A_1 \cap A_3 \cap A_5 \cap A_7| = |A_1 \cap A_3 \cap A_5 \cap A_9| = |A_1 \cap A_3 \cap A_7 \cap A_9| = |A_1 \cap A_5 \cap A_7 \cap A_9| = |A_3 \cap A_5 \cap A_7 \cap A_9|$$

$|A_1 \cap A_3 \cap A_5 \cap A_7 \cap A_9|$: Since $1$, $3$, $5$, $7$, and $9$ are all excluded, each of the nine positions in the string can be filled in five ways. Hence, $|A_1 \cap A_3 \cap A_5 \cap A_7 \cap A_9| = 5^9$.

Thus, by the Inclusion-Exclusion Principle, the number of strings of length $9$ in which at least one odd digit is missing is $$5 \cdot 9^9 - 10 \cdot 8^9 + 10 \cdot 7^9 - 5 \cdot 6^9 + 5^9$$ Therefore, the number of strings of length $9$ in which no odd digits are missing is \begin{align*} 10^9 - (5 \cdot 9^9 - 10 \cdot 8^9 + 10 \cdot 7^9 - 5 \cdot 6^9 + 5^9) & = 10^9 - 5 \cdot 9^9 + 10 \cdot 8^9 - 10 \cdot 7^9 + 5 \cdot 6^9 - 5^9\\ & = \binom{5}{0}10^9 - \binom{5}{1}9^9 + \binom{5}{2}8^9 - \binom{5}{3}7^9 + \binom{5}{4}6^9 - \binom{5}{5}5^9\\ & = \sum_{k = 0}^{5} (-1)^{k} \binom{5}{k}(10 - k)^9 \end{align*} where $\binom{5}{k}$ is the number of ways of excluding $k$ of the $5$ odd digits and $(10 - k)^9$ is the number of ways of filling the nine positions of the string with the remaining $10 - k$ decimal digits.

$\endgroup$
  • 1
    $\begingroup$ Clearest it could ever be! thanks $\endgroup$ – Krishna Oct 7 '18 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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