Skip to main content
added 6 characters in body
Source Link
Mike Earnest
  • 78.3k
  • 11
  • 67
  • 136

For future reference, to people who are unfamiliar with generating functions, here is a solution using the principle of inclusion exclusion.


Ignoring the constraint $a_i\le r_i$, the number of solutions is $\binom{N+n-1}{n-1}$, by stars and bars. To incorporate these constraints, we subtract the "bad" solutions where some $a_i>r_i$. To count solutions where $a_1>r_1$, we instead count solutions to the equation $$ (a_1-r_1-1)+a_2+a_3+\dots+a_n=N-r_1-1 $$ Now, all summands on the left hand side are nonnegative integers, so the number of solutions is $\binom{N-r_1-1+n-1}{n-1}$. Therefore we subtract $\binom{N-r_i-1+n-1}{n-1}$ for each $i=1,2,\dots,n$.

However, solutions with two variable which were too large have now been subtracted twice, so these must be added back in. Solutions where $a_i>r_i$ and $a_j>r_j$ can be counted by subtracting $r_i+1$ from $a_i$ and $r_j+1$ from $a_j$, leaving a list of integers summing to $N-(r_i+1)-(r_j+1)$, the number of which is $\binom{N-(r_i+1)-(r_j+1)+n-1}{n-1}$.

We must then correct for the solutions with three variables which are too large, then four, and so on. This can be handled systematically using the principle of inclusion exclusion. The result is $$ \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1} $$ Here, we define $\binom{m}k=0$ whenever $m<0$.


For the special case $r_1=r_2=\dots=r_n=r$ where the upper limit is the same for each variable, the result is $$ \sum_{k=0}^{\lfloor N/(r+1) \rfloor}\binom{n}k\binom{N-k(r+1)+n-1}{n-1}. $$$$ \sum_{k=0}^{\lfloor N/(r+1) \rfloor}(-1)^k\binom{n}k\binom{N-k(r+1)+n-1}{n-1}. $$

For future reference, to people who are unfamiliar with generating functions, here is a solution using the principle of inclusion exclusion.


Ignoring the constraint $a_i\le r_i$, the number of solutions is $\binom{N+n-1}{n-1}$, by stars and bars. To incorporate these constraints, we subtract the "bad" solutions where some $a_i>r_i$. To count solutions where $a_1>r_1$, we instead count solutions to the equation $$ (a_1-r_1-1)+a_2+a_3+\dots+a_n=N-r_1-1 $$ Now, all summands on the left hand side are nonnegative integers, so the number of solutions is $\binom{N-r_1-1+n-1}{n-1}$. Therefore we subtract $\binom{N-r_i-1+n-1}{n-1}$ for each $i=1,2,\dots,n$.

However, solutions with two variable which were too large have now been subtracted twice, so these must be added back in. Solutions where $a_i>r_i$ and $a_j>r_j$ can be counted by subtracting $r_i+1$ from $a_i$ and $r_j+1$ from $a_j$, leaving a list of integers summing to $N-(r_i+1)-(r_j+1)$, the number of which is $\binom{N-(r_i+1)-(r_j+1)+n-1}{n-1}$.

We must then correct for the solutions with three variables which are too large, then four, and so on. This can be handled systematically using the principle of inclusion exclusion. The result is $$ \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1} $$ Here, we define $\binom{m}k=0$ whenever $m<0$.


For the special case $r_1=r_2=\dots=r_n=r$ where the upper limit is the same for each variable, the result is $$ \sum_{k=0}^{\lfloor N/(r+1) \rfloor}\binom{n}k\binom{N-k(r+1)+n-1}{n-1}. $$

For future reference, to people who are unfamiliar with generating functions, here is a solution using the principle of inclusion exclusion.


Ignoring the constraint $a_i\le r_i$, the number of solutions is $\binom{N+n-1}{n-1}$, by stars and bars. To incorporate these constraints, we subtract the "bad" solutions where some $a_i>r_i$. To count solutions where $a_1>r_1$, we instead count solutions to the equation $$ (a_1-r_1-1)+a_2+a_3+\dots+a_n=N-r_1-1 $$ Now, all summands on the left hand side are nonnegative integers, so the number of solutions is $\binom{N-r_1-1+n-1}{n-1}$. Therefore we subtract $\binom{N-r_i-1+n-1}{n-1}$ for each $i=1,2,\dots,n$.

However, solutions with two variable which were too large have now been subtracted twice, so these must be added back in. Solutions where $a_i>r_i$ and $a_j>r_j$ can be counted by subtracting $r_i+1$ from $a_i$ and $r_j+1$ from $a_j$, leaving a list of integers summing to $N-(r_i+1)-(r_j+1)$, the number of which is $\binom{N-(r_i+1)-(r_j+1)+n-1}{n-1}$.

We must then correct for the solutions with three variables which are too large, then four, and so on. This can be handled systematically using the principle of inclusion exclusion. The result is $$ \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1} $$ Here, we define $\binom{m}k=0$ whenever $m<0$.


For the special case $r_1=r_2=\dots=r_n=r$ where the upper limit is the same for each variable, the result is $$ \sum_{k=0}^{\lfloor N/(r+1) \rfloor}(-1)^k\binom{n}k\binom{N-k(r+1)+n-1}{n-1}. $$

Source Link
Mike Earnest
  • 78.3k
  • 11
  • 67
  • 136

For future reference, to people who are unfamiliar with generating functions, here is a solution using the principle of inclusion exclusion.


Ignoring the constraint $a_i\le r_i$, the number of solutions is $\binom{N+n-1}{n-1}$, by stars and bars. To incorporate these constraints, we subtract the "bad" solutions where some $a_i>r_i$. To count solutions where $a_1>r_1$, we instead count solutions to the equation $$ (a_1-r_1-1)+a_2+a_3+\dots+a_n=N-r_1-1 $$ Now, all summands on the left hand side are nonnegative integers, so the number of solutions is $\binom{N-r_1-1+n-1}{n-1}$. Therefore we subtract $\binom{N-r_i-1+n-1}{n-1}$ for each $i=1,2,\dots,n$.

However, solutions with two variable which were too large have now been subtracted twice, so these must be added back in. Solutions where $a_i>r_i$ and $a_j>r_j$ can be counted by subtracting $r_i+1$ from $a_i$ and $r_j+1$ from $a_j$, leaving a list of integers summing to $N-(r_i+1)-(r_j+1)$, the number of which is $\binom{N-(r_i+1)-(r_j+1)+n-1}{n-1}$.

We must then correct for the solutions with three variables which are too large, then four, and so on. This can be handled systematically using the principle of inclusion exclusion. The result is $$ \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1} $$ Here, we define $\binom{m}k=0$ whenever $m<0$.


For the special case $r_1=r_2=\dots=r_n=r$ where the upper limit is the same for each variable, the result is $$ \sum_{k=0}^{\lfloor N/(r+1) \rfloor}\binom{n}k\binom{N-k(r+1)+n-1}{n-1}. $$