0
$\begingroup$

What is the number of solutions to $(x_1+x_2+x_3)(x_4+x_5+x_6+x_7)=77$, where $x_1,x_2,\dots,x_6,x_7$ are non negative integers? Obviously the $2$ multipliers are $1 \times 77$ and $7 \times 11$, so we have $x_1+x_2+x_3 = 1,7,11,77$ and $x_4+x_5+x_6+x_7 = 1,7,11,77$.

$\endgroup$
5
  • $\begingroup$ Have you heard of stars and bars? $\endgroup$
    – octave
    Mar 22 at 22:25
  • $\begingroup$ Obviously I am not an expert... $\endgroup$
    – Avi Tal
    Mar 22 at 22:26
  • $\begingroup$ You should reverse one of $1,7,11,77$. $\endgroup$
    – user
    Mar 22 at 22:28
  • 3
    $\begingroup$ That's alright. It turns out that the number of nonnegative integer solutions to $x_1+x_2+\cdots+x_k = n$ is $\binom{n+k-1}{n}$, where $\binom{}{}$ is the binomial coefficient. A reference can be found at math.stackexchange.com/questions/910809/…. For your problem, you can handle the cases separately: the number of ways for $x_1 + x_2 + x_3 = 1$ and $x_4 + x_5 + x_6 + x_7 = 77$, etc. $\endgroup$
    – octave
    Mar 22 at 22:30
  • $\begingroup$ @octave - Would you like to post this as an answer? $\endgroup$
    – Avi Tal
    Mar 22 at 22:37
2
$\begingroup$

Recall the method of "stars and bars," which tells us that the number of nonnegative integer solutions to the equation $$ x_1 + x_2 + \cdots + x_k = n $$ is $$ \binom{n+k-1}{n}. $$

There are four cases, as you pointed out. The tuple $(x_1 + x_2 + x_3, x_4 + x_5 + x_6 + x_7)$ can only equal $(1, 77)$, $(7, 11)$, $(11, 7)$, or $(77, 1)$. In the first case, where $x_1 + x_2 + x_3 = 1$ and $x_4+x_5+x_6+x_7=77$, the number of solutions is $$ \binom{3}{1}\binom{80}{77}. $$

Applying this reasoning for the other three cases, we get that the total number of solutions is $$ \binom{3}{1}\binom{80}{77} + \binom{9}{7}\binom{14}{11} + \binom{13}{11}\binom{10}{7} + \binom{79}{77}\binom{4}{1}. $$

$\endgroup$
2
  • $\begingroup$ Thanks allot for your answer! And how about this: |x|+|y|+|z| = 30? Without the absolute value I get 32 choose 30 (496). With the absolutes my intuition was to multiply this by 8, but I actually get 3602 and I don't know why... $\endgroup$
    – Avi Tal
    Mar 23 at 5:06
  • $\begingroup$ You can ask a separate question (not in these comments) if it’s a different equation. $\endgroup$
    – octave
    Mar 23 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.