Hello, everyone!
I received the following question as part of my Discrete Mathematics course and am unable to solve it.
How many strings of four decimal digits that do not contain the same digit three times?
I know that it is related to counting rules and involves the product and sum rules however, I can not decide what approach to take to solve.
What I have so far:1) Solution 1Total number of combinations = 10 * 10 * 10 * 10 = 10 ^ 4 = 10 000
Number of combinations where the string contains the same digit three times: 1 * 1 * 1 * 10 = 10 * 10 (since 0 - 9 are possible numbers that can be repeated) = 100
Number of combinations where the string does not contain the same digit three times: 10 000 - 100 = 9 900
Help Needed:I do not know if this is correct. If it isn't, I would be very appreciative if someone could direct me to the correct method for solving the problem.
$\endgroup$ 35 Answers
$\begingroup$As Eric noted in a comment, you're not taking into account the fact that there are four different positions for the fourth digit. The correct calculation is
$$ 10^4-4\cdot10\cdot10+3\cdot10=9630\;, $$
where the last term corrects for the fact that the second term counts each string of four identical digits $4$ times. Alternatively, not counting them in the second term, you could also write
$$ 10^4-4\cdot10\cdot9-10=9630\;. $$
$\endgroup$ $\begingroup$Bad strings with exactly $3$ digits same:
[Choose triple]$\;\times\;$[Choose single]$\;\times\;$ [Place single] $=\binom{10}{1}\binom91\times 4 = 360$
Bad strings with all $4$ digits same: = $10$
Depending upon whether you mean exactly $3$ same or at least $3$ same,
answers are $9640$ or $9630$
the possible combinations are
axxx-10*9=90
xaxx-10*9=90
xxax-10*9=90
xxxa-10*9=90
xxxx-only 10 times
a can be 0 to 9
so total=10000-370=9630
$\endgroup$ 1 $\begingroup$I think it should work somehow as foollows: There are $10\cdot9\cdot8\cdot7=5040$ strings where all digits are different and there are $10\cdot(1\cdot1\cdot9\cdot8)\cdot\binom{4}{2}=4320$ where exactly one digit appears twice (the expression is constrcted in the following way: choose one of the ten digits, this digit is chosen twice and the other two digits are chosen randomly without replacement, but there are six ways to of the two equal digits in a string of four). It remains to include the strings that contain two pairs of digits each. This gives $10\cdot9\cdot\binom{4}{2}\cdot\frac{1}{2}=270$, because there are $10\cdot9$ ways in which we can pick two numbers and then it remains to choose the different positions in which we can put two of the digits in the string. The last division accounts for the fact that each permutation is chosen twice. This gives a total of 9630 different strings.
$\endgroup$ 2 $\begingroup$Starting with the maximum number of 4 digit combinations, you'll have 10,000 possibilities.
Now lets look at how we can combine a single digit 3+ times within that 4 digit number:
DXXX * 9 different values of D where D != X
XDXX * 9
XXDX * 9
XXXD * 9
XXXX * 1So that is 37 different combinations. Now 37 * 10 different digits = 370 ways to make a digit appear at least 3 times.
Therefore, 10,000 - 370 = 9630 4 digit numbers where the same digit does not appear 3 times.
$\endgroup$
