The sum of the all possible $6$ digits numbers which are chosen in the set of {$0,0,0,1,2,3,4,5,6,7,8$}

combinationscombinatoricsdiscrete mathematicspermutationssolution-verification

When i get around in park , i thought about combinatorics and made up a question in my mind.

However, i cannot be sure about my solution because as you know , it is very easy to miss some details in combinatorics.So , i want to be checked my solution here.

Question: What is the sum of the all possible $6$ digits numbers which are chosen in the set of {$0,0,0,1,2,3,4,5,6,7,8$}

My humble attempt:

First step-) We can put $1$ element in the first digit in the set of {$1,2,3,4,5,6,7,8$},so there left $7+3=10$ possible numbers to put into the other $5$ digits. We can calculate it by $\frac{10 \times9\times8\times7\times6}{3!}=5040$ (we made division because of the zeros)

$\therefore 5040\times(1+2+3+4+5+6+7+8=36)\times10^5$

Second Step-) We have chosen one element for the first digit which is not zero.Then, for the second digit:

$1\times(\frac{7\times9\times8\times7\times6}{3!}=3528)\times10^4$

This will continue up to the sixth digits in the same logic.

Then $5040\times10^5+3528\times10^4+3528\times10^3+3528\times10^2+3528\times10^1+3528\times10^0=543199608$

Is my solution correct ? If not, can you write the correct solution.

Moreover , even if it is corect if you know much shorter way, can you share with us ?

Have a nice day…

Best Answer

I believe your approach to the question is correct, however, there seems to be one mistake. In your solution you claim that there are $\frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{3!} = 5040$ numbers with a particular starting digit. However, this is not quite correct. To illustrate your mistake here is a simpler example:

A simpler example

Let us say that we have the digits $\{0,0,1,2,3,4\}$ and we want to find all of the numbers of length 4 that start with $1$. Then we can list them all out to find that there are $33$ of them:

  • $1234, 1243, 1324, 1342, 1423, 1432$
  • $1023, 1024, 1032, 1034, 1042, 1043, 1203, 1204, 1230, 1240, 1302, 1304, 1320, 1340, 1402, 1403, 1420, 1430$
  • $1002, 1003, 1004, 1020, 1030, 1040, 1200, 1300, 1400$

How the total number is calculated is perhaps hinted by the way I have arranged the numbers above. Namely, we want to calculate in how many ways we can get a number of length $4$ starting with $1$ such that none of the zeros are used, one of the zeros is used, or all of the zeros are used.

  • If no zero gets used we get $ \binom{3}{0} \cdot 3 \cdot 2 \cdot 1 = 6$ results.
  • If one zero gets used we get $ \binom{3}{1} \cdot 3 \cdot 2 = 18 $ results.
  • If two zeros get used we get $ \binom{3}{2} \cdot 3 = 9$ results.

The sum of these yields exactly $33$. However, if I understood your calculation correctly, you would have claimed that there are $\frac{5 \cdot 4 \cdot 3}{2!} = 30$ results which is incorrect.

Back to the original problem

Now coming back to the original problem let us apply the same procedure. Consider any number $XZZZZZ$ where $X$ is fixed and each $Z$ represents an arbitrary digit.

  • If no zero gets used we get $ \binom{5}{0} \cdot \frac{7!}{2!} = 2520 $ results.
  • If one zero gets used we get $ \binom{5}{1} \cdot \frac{7!}{3!} = 4200$ results.
  • If two zeros get used we get $ \binom{5}{2} \cdot \frac{7!}{4!} = 2100$ results.
  • If three zeros get used we get $ \binom{5}{3} \cdot \frac{7!}{5!} = 420 $ results.

So in total there are $9240$ numbers where $X$ is the first digit.

Now note that an integer contributes nothing to the sum if it is $0$ and fix the first two digits so that our number is given by $XYZZZZ$. We then ask ourselves how many numbers of this kind we can make. This is simply a slight alteration of what we did before.

  • If no zero gets used we get $ \binom{4}{0} \cdot \frac{6!}{2!} = 360 $ results.
  • If one zero gets used we get $ \binom{4}{1} \cdot \frac{6!}{3!} = 480$ results.
  • If two zeros get used we get $ \binom{4}{2} \cdot \frac{6!}{4!} = 180$ results.
  • If three zeros get used we get $ \binom{4}{3} \cdot \frac{6!}{5!} = 24 $ results.

Now allowing $Y$ to be any non-zero value we see that there are $1044 \cdot 7 = 7308$ numbers which start with $X$ and have a non-zero second coefficient.

Since the same procedure can be applied to the number $XZZZZZ$ where any $Z$ is replaced by a $Y$, we conclude that our answer is:

$$36 \cdot \left( 9240 \cdot 10^5 + 7308 \cdot 11111 \right)$$

A general solution

By now, you might be able to see how we can construct the general solution to this problem. If we have an input of consisting of $m$ zeros, the first $n$ positive integers and you are creating a number of length $r$ with $m \leq r-2$ and $n \geq r$ then I believe the general solution to this problem is given by:

$$ \frac{(n)(n+1)}{2} \cdot \left( 10^{r-1}\sum_{i=0}^m \left[\binom{r-1}{i} \cdot \frac{(n-1)!}{(n-r+i)!} \right] + \left(\sum_{i=0}^{r-2} 10^i\right) \sum_{i=0}^m\left[\binom{r-2}{i} \cdot \frac{(n-1)!}{(n-r+i)!} \right] \right) $$

Comment

Combinatorics is not my strong suit by any stretch of the imagination, so by all means, please point out anything you think is incorrect or is explained poorly.

Related Question