On the number of solutions of indefinite equations

The number of solutions of the indefinite equation

Lv0

  First of all, let's look at such a problem , seek $\sum _{i=1}^n{x}_i=b$ The number of nonnegative integer solutions of .

  This problem is very simple , Let's transform him a little , This problem is equivalent to having $n$ A child points $b$ A candy , Each child gets at least $0$ A candy （ What a tragedy ）, Find the number of schemes to divide the candy .

  Then we will transform the problem , Now there is $b$ Candy in a row , Put it in it $n-1$ A board （ There can be multiple boards in the same grid ）, In this way, these candies can be divided into $n$ part , Find the number of plans for square planks .

  It's obvious , The answer is a total of $n+b-1$ Grid options , Choose among them $n-1$ The number of schemes in a grid , That is to say $C_{n+b-1}^{n-1}$.

Lv1

  There is another problem , seek $\sum _{i=1}^n{x}_i=b$ And $x_i\ge l_i$ The number of nonnegative integer solutions of . Obviously, we don't want the following constraints , So we consider this ：

$$\sum _{i=1}^n{x}_i=b-\sum _{i=1}^n{l}_i$$

  In this way, we will transform the problem into the same form as the first problem （ It's equivalent to we lose $x_i<l_i$ The contribution of ）, The answer is ：

$$ans=\left(\begin{array}{c}n+b-\sum _{i=1}^n{l}_i-1\\ n-1\end{array}\right)$$

Lv2

  Last question , seek $\sum _{i=1}^n{x}_i=b$ And $x_i\le r_i$ The number of nonnegative integer solutions of . This problem is not as good as the previous one . So we consider letting go $x_i\ge r_i+1$ The contribution of .

  We ordered the assembly $S$ Express $\sum _{i=1}^n(x_i\ge r_i+1)$ Binary set of . This is equivalent to asking $S=\{0,0,\cdots ,0\}$ The answer when . We make $f(S)$ Indicates that the binary set is $S$ The answer is . Then there are ：

$$f(S=\{0,0,\cdots ,0\})=tot-\sum _{S\subset U}(-1{)}^{|S|+1}f(S)$$

  among $tot$ Represents the total number , That is the answer to the first question .$U=\{0,0,\cdots ,0\}$ （$n$ individual $0$）. The above formula is the inclusion exclusion principle .

  And then one of them （ Equivalent to the second problem ）：

$$f(S)=\left(\begin{array}{c}n+b-1-\sum _{i\in S}(r_i+1)\\ n-1\end{array}\right)$$

  therefore ：

$$\begin{array}{rl}ans& =\left(\begin{array}{c}n+b-1\\ n-1\end{array}\right)-\sum _{S\subset U}(-1{)}^{|S|+1}f(S)\\ & =\left(\begin{array}{c}n+b-1\\ n-1\end{array}\right)+\sum _{S\subset U}(-1{)}^{|S|}\left(\begin{array}{c}n+b-1-\sum _{i\in S}(r_i+1)\\ n-1\end{array}\right)\\ & =\sum _{S\subseteq U}(-1{)}^{|S|}f(S)\end{array}$$