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:
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.
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.
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.
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.