Skip to main content
"but.. but..." is ugly; rephrase
Source Link
Marc van Leeuwen
  • 116.1k
  • 8
  • 170
  • 352

There is as far as I know no closed formula for this general problem, but there is a formula that allows the number of solutions to be computed in a number of operations independent of $N$. Consider first the case that all limits are equal $r_1=r_2=\cdots=r_n=r$. Then the number is the coefficient of $X^N$ in the polynomial $(1+X+\cdots+X^r)^n$. By writing this as a rational function of$~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ the coeffiecient of $X^k$ in the numerator is zero unless $k$ is a multiple $q(r+1)$ of $r+1$, in which case it is $(-1)^q\binom nq$, and the coefficient of $X^l$ in the inverse of the denominator is $(-1)^l\binom{-n}l=\binom{l+n-1}l$, which is zero unless $l\geq0$ and otherwise equal to $\binom{l+n-1}{n-1}$. It remains to sum over all $k+l=N$, which gives $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom nq\binom{N-q(r+1)+n-1}{n-1}, $$ where the summation is truncated to ensure that $N-q(r+1)\geq0$ (the condition $l\geq0$). Although the summation looks complicated, it has at most $n+1$ easily computed terms, for any$~N$. Just to illustrate, the coefficient for $n=5$, $r=100$ and $N=243$ is easily computed to be $62018665$. An interesting point to remark is that if the summation had not been truncated, then the result would clearly have been a polynomial function of$~N$ of degree${}<n$ (because binomial coefficients $\binom xk$ are polynomial functions of$~x$ of degree$~k$). But on one hand that polynomial function gives the exact values of this problem for $N\geq n(r+1)$ where no truncation takes place, butwhile on the other hand, given the original problem, those values are all$~0$,; so the polynomial function will be identically zero! So an alternative formula for the result is to compute the negative of the truncated terms, which formula becomes after some massaging $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom nq\binom{q(r+1)-1-N}{n-1}, $$ which is easier to use for large$~N$. For instance in the above example this formula gives a single term $\binom{78}4=1426425$ for $N=426$; it is the same value as obtained for $N=74=500-426$ (from the first formula) which can be understood by the fact that the "remainders" $r_i-a_i$ add up to $nr-N$.

In the general case of distinct limits $r_i$, the approach is the same, but the formula becomes a bit messy. Instead of a numerator $(1-X^{r+1})^n$ one gets a product $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ which in general has more nonzero terms, (the number of terms can be up to $\min(\Sigma r_i+n+1,2^n)$), but which can be computed once and for all. With $P=\sum_ic_iX^{e_i}$, the formula for the result becomes $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ which still is a sum of a number of terms independent of$~N$. But of course just computing the polynomial $\frac P{(1-X)^n}$ beforehand, and then for any $N$ just looking up the coefficient of $X^N$, is another essentially constant-time (in $N$) solution.

There is as far as I know no closed formula for this general problem, but there is a formula that allows the number of solutions to be computed in a number of operations independent of $N$. Consider first the case that all limits are equal $r_1=r_2=\cdots=r_n=r$. Then the number is the coefficient of $X^N$ in the polynomial $(1+X+\cdots+X^r)^n$. By writing this as a rational function of$~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ the coeffiecient of $X^k$ in the numerator is zero unless $k$ is a multiple $q(r+1)$ of $r+1$, in which case it is $(-1)^q\binom nq$, and the coefficient of $X^l$ in the inverse of the denominator is $(-1)^l\binom{-n}l=\binom{l+n-1}l$, which is zero unless $l\geq0$ and otherwise equal to $\binom{l+n-1}{n-1}$. It remains to sum over all $k+l=N$, which gives $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom nq\binom{N-q(r+1)+n-1}{n-1}, $$ where the summation is truncated to ensure that $N-q(r+1)\geq0$ (the condition $l\geq0$). Although the summation looks complicated, it has at most $n+1$ easily computed terms, for any$~N$. Just to illustrate, the coefficient for $n=5$, $r=100$ and $N=243$ is easily computed to be $62018665$. An interesting point to remark is that if the summation had not been truncated, then the result would clearly have been a polynomial function of$~N$ of degree${}<n$ (because binomial coefficients $\binom xk$ are polynomial functions of$~x$ of degree$~k$). But that polynomial function gives the exact values of this problem for $N\geq n(r+1)$, but given the original problem those values are all$~0$, so the polynomial function will be identically zero! So an alternative formula for the result is to compute the negative of the truncated terms, which formula becomes after some massaging $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom nq\binom{q(r+1)-1-N}{n-1}, $$ which is easier to use for large$~N$. For instance in the above example this formula gives a single term $\binom{78}4=1426425$ for $N=426$; it is the same value as obtained for $N=74=500-426$ (from the first formula) which can be understood by the fact that the "remainders" $r_i-a_i$ add up to $nr-N$.

