Number of $4$-digit numbers that can be formed with the digits $0,1,2,3,4,5$ with constraint on repetition

2.3k Views Asked by At

Problem Statement:-

Find the number of numbers of four digits that can be made from the digits $0,1,2,3,4,5$ if digits can be repeated in the same number. How many of these numbers have at least one digit repeated?

For those who wanna skip all the babble below this para on why I thought what I thought just jump to the Modified Problem Statement in the Edit.

Seems pretty easy, right? Until you are me who misread the given constraint on the repetition of the digits as this - "the numbers can be repeated as many times as their magnitude". So, this would imply $0$ being repeated $0$ times, so it will occur only $1$ time. Similarly, $1$ will repeat $1$ time so it will occur only $2$ times, and so $2$ occurs $3$ times, $3$ occurs $4$ times, and so on. If we were to write the multiset for the digits from which we can choose from then, the multiset would be $$(\{(0,1),(1,2),(2,3),(3,4),(4,5),(5,6)\})$$

And after spending a lot of time I thought why not try to find a solution here, because I was not able to get one.


My Attempt at a solution to my proposed problem:-

The first digit can be anyone of the five non-zero digits. Assuming the non zero digits to be distinct, we get the total no of nonzero digits to be $20$, hence no of ways of selecting the first digit (i.e. the digit at the thousandths place) is $\displaystyle{{20}\choose{1}}$ and the remaining $20$ digits can be arranged in $3$ remaining spaces is ${}^{20}P_3$. Since we had assumed all the digits to be distinct (even those which were repeating), hence we need to set the overcount that we did due to repetition of arrangements hence we divide the ways of arranging by $(4!)^3.3!.2!.1!$ due to $3,4,5$ can have $4$ copies each in the arrangement, the digit $2$ has $3$ copies and the digit $1$ has $2$ copies. Hence, the total no of ways can be given as $$\dfrac{\displaystyle{{20}\choose{1}}.{}^{20}P_3}{(4!)^3.3!.2!}$$.

On calculating this comes out to be a fraction. So, this is definitely not the correct approach.

Edit:- For all those who are solving the problem as given in the Problem Statement in the quotes, what I was wanting was that what if instead of the constraint the question had placed the constraint had been what I had interpreted it initially which I have already written just below the quote, i.e. "the numbers can be repeated as many times as their magnitude"

So, lets state the problem that I am trying to solve if you wanna skip all the babble in the first part

Modified Problem Statement:-

Find the number of numbers of four digits that can be made from the digits $0,1,2,3,4,5$ if digits can be repeated as many times as their magnitudes. How many of these numbers have at least one digit repeated?

3

There are 3 best solutions below

3
On

If I read your problem statement correctly, there are no limits on repetitions. As $0$ cannot occur as the first one (by convention), ther are 5 options for the first digit and 6 for the 3 others. So there are $5\cdot 6^3 = 1080$ numbers in total. To count the ones with a repeating digit, count those with no repeating digits and take the complement. The first place has $5$ options, the second $5$ as well (all but the one we pick first), then $4$ options and finally $3$, so $25 \cdot 12 = 300$ numbers have no repeated digits, so $1080 - 300 = 780$ 4-digit numbers will have at least a repeated digit. I see (in the exact quote you gave) no evidence that 5 can repeat 5 times etc.

In the alternate interpretation, the universe of allowed numbers is smaller: we can have no repeated $0$'s (there are $\binom{3}{2} \cdot 5 \cdot 5$ numbers that are disallowed by that rule (2 out of 3 places with possible 0's, the remaining can be 5 things for the first place and 5 for the remaining digit as well). As to 1: 2 1's is allowed, but not 3 or 4, so we only discard $\binom{4}{3} \cdot 5 + 1$ many numbers. The 1 is for $1111$, also disallowed ) After recomputing the size of the "universe" of allowed 4-digit numbers, we still substract all numbers where all digits are different to get the required answer. 4 and 5 offer no restrictions, as we cannot even have more than 4 repeated 4's etc.

1
On

The first part is simple. except zero, all digits can go at first and the remaining positions can be either of the six digits. So the total number of 4-digit numbers is:

$$A=5\times6\times6\times6$$

For the second part, the number of 4-digit numbers with no repeat is

$$B=5\times5\times4\times3$$

So the number of them with at least one repeat is $A-B$.

2
On

(This is for the modified version)

Count them in 4 disjoint batches.

    1. No $0$'s
    1. $\dots$ 4. $0$ is in place i. (These are similar and have equal number of numbers)

1.

Calculate the complement. That is: there is at least 3 $1$'s OR at least 4 $2$'s OR all digits are distinct. These don't intersect. Therefore count of this batch is

$$5^4 - \left({4 \choose 3} \cdot 4 + 1 \right) - 1 - {5 \choose 4}\cdot 4!= 487.$$

2. - 4.

As said, these are similar. We must make a 3 digit number from digits 1-5 with the repeat restrictions. Calculate the complement again. Now there are cases 3 $1$'s OR distinct digits. We get the count

$$5^3 - 1 - {5 \choose 3}\cdot 3! = 64.$$


So the total number is

$$487 + 3\cdot 64 = 679.$$