0
$\begingroup$

So I was given this question. How many $10-$digit decimal sequences (using $0, 1, 2, . . . , 9$) are there in which digits $3, 4, 5, 6$ all appear?

My solution below (not sure if correct)

Let $A_i$ = set of sequences of $n$ digits where $i$ does not appear. The number of $n$ digit decimal sequences = the total number of decimal sequences minus those that do not have either $3, 4, 5,$ or $6$. That is we wish to calculate $10^n - |A_1 \cup A_2 \cup A_3 \cup A_4| = 10^n - |A_1| − |A_2| − |A_3| - |A_4| + |A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3| + |A_1 \cap A_4| + |A_2 \cap A_4| + |A_3 \cap A_4| − |A_1 \cap A_2 \cap A_3 \cap A_4|$ where $10^n$ represents the number of sequences of n digits and $|A_1 \cup A_2 \cup A_3 \cup A_4|$ represents the number of n digit sequences that either do not have a $3$ or a $4$ or a $5$ or a $6$. $|A_i| = 9^n, |A_i \cap A_j | = 8^n$ and $|A_1 \cap A_2 \cap A_3 \cap A_4| = 7^n$. The answer is then $10^n − 4 \cdot 9^n + 4 · 8^n − 7^n$

Is this correct?

$\endgroup$
  • 1
    $\begingroup$ You originally stated the problem as being $10$-digit, but later refer to $n$ digits. You also use the notation $A_1, A_2, A_3, A_4$ which by your definitions above should denote the sets "does not have a $1$", "does not have a $2$", etc while your problem was referring to "has a 3", "has a 4", "has a 5" etc... Next, you seem to have gone from single sets to intersection of two sets skipping straight to intersection of four sets. What about intersection of three sets? You missed that. $\endgroup$ – JMoravitz Feb 10 '16 at 4:23
1
$\begingroup$

You have used Inclusion-Exclusion, which is correct, but it goes further than that.
Numbers with none of 3,4,5 have been subtracted three times in $|A_1|,|A_2|,|A_3|$, added back in three times in $|A_1\cap A_2|,|A_1\cap A_3|,|A_2\cap A_3|$, so must be subtracted again in $|A_1\cap A_2\cap A_3|$
Lastly, $|A_1\cap A_2\cap A_3\cap A_4|$ must be added back in.

$\endgroup$
  • $\begingroup$ don't you add $|A_1|, |A_2|, |A_3|, |A_4|$ and subtract $\endgroup$ – Zero Feb 10 '16 at 4:27
  • $\begingroup$ No. We count sequences where they all appear, so subtract sequences where each doesn't appear. $\endgroup$ – Empy2 Feb 10 '16 at 4:30
  • $\begingroup$ how would that change the final answer exactly? $\endgroup$ – Zero Feb 10 '16 at 4:31
0
$\begingroup$

You missed that there are six pairs of two sets, not four, then that you have to consider triplets of sets before you get to the intersection of all four.

$\endgroup$

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.