0
$\begingroup$

I was trying to count the number of natural number solutions to the equation: $x_1 + x_2 + ... + x_{11} = 20$, such that $0 \leq x_i \leq 9$, for all $i \in \{1, ..., 11\}$.

I know how to apply the first boundary condition - if I only required $0 \leq x_i$, then the number of solutions is $$\frac{30!}{20!\cdot10!}$$ because I can interpret the problem as trying to arrange $20$ balls in between $10$ bars, including the possibility of having $0$ balls in between two given bars. I just don't know how to apply the latter condition, i.e. $x_i \leq 9$.

Could anyone help me? Thanks in advance!

$\endgroup$
2
  • 1
    $\begingroup$ Inclusion-exclusion based on whether or not any upper bound conditions are violated. In particular, if the first upper bound condition were violated for instance (among possibly more), then you are in the scenario of $10\leq x_1$ and $0\leq x_i$ for each other $i$. Through a change of variable, letting $y_1=x_1-10$ and $y_i=x_i$ for the rest, you should be able to solve for the number of solutions to this new system of $y_i$'s in the same way that you did for the original system. Note in particular that you can violate multiple upper bound conditions simultaneously. $\endgroup$
    – JMoravitz
    Commented Aug 24, 2020 at 18:14
  • $\begingroup$ @RobPratt Thank you, I think it does! It’s a deeper explanation of what JMoravitz suggested, and I believe I understand it now! $\endgroup$
    – Gauss
    Commented Aug 24, 2020 at 19:49

1 Answer 1

Reset to default
0
$\begingroup$

Big Hint:

To divide 5 into 4 parts none of which is larger than 2 (or negative), can be done in following ways (ignoring permutations)

$2,2,1,0$

$2,1,1,1$

Consider $(x^0+x^1+x^2)^4$. Then $x^5$ would be formed from terms like $x^2.x^2.x^1.x^0$ and $x^2.x^1.x^1.x^1$ only. In how many ways? Obviously that's the strength of the coefficient.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .