1
$\begingroup$

I trying find the number of all solutions in the following:

$ x_1 + x_2 + x_3 + x_4 + x_5 = 24 $

where:

2 of variables are natural odd numbers

3 of variables are natural even numbers

none of variables are equal to $0$ or $1$ (all the variables are $>= 2$)

So I've made generating functions according to the limitations as follow:

$ (x^3 + x^5 + x^7 + ... + x^{21} + x^{23})^2 $ $ (x^2 + x^4 + x^6 + ... + x^{22} + x^{24})^3 $

Now I need to find the coefficient of $ x^{24} $

I've tried to solve it but get stuck, here is what I've done:

$ x^6(1 + x^2 + x^4 + ... + x^{18} + x^{20})^2 $ $ x^6(1 + x^2 + x^4 + ... + x^{20} + x^{22})^3 $

$ x^{12}(1 + x^2 + x^4 + ... + x^{18} + x^{20})^2(1 + x^2 + x^4 + ... + x^{20} + x^{22})^3 $

Now we actually looking for coefficient of $ x^{24-12}=x^{12} $ in:

$ (1 + x^2 + x^4 + ... + x^{18} + x^{20})^2(1 + x^2 + x^4 + ... + x^{20} + x^{22})^3 $

$ (\frac{1 - x^{21}}{1 - x})^2(\frac{1 - x^{23}}{1 - x})^3 $

Here I'm stuck. How to proceed in order to find coefficient of $ x^{12} $?

Regards.

PS: Solution was given but just out of curiosity, how to solve it using generating-functions?

$\endgroup$
2
$\begingroup$

Let the numbers be $2a + 1, 2b + 1, 2c, 2d, 2e$, where $a, b, c, d, e$ are natural. Note that this makes the odd numbers greater than or equal to $3$, and the even numbers greater than or equal to $2$.

Then you have $2a + 1 + 2b + 1 + 2c + 2d + 2e = 24 \rightarrow a + b + c + d + e = 11$. You can solve this with a standard stars-and-bars approach.

$\endgroup$
  • $\begingroup$ That's very nice! But just out of curiosity, how to solve it using generating-functions? $\endgroup$ – Mike Jun 15 '15 at 17:13
  • $\begingroup$ Doesn't this approach suffer from positioning the two odd summands first and the even summands last, a restriction not imposed in the Question? $\endgroup$ – hardmath Jun 15 '15 at 19:10
  • $\begingroup$ @hardmath You bring up a good point. It looks like the numbers can be in any order, so I guess we can just multiply by $\binom{5}{2}$ in the end? $\endgroup$ – Ashkay Jun 15 '15 at 19:13
  • $\begingroup$ Maybe the rearrangements are built in to your calculation. If you take $\binom{10}{4}$ in stars-and-bars, you get $210$ like I got. I'm a bit confused by this. $\endgroup$ – hardmath Jun 15 '15 at 19:28
  • $\begingroup$ @hardmath isn't that should be $\binom{11+5-1}{11}$ so instead you get $\binom{15}{11} = 1365$ $\endgroup$ – Mike Jun 15 '15 at 19:53
1
$\begingroup$

Let's take it from the point where we ask for the coefficient of $x^{12}$ in:

$$ (1 + x^2 + x^4 + ... + x^{18} + x^{20})^2(1 + x^2 + x^4 + ... + x^{20} + x^{22})^3 $$

[Note, however, that a factor of $\binom{5}{2}=10$ is already left out of the calculation at this point, which would account for varying positions of the two odd summands $x_i$. See the comments on Ashtay's Answer for more details.]

Replace $x^2$ with $y$ and ask for the coefficient of $y^6$:

$$ (1 + y + y^2 + \ldots + y^9 + y^{10})^2 (1 + y + y^2 + \ldots + y^{10} + y^{11})^3 $$

Of course we can remove all polynomial in $y$ terms with exponents greater than $6$ since these cannot contribute to the coefficient of $y^6$, then notice the polynomial factors are now equal:

$$ (1 + y + y^2 + \ldots + y^6)^5 $$

We can continue to explicitly work out the coefficient of $y^6$ by repeated squarings (and removing terms beyond $y^6$):

$$ (1 + y + \ldots + y^6)^2 \; \to \; (1 + 2y + 3y^2 + 4y^3 + 5y^4 + 6y^5 + 7y^6) $$

$$ (1 + 2y + 3y^2 + \ldots + 7y^6)^2 \; \to \; (1 + 4y + 10y^2 + 20y^3 + 35y^4 + 56y^5 + 84y^6) $$

Multiplication by $(1+y+y^2+\ldots + y^6)$ of the last result gives the desired term $210y^6$. It follows that $210$ was the original coefficient of $x^{24}$ you wanted (if my arithmetic is right!).

$\endgroup$
  • $\begingroup$ Thanks a lot, it looks very good! Is there any other (less tedious) way to get the desired coefficient of $y^6$ out of $(1+y+y^2+y^3+y^4+y^5+y^6)^5$? $\endgroup$ – Mike Jun 15 '15 at 19:30
  • $\begingroup$ The method of @Ashkay, i.e. stars-and-bars, works on that as well and reduces it to computing the sums of $5$ nonnegative integers that add up to $6$, $\binom{6+4}{4} = 210$. $\endgroup$ – hardmath Jun 15 '15 at 19:46

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.