In the general case of distinct limits $r_i$, the approach is the same, but the formula becomes a bit messy. Instead of a numerator $(1-X^{r+1})^n$ one gets a product $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ which in general has more nonzero terms, up to $\min(\Sigma r_i+n+1,2^n)$, but can be computed once and for all. With $P=\sum_ic_iX^{e_i}$, the formula for the result becomes $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ which still is a sum of a number of terms independent of$~N$. But of course just computing the polynomial $\frac P{(1-X)^n}$ and looking up the coefficient of $X^N$ is another essentially constant-time solution.

There is as far as I know no closed formula for this general problem, but there is a formula that allows the number of solutions to be computed in a number of operations independent of $N$. Consider first the case that all limits are equal $r_1=r_2=\cdots=r_n=r$. Then the number is the coefficient of $X^N$ in the polynomial $(1+X+\cdots+X^r)^n$. By writing this as a rational function of$~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ the coeffiecient of $X^k$ in the numerator is zero unless $k$ is a multiple $q(r+1)$ of $r+1$, in which case it is $(-1)^q\binom nq$, and the coefficient of $X^l$ in the inverse of the denominator is $(-1)^l\binom{-n}l=\binom{l+n-1}l$, which is zero unless $l\geq0$ and otherwise equal to $\binom{l+n-1}{n-1}$. It remains to sum over all $k+l=N$, which gives $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom nq\binom{N-q(r+1)+n-1}{n-1}, $$ where the summation is truncated to ensure that $N-q(r+1)\geq0$ (the condition $l\geq0$). Although the summation looks complicated, it has at most $n+1$ easily computed terms, for any$~N$. Just to illustrate, the coefficient for $n=5$, $r=100$ and $N=243$ is easily computed to be $62018665$. An interesting point to remark is that if the summation had not been truncated, then the result would clearly have been a polynomial function of$~N$ of degree${}<n$ (because binomial coefficients $\binom xk$ are polynomial functions of$~x$ of degree$~k$). But on one hand that polynomial function gives the exact values of this problem for $N\geq n(r+1)$ where no truncation takes place, while on the other hand, given the original problem, those values are all$~0$; so the polynomial function will be identically zero! So an alternative formula for the result is to compute the negative of the truncated terms, which formula becomes after some massaging $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom nq\binom{q(r+1)-1-N}{n-1}, $$ which is easier to use for large$~N$. For instance in the above example this formula gives a single term $\binom{78}4=1426425$ for $N=426$; it is the same value as obtained for $N=74=500-426$ (from the first formula) which can be understood by the fact that the "remainders" $r_i-a_i$ add up to $nr-N$.

In the general case of distinct limits $r_i$, the approach is the same, but the formula becomes a bit messy. Instead of a numerator $(1-X^{r+1})^n$ one gets a product $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ which in general has more nonzero terms (the number of terms can be up to $\min(\Sigma r_i+n+1,2^n)$), but which can be computed once and for all. With $P=\sum_ic_iX^{e_i}$, the formula for the result becomes $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ which still is a sum of a number of terms independent of$~N$. But of course computing the polynomial $\frac P{(1-X)^n}$ beforehand, and then for any $N$ just looking up the coefficient of $X^N$, is another essentially constant-time (in $N$) solution.

corrected binomial coefficients
Source Link
Marc van Leeuwen
  • 116.1k
  • 8
  • 170
  • 352

There is as far as I know no closed formula for this general problem, but there is a formula that allows the number of solutions to be computed in a number of operations independent of $N$. Consider first the case that all limits are equal $r_1=r_2=\cdots=r_n=r$. Then the number is the coefficient of $X^N$ in the polynomial $(1+X+\cdots+X^r)^n$. By writing this as a rational function of$~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ the coeffiecient of $X^k$ in the numerator is zero unless $k$ is a multiple $q(r+1)$ of $r+1$, in which case it is $(-1)^q\binom qn$$(-1)^q\binom nq$, and the coefficient of $X^l$ in the inverse of the denominator is $(-1)^l\binom{-n}l=\binom{l+n-1}l$, which is zero unless $l\geq0$ and otherwise equal to $\binom{l+n-1}{n-1}$. It remains to sum over all $k+l=N$, which gives $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom qn\binom{N-q(r+1)+n-1}{n-1}, $$$$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom nq\binom{N-q(r+1)+n-1}{n-1}, $$ where the summation is truncated to ensure that $N-q(r+1)\geq0$ (the condition $l\geq0$). Although the summation looks complicated, it has at most $n+1$ easily computed terms, for any$~N$. Just to illustrate, the coefficient for $n=5$, $r=100$ and $N=243$ is easily computed to be $62018665$. An interesting point to remark is that if the summation had not been truncated, then the result would clearly have been a polynomial function of$~N$ of degree${}<n$ (because binomial coefficients $\binom xk$ are polynomial functions of$~x$ of degree$~k$). But that polynomial function gives the exact values of this problem for $N\geq n(r+1)$, but given the original problem those values are all$~0$, so the polynomial function will be identically zero! So an alternative formula for the result is to compute the negative of the truncated terms, which formula becomes after some massaging $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom qr\binom{q(r+1)-1-N}{n-1}, $$$$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom nq\binom{q(r+1)-1-N}{n-1}, $$ which is easier to use for large$~N$. For instance in the above example this formula gives a single term $\binom{78}4=1426425$ for $N=426$; it is the same value as obtained for $N=74=500-426$ (from the first formula) which can be understood by the fact that the "remainders" $r_i-a_i$ add up to $nr-N$.

