What is the number of possibilities to choose 80 numbers out of the set $~\{10,11,\cdots,99\}~$ with repetition and no order significant. In which if an element that divides by $10$ with no Remain of division selected it must be chosen at least as many times as its $~10^{\text{th}}~$ digit.

Example: if $~30~$ is chosen it will be chosen minimum $~3~$ times. Otherwise it could not be selected.

I've been tried to solve it with Inclusion-Exclusion by taking the sum of all the possibilities and reduce from it the following groups:

$A_2=$ all the possibilities that $20$ will appears only once $\binom{89}{79}$

$A_3=$ all the possibilities that $30$ will appears only once, or only twice $\binom{89}{79}$ + $\binom{89}{78}$.





which give me the following :

$$\binom{89}{79}-\Biggl(\sum_0^1 \binom{89}{79-i} + \sum_0^2 \binom{89}{79-i} + \sum_0^3 \binom{89}{79-i} +\sum_0^4 \binom{89}{79-i}+\cdots+\sum_0^8 \binom{89}{79-i}\Biggr)$$ and so on..

I think, I'm missing the target by trying way too hard to manipulate the problem into this formula and it sure has a simpler way to calculate it. but I can't put my finger on it.

Please advice.

  • 2
    $\begingroup$ I know I saw this exact question earlier today, probably from you. Deleting previous version and reposting just to gain more attention is frowned upon. $\endgroup$ – JMoravitz Aug 20 at 14:33
  • $\begingroup$ I've asked earlier this week a similar question you right. but as you can see the question "data" is the same but the question itself is different. If you would like I can link you into the question you helped me with before, just to make it clear that I didn't delete and re-post the question. thanks for replaying. $\endgroup$ – David Aug 20 at 14:58

You are asking for the number of non-negative integer solutions of $x_{10}+x_{11}+\dots+x_{99}=80$ subject to $x_i\geq 0, x_{10}\geq 1, x_{20}\geq 2,\dots,x_{90}\geq 9$.

Consider a change of variable., letting $y_{10}=x_{10}-1$, letting $y_{20}=x_{20}-2$, ..., $y_{90}=x_{90}-9$ and $y_i=x_i$ otherwise.

You are now looking for the number of non-negative integer solutions of $y_{10}+y_{11}+\dots+y_{99}=35$ subject to $y_i\geq 0$ for each $i$.

This can be solved using traditional stars-and-bars approaches.

If this question were reflavored as asking how many ways you can distribute cookies to children, where the tenth child must get at least one cookie, the twentieth child must get at least two cookies, etc... you can explain the solution above by "giving the required necessary cookies out ahead of time and then distributing the remaining cookies after the fact."

  • 2
    $\begingroup$ As I read the question $x_{30}=0$ is allowed, just not $1$ or $2$ $\endgroup$ – Ross Millikan Aug 20 at 14:51
  • 1
    $\begingroup$ @RossMillikan hmm., in that case the easiest approach would be generating functions... Otherwise it becomes a horridly tedious inclusion-exclusion or breaking into cases based on which if any were zero. $\endgroup$ – JMoravitz Aug 20 at 14:54
  • $\begingroup$ @RossMillikan you are correct. if I can select all the numbers that not divide by 10 as many times as I wish, but by choosing a number which divides by 10 I would have to choose it at least the same amount as his 10th digit number. $\endgroup$ – David Aug 20 at 14:54

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.