I want to find the number of positive integer solutions of the equations given by
$$\sum_{i=1}^{10} x_i=30,\text{ where } 0 < x_i<7, \forall 1\le i\le 10.$$
I know the case that, for any pair of positive integers $n$ and $k$, the number of distinct $k$-tuples of positive integers whose sum is $n$ is given by the binomial coefficient ${n-1}\choose {k-1}$.
But, in my case there is a restriction of solutions that, for all $i$ we must have $0<x_i<7$, where $x_i$ are positive integers. Please help me to solve this. Thank you.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ For starters, you can subtract $1$ from all $x_i$ to get $\sum = 20$ and $0 \le x_i \le 5.$ $\endgroup$– Display nameCommented Sep 4, 2023 at 20:40
-
$\begingroup$ See here math.stackexchange.com/questions/21645/restricted-compositions $\endgroup$– leonbloyCommented Sep 4, 2023 at 20:49
-
1$\begingroup$ See also this answer. $\endgroup$– user2661923Commented Sep 4, 2023 at 21:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Following my comment, you can use Principle of Inclusion Exclusion. First find all ways (no upper bound on $x_i$), then subtract off number of ways given $x_1 > 5,$ given $x_2 > 5, \dots,$ given $x_{10} > 5,$ then add back number of ways given $x_i, x_j > 5$ for every $\{i, j\},$ then subtract off number of ways given $x_i, x_j, x_k > 5,$ you get the idea.
-
$\begingroup$ See my comment following the original posting. $\endgroup$ Commented Sep 5, 2023 at 2:26
$\begingroup$
$\endgroup$
7
Computing $(x+x^2+x^3+x^4+x^5+x^6)^{10}$ with Wolfram gives a coefficient of $2930455$ to $x^{30}$.
-
$\begingroup$ Hooray for generating functions! I believe they are the simplest and most powerful way to address questions like this $\endgroup$ Commented Sep 4, 2023 at 22:53
-
$\begingroup$ @H.sapiensrex However, a case can be made that such a use of generating functions is pointless, because (apparently) there is no elegant way of completing the problem without computer assistance. Then, if you compromise and allow computer assistance, you can simply programmatically loop through all possible ordered $~k$-tuples, where each $~k$-tuple represents the values assigned to $~x_1, \cdots, x_k.~$ From my perspective, either you are using computer assistance or you're not. My comment following the original posting provides a link to a completely analytical approach. $\endgroup$ Commented Sep 5, 2023 at 2:26
-
$\begingroup$ Generating functions are often the best approach. I agree an analytical approach would be better (not sure if your link applies since you never actually give a full formula that I could compute, though if you could calculate like 40 binomials without a computer, then I guess your approach might work). A neat hybrid approach would be to to compute $(x/(1-x)-x^7/(1-x))^n$ as a binomial sum (equivalent to PIE) and then substitute for the $1/(1-x)^j$ terms with a sum of binomial coefficients (like stars and bars). $\endgroup$– EricCommented Sep 5, 2023 at 4:26
-
1$\begingroup$ Separately, it’s little odd to comment on other answers saying that yours is better - we should probably just close the question if this is a duplicate. $\endgroup$– EricCommented Sep 5, 2023 at 4:29
-
$\begingroup$ @Eric The point of my comment is that if you are going to post an answer involving generating functions, then at least some attempt should be made to provide an analytical method of computing the corresponding coefficient. At MathSE, there seems to be a pervasive trend towards generating functions as a replacement for [Stars and Bars + Incl.-Excl], without any discussion of some analytical means of computing the corresponding coefficient. ...see next comment $\endgroup$ Commented Sep 5, 2023 at 7:50