In the general case of distinct limits $r_i$, the approach is the same, but the formula becomes a bit messy. Instead of a numerator $(1-X^{r+1})^n$ one gets a product $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ which in general has more nonzero terms, up to $\min(\Sigma r_i+n+1,2^n)$, but can be computed once and for all. With $P=\sum_ic_iX^{e_i}$, the formula for the result becomes $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ which still is a sum of a number of terms independent of$~N$. But of course just computing the polynomial $\frac P{(1-X)^n}$ and looking up the coefficient of $X^N$ is another essentially constant-time solution.

There is as far as I know no closed formula for this general problem, but there is a formula that allows the number of solutions to be computed in a number of operations independent of $N$. Consider first the case that all limits are equal $r_1=r_2=\cdots=r_n=r$. Then the number is the coefficient of $X^N$ in the polynomial $(1+X+\cdots+X^r)^n$. By writing this as a rational function of$~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ the coeffiecient of $X^k$ in the numerator is zero unless $k$ is a multiple $q(r+1)$ of $r+1$, in which case it is $(-1)^q\binom qn$, and the coefficient of $X^l$ in the inverse of the denominator is $(-1)^l\binom{-n}l=\binom{l+n-1}l$, which is zero unless $l\geq0$ and otherwise equal to $\binom{l+n-1}{n-1}$. It remains to sum over all $k+l=N$, which gives $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom qn\binom{N-q(r+1)+n-1}{n-1}, $$ where the summation is truncated to ensure that $N-q(r+1)\geq0$ (the condition $l\geq0$). Although the summation looks complicated, it has at most $n+1$ easily computed terms, for any$~N$. Just to illustrate, the coefficient for $n=5$, $r=100$ and $N=243$ is easily computed to be $62018665$. An interesting point to remark is that if the summation had not been truncated, then the result would clearly have been a polynomial function of$~N$ of degree${}<n$ (because binomial coefficients $\binom xk$ are polynomial functions of$~x$ of degree$~k$). But that polynomial function gives the exact values of this problem for $N\geq n(r+1)$, but given the original problem those values are all$~0$, so the polynomial function will be identically zero! So an alternative formula for the result is to compute the negative of the truncated terms, which formula becomes after some massaging $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom qr\binom{q(r+1)-1-N}{n-1}, $$ which is easier to use for large$~N$. For instance in the above example this formula gives a single term $\binom{78}4=1426425$ for $N=426$; it is the same value as obtained for $N=74=500-426$ (from the first formula) which can be understood by the fact that the "remainders" $r_i-a_i$ add up to $nr-N$.

In the general case of distinct limits $r_i$, the approach is the same, but the formula becomes a bit messy. Instead of a numerator $(1-X^{r+1})^n$ one gets a product $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ which in general has more nonzero terms, up to $\min(\Sigma r_i+n+1,2^n)$, but can be computed once and for all. With $P=\sum_ic_iX^{e_i}$, the formula for the result becomes $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ which still is a sum of a number of terms independent of$~N$. But of course just computing the polynomial $\frac P{(1-X)^n}$ and looking up the coefficient of $X^N$ is another essentially constant-time solution.

