3
$\begingroup$

I am trying to solve a combinatorial problem involving finding the number of integer solutions to the following equation:

$$ x_1 + x_2 + \dots + x_{10} = 100 $$

Subject to the constraints: $$ 2 \le x_i \le 21 \quad \text{for all } i = 1, \dots, 10 $$

My Attempt: I understand that I can simplify the lower bound by performing a variable change. Let $y_i = x_i - 1$. The constraints change from $2 \le x_i \le 21$ to $1 \le y_i \le 20$. Substituting this into the sum: $$ \sum_{i=1}^{10} (y_i + 1) = 100 \implies \sum_{i=1}^{10} y_i + 10 = 100 \implies \sum_{i=1}^{10} y_i = 90 $$

So the problem is equivalent to finding the number of integer solutions for: $$ y_1 + y_2 + \dots + y_{10} = 90, \quad 1 \le y_i \le 20 $$

I know how to use Stars and Bars for the lower limit ($y_i \ge 1$), which would be $\binom{n-1}{k-1} = \binom{89}{9}$, but I am stuck on how to handle the upper bound ($y_i \le 20$).

Define the "Bad" Condition

We must subtract cases that violate the rule $y_i \le 20$. A variable is "bad" if: $$ y_i \ge 21 $$ (Note: The limit was 20, so 21 is the first number that breaks the rule).

But I don't quite understand how to count solutions in each bad case

(eg.you got 1 bad number so that is $\binom{10}{1} \times ? $)

Any help is appreciated.

(UPDATE) different from this post Number of integer solutions of $x_1+x_2+⋯+x_n=m$ when $x_i$ can be negative, simpler solution we have both upperbounds and lowerbounds

$\endgroup$
5
  • 4
    $\begingroup$ Yes, you can use Inclusion-Exclusion. See Mike Earnest's solution to Extended stars-and-bars problem (where the upper limit of the variable is bounded). Marc van Leeuwen's solution shows how generating functions can be applied to the same problem. Note that both solutions work with nonnegative integers rather than positive integers. $\endgroup$ Commented 19 hours ago
  • $\begingroup$ .What is your specific problem with inclusion-exclusion ? Unless you are familiar with generating functions and have computational assistance, inclusion -exclusion is straightforward. $\endgroup$ Commented 18 hours ago
  • $\begingroup$ @trueblueanil added to the problem $\endgroup$ Commented 18 hours ago
  • $\begingroup$ So $$\binom{89}9 - \binom{10}1\binom{68}9 + \binom{10}2\binom{47}9- ...$$ , got it ? $\endgroup$ Commented 17 hours ago
  • $\begingroup$ I know it's not really the mathematician's way, but dynamic programming can make light work of these kinds of counting problems also.(Is it 160155230027?) $\endgroup$ Commented 11 hours ago

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.