6
$\begingroup$

This question already has an answer here:

This question is related to Error solving “stars and bars” type problem

I have what I thought is a fairly simple problem: Count non-negative integer solutions to the equation

$$x_1 + x_2 + x_3 + x_4 + x_5 = 23$$

such that $0 \leq x_1 \leq 9$.

The difference here is on the constraint. It bounds all the $x_i$ under 10 : $\forall i\le5$ , $0 \leq x_i \leq 9$.

$8+8+0+0+7=23$ is accepted but not $18+3+0+0+2=23$ or $11+0+0+0+12=23$ . In other words all the $x_i$ must be usual digits.

Note that bad solutions may include one or two bad $x_i$. It is the main difficulty.

What is the count of combinations ?

Edit : this question includes a double bounds and a supplemental difficulty to find the right solution.

$\endgroup$

marked as duplicate by GoodDeeds, Watson, Claude Leibovici, Shailesh, JonMark Perry Sep 13 '16 at 4:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

The result $6000$ provided by @igael is correct. Here is supplement to the answer of @EricStucky. It is convenient to use the coefficient of operator $[x^j]$ to denote the coefficient of $x^j$ in a series. This way we can write e.g. \begin{align*} [x^j](1+x)^n=\binom{n}{j} \end{align*}

We obtain \begin{align*} [x^{23}]&(1-x^{10})^5\sum_{k\geq 0}\binom{k+4}{4}x^k\\ &=[x^{23}]\left(1-5x^{10}+10x^{20}\right)\sum_{k\geq 0}\binom{k+4}{4}x^k\tag{1}\\ &=\left([x^{23}]-5[x^{13}]+10[x^3]\right)\sum_{k\geq 0}\binom{k+4}{4}x^k\tag{2}\\ &=\binom{27}{4}-5\binom{17}{4}+10\binom{7}{4}\tag{3}\\ &=17550-5\cdot 2380+10\cdot35\\ &=6000 \end{align*}

Comment:

  • In (1) we expand the binomial up to $10x^{20}$ since higher powers do not contribute to $[x^{23}]$.

  • In (2) we use the linearity of the coefficient of operator and apply the rule $$[x^{p-q}]A(x)=[x^p]x^{q}A(x)$$

  • In (3) we select the coefficients accordingly.

$\endgroup$
  • $\begingroup$ nice synthesis ... $\endgroup$ – user354674 Sep 18 '16 at 14:47
  • 1
    $\begingroup$ @igael: Thanks! :-) $\endgroup$ – Markus Scheuer Sep 18 '16 at 14:52
  • $\begingroup$ Great explanation! $\endgroup$ – Abbas Jun 13 '18 at 16:28
  • $\begingroup$ @Abbas: Thanks. :-) $\endgroup$ – Markus Scheuer Jun 13 '18 at 17:03
3
$\begingroup$

We cannot have $3$ $x_i= > 9$ because the result might be $>= 30$

We can have two $x_i > 9$ because the result may be in the bounds , example $10+10+1+1+1=23$ and $11+10+1+1+0=23$

1 ) let's see the case where there is one or two $x_i > 9$

We can have one $x_i > 9$ because the result may be in the bounds , example $10+9+2+1+1=23$.

The trick would be to remove $10$ and to focalize on the distribution of the remaining $13$ ( which will include a case of twice overflow ) :

Ways to chose the overflow candidates $ = \binom {5}{1} \begin{pmatrix}23 + (5-1) -10 \\ (5-1)\end{pmatrix} = \binom {5}{1} \begin{pmatrix}17 \\ 4\end{pmatrix} = 11900$

2 ) let's see the case where there are two $x_i > 9$ .

Again, the trick is to remove twice 10 and to focalize on the distribution of the remaining $3$.

Ways to chose the twice overflow candidates $ = \binom {5}{2} \binom {23 + (5-1) -10-10}{5-1} = \binom {5}{2} \binom {7}{4} = 350$

These last combinations had been counted twice and then we must deduced it once.

3 ) Now ignoring the bounds limitation, we have a total of combinations of $\begin{pmatrix}23 + (5-1) \\ (5-1)\end{pmatrix} = \begin{pmatrix}27 \\ 4\end{pmatrix} = 17550$

The result must be $17550 - (11900 - 350) =6000$

$\endgroup$
  • 1
    $\begingroup$ (+1) to equalize some worries. From my point of view this question is of the same type as the referred one. But since the focus is put on specific aspects, it shouldn't be marked as duplicate. $\endgroup$ – Markus Scheuer Sep 13 '16 at 8:15
2
$\begingroup$

One of the answers in the cited question uses generating functions. This idea ports over immediately: as argued in that post, the relevant generating function for this problem is

$$\left(\frac{1-x^{10}}{1-x}\right)^5 = (1-x^{10})^5\left(\sum_{k\geq 0} x^k\right)^5 = (1-x^{10})^5\sum_{k\geq 0} \binom{k+4}{4}x^k,$$

and we are interested in the coefficient on $x^{23}$. (The reasoning for this setup is essentially given in the linked answer.)

Tiny simplification: we do not need to expand the first polynomial out in full, since if we get to the $-\binom{5}{3}x^{30}$ term we have already exceeded the required degree. (If you think about it, you'll see that this corresponds to your observation that there cannot be more than two bad $x_i$).

So the problem is equivalent to finding the $x^{23}$ coefficient of

$$(1-5x^{10}+10x^{20}+\cdots)\sum_{k\geq 0} \binom{k+4}{4}x^k.$$

Can you take it from here?

$\endgroup$
  • $\begingroup$ Thomas Andrew's comment to GoodDeeds's answer linked above gives some insight about how to convert this to a inclusion-exclusion proof. (But then, perhaps so will the form of the answer :P) $\endgroup$ – Eric Stucky Sep 11 '16 at 17:20
  • $\begingroup$ I have the answer. Could you please provide a numerical result ? I took another way but I'll will now read your answer carefully. $\endgroup$ – user354674 Sep 11 '16 at 17:21
  • $\begingroup$ Yes, it's a good way ... a little difficult to apply but most general and elegant $\endgroup$ – user354674 Sep 11 '16 at 17:35