There is as far as I know no closed formula for this general problem, but there is a formula that allows the number of solutions to be computed in a number of operations independent of $N$. Consider first the case that all limits are equal $r_1=r_2=\cdots=r_n=r$. Then the number is the coefficient of $X^N$ in the polynomial $(1+X+\cdots+X^r)^n$. By writing this as a rational function of$~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ the coeffiecient of $X^k$ in the numerator is zero unless $k$ is a multiple $q(r+1)$ of $r+1$, in which case it is $(-1)^q\binom nq$, and the coefficient of $X^l$ in the inverse of the denominator is $(-1)^l\binom{-n}l=\binom{l+n-1}l$, which is zero unless $l\geq0$ and otherwise equal to $\binom{l+n-1}{n-1}$. It remains to sum over all $k+l=N$, which gives $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom nq\binom{N-q(r+1)+n-1}{n-1}, $$ where the summation is truncated to ensure that $N-q(r+1)\geq0$ (the condition $l\geq0$). Although the summation looks complicated, it has at most $n+1$ easily computed terms, for any$~N$. Just to illustrate, the coefficient for $n=5$, $r=100$ and $N=243$ is easily computed to be $62018665$. An interesting point to remark is that if the summation had not been truncated, then the result would clearly have been a polynomial function of$~N$ of degree${}<n$ (because binomial coefficients $\binom xk$ are polynomial functions of$~x$ of degree$~k$). But that polynomial function gives the exact values of this problem for $N\geq n(r+1)$, but given the original problem those values are all$~0$, so the polynomial function will be identically zero! So an alternative formula for the result is to compute the negative of the truncated terms, which formula becomes after some massaging $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom nq\binom{q(r+1)-1-N}{n-1}, $$ which is easier to use for large$~N$. For instance in the above example this formula gives a single term $\binom{78}4=1426425$ for $N=426$; it is the same value as obtained for $N=74=500-426$ (from the first formula) which can be understood by the fact that the "remainders" $r_i-a_i$ add up to $nr-N$.

In the general case of distinct limits $r_i$, the approach is the same, but the formula becomes a bit messy. Instead of a numerator $(1-X^{r+1})^n$ one gets a product $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ which in general has more nonzero terms, up to $\min(\Sigma r_i+n+1,2^n)$, but can be computed once and for all. With $P=\sum_ic_iX^{e_i}$, the formula for the result becomes $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ which still is a sum of a number of terms independent of$~N$. But of course just computing the polynomial $\frac P{(1-X)^n}$ and looking up the coefficient of $X^N$ is another essentially constant-time solution.

Source Link
Marc van Leeuwen
  • 116.1k
  • 8
  • 170
  • 352

There is as far as I know no closed formula for this general problem, but there is a formula that allows the number of solutions to be computed in a number of operations independent of $N$. Consider first the case that all limits are equal $r_1=r_2=\cdots=r_n=r$. Then the number is the coefficient of $X^N$ in the polynomial $(1+X+\cdots+X^r)^n$. By writing this as a rational function of$~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ the coeffiecient of $X^k$ in the numerator is zero unless $k$ is a multiple $q(r+1)$ of $r+1$, in which case it is $(-1)^q\binom qn$, and the coefficient of $X^l$ in the inverse of the denominator is $(-1)^l\binom{-n}l=\binom{l+n-1}l$, which is zero unless $l\geq0$ and otherwise equal to $\binom{l+n-1}{n-1}$. It remains to sum over all $k+l=N$, which gives $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom qn\binom{N-q(r+1)+n-1}{n-1}, $$ where the summation is truncated to ensure that $N-q(r+1)\geq0$ (the condition $l\geq0$). Although the summation looks complicated, it has at most $n+1$ easily computed terms, for any$~N$. Just to illustrate, the coefficient for $n=5$, $r=100$ and $N=243$ is easily computed to be $62018665$. An interesting point to remark is that if the summation had not been truncated, then the result would clearly have been a polynomial function of$~N$ of degree${}<n$ (because binomial coefficients $\binom xk$ are polynomial functions of$~x$ of degree$~k$). But that polynomial function gives the exact values of this problem for $N\geq n(r+1)$, but given the original problem those values are all$~0$, so the polynomial function will be identically zero! So an alternative formula for the result is to compute the negative of the truncated terms, which formula becomes after some massaging $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom qr\binom{q(r+1)-1-N}{n-1}, $$ which is easier to use for large$~N$. For instance in the above example this formula gives a single term $\binom{78}4=1426425$ for $N=426$; it is the same value as obtained for $N=74=500-426$ (from the first formula) which can be understood by the fact that the "remainders" $r_i-a_i$ add up to $nr-N$.

In the general case of distinct limits $r_i$, the approach is the same, but the formula becomes a bit messy. Instead of a numerator $(1-X^{r+1})^n$ one gets a product $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ which in general has more nonzero terms, up to $\min(\Sigma r_i+n+1,2^n)$, but can be computed once and for all. With $P=\sum_ic_iX^{e_i}$, the formula for the result becomes $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ which still is a sum of a number of terms independent of$~N$. But of course just computing the polynomial $\frac P{(1-X)^n}$ and looking up the coefficient of $X^N$ is another essentially constant-time solution.