Results 1 to 13 of 13

Thread: Number of solutions to linear equation

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    8

    Number of solutions to linear equation

    How many solutions are there to the equation x1+x2+x3+x4 = 10, where for every i, 1 <= xi <= 4 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    One way is to find the coefficient of $\displaystyle x^{10}$ in the expansion of $\displaystyle (x^4+x^3+x^2+x)^4$, which can be done in WolframAlpha. I would not say that this restatement makes the counting easier; it just reduces the problem to a well-known question for which automatic tools exist.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    8
    Can you solve it without that trick? I mean without using automatic tools, let's say its a question on the test, what would you do then?:P
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    You could also try brute force. Consider the following table. Let $\displaystyle a_{i,j}$ be the element at row $\displaystyle i$ and column $\displaystyle j$. We want $\displaystyle a_{i,j}$ be the number of solutions of $\displaystyle x_1+\dots+x_i=j$ where $\displaystyle 1\le x_k\le 4$ for all $\displaystyle 1\le k\le i$.

    $\displaystyle
    \begin{array}{c|cccccccccc}
    & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
    \hline
    1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
    2 & 0 & 1 & 2 & 3 & 4 & 3 & 2 & 1 & 0 & 0\\
    3 & 0 & 0 & 1 & & & \mathbf{10} & \mathbf{12} & \mathbf{12} & \mathbf{10} & \\
    4 & 0 & 0 & 0 & 1 & & & & & & \mathbf{44}
    \end{array}
    $

    The non-bold elements of the table are computed directly. Next, for $\displaystyle i>1$ and $\displaystyle j>4$, we have $\displaystyle a_{i,j}=a_{i-1,j-4}+a_{i-1,j-3}+a_{i-1,j-2}+a_{i-1,j-1}$.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    8
    OK, its nice and all, I have tried to solve it in a different way that seems so correct but doesn't work and I'm confused. Look what I did:

    because xi >= 1 we can change variable to xi = yi + 1 then we have y1 + 1 + y2 + 1 + y3 + 1 + y4 + 1 = 10 => y1+y2+y3+y4= 6. now we want to find the number of solutions to y1+y2+y3+y4= 6 where for every i, 0<=yi<=4.
    for getting the number of solutions to the latter equation where yi >=0, we can use the formula for dividing 6 identical objects into 4 different boxes it's |U|= nCr(4-1+6,4-1)=84, the size of our universe. now we can use the inclusion & exclusion in order to find number of solutions where y1 >= 5 or y2 >= 5 or y3 >= 5 or y4 >= 5, there are only 16 such solutions. so the final answer is 84-16=68. but the answer is incorrect. where is my mistake? I cant figure it out, just looking for it for hours.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2010
    Posts
    8
    oh, just one little detail that makes a big different, it should be yi <=3 instead of 4, but thanks!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    because xi >= 1 we can change variable to xi = yi + 1 then we have y1 + 1 + y2 + 1 + y3 + 1 + y4 + 1 = 10 => y1+y2+y3+y4= 6. now we want to find the number of solutions to y1+y2+y3+y4= 6 where for every i, 0<=yi<=4.
    It should be, 0 <= y_i <= 3.

    Your method is otherwise correct. I was just looking into it at this thread. Let s be the sum of all $\displaystyle y_i$'s, namely, 6, and let m be the maximum of $\displaystyle y_i$'s, namely, 3. What makes it easy to subtract the number of variants where some $\displaystyle y_i>m$ is that $\displaystyle s\le 2m+1$. In this case, when $\displaystyle y_1=m+1$, $\displaystyle y_2+y_3+y_4=s-(m+1)\le m$, so the restriction that $\displaystyle y_i\le m$ does not have to be taken into account and the number of solutions of $\displaystyle y_2+y_3+y_4=s-(m+1)$ can be calculated by the general formula.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    You don't need alpha for this one

    Here is a way to get the coefficient of x^10 from the generating function. The ordinary power series generating function (as already noted) is

    $\displaystyle f(x) = (x + x^2 + x^3 + x^4)^4$
    $\displaystyle = x^4 (1 + x + x^2 + x^3)^4$
    $\displaystyle =x^4 \left( \frac{1-x^4}{1-x} \right) ^4$
    $\displaystyle =x^4 (1-x^4)^4 (1-x)^{-4}$
    $\displaystyle =x^4 (1 -4x^4 + 6x^8 -4x^{12} + x^{16}) \sum_{i=0}^{\infty} \binom{4+i-1}{i} x^i$

    Looking at the last equation, we can see the coefficient of x^10 is

    $\displaystyle \binom{9}{3} - 4 \binom{5}{2}$
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    849
    Hello, Ginsburg!

    A slight variation of emarakov's solution . . .


    $\displaystyle \text{How many solutions are there to the equation}$

    . . $\displaystyle x_1+x_2+x_3+x_4 \:=\: 10\:\text{ where }1 \le x_i \le 4\,?$

    . . $\displaystyle \begin{array}{ccc}
    x_1,x_2,x_3,x_4 & \text{Permutations} \\ \hline \\[-4mm]
    (1,1,4,4) & \frac{4!}{2!\,2!} \;=\;6 \\ \\[-3mm]
    (1,2,3,4) & 4! \;\;=\;24 \\ \\[-3mm]
    (1,3,3,3) & \frac{4!}{1!\,3!} \;=\;4 \\ \\[-3mm]
    (2,2,2,4) & \frac{4!}{3!\,1!} \;=\;4 \\ \\[-3mm]
    (2,2,3,3) & \frac{4!}{2!\,2!} \;=\;6 \\ \\[-4mm] \hline \\[-4mm]
    \text{Total:} & \qquad\quad 44 \end{array}$

    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    By the Erdos principle, there is always a simple explanation for a simple answer

    Ginsburg was quite close in an earlier post.

    Number of solutions to

    $\displaystyle x_1 + x_2 + x_3 + x_4 = 10$
    with $\displaystyle 1 \leq x_i \leq 4$

    is the number of solutions to (substitue $\displaystyle y_i = x_i - 1$)

    $\displaystyle y_1 + y_2 + y_3 + y_4 = 10 - 4 = 6$
    with $\displaystyle 0 \leq y_i \leq 3$

    Number of solutions to

    $\displaystyle y_1 + y_2 + y_3 + y_4 = 6$
    with $\displaystyle 0 \leq y_i$

    is $\displaystyle \binom{6 + 4 - 1}{4 - 1} = \binom{9}{3}$

    We need to throw away solutions where one of $\displaystyle y_i \geq 4$.
    For the case of $\displaystyle y_1 \geq 4$, let $\displaystyle z = y_1 - 4$, the number of solutions to

    $\displaystyle z + y_2 + y_3 + y_4 = 6 - 4 = 2$

    is $\displaystyle \binom{2 + 4 - 1}{4 - 1} = \binom{5}{3}$

    Since exactly one of $\displaystyle y_i$ could be larger than 3 in any solution.
    We have $\displaystyle 4\binom{5}{3}$.

    Subtracting invalid solutions, the number of possible solutions is:

    $\displaystyle \binom{9}{3} - 4\binom{5}{3}$

    Consistent with awkward's solution.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by snowtea View Post
    By the Erdos principle, there is always a simple explanation for a simple answer

    Ginsburg was quite close in an earlier post.

    Number of solutions to

    $\displaystyle x_1 + x_2 + x_3 + x_4 = 10$
    with $\displaystyle 1 \leq x_i \leq 4$

    is the number of solutions to (substitue $\displaystyle y_i = x_i - 1$)

    $\displaystyle y_1 + y_2 + y_3 + y_4 = 10 - 4 = 6$
    with $\displaystyle 0 \leq y_i \leq 3$

    Number of solutions to

    $\displaystyle y_1 + y_2 + y_3 + y_4 = 6$
    with $\displaystyle 0 \leq y_i$

    is $\displaystyle \binom{6 + 4 - 1}{4 - 1} = \binom{9}{3}$

    We need to throw away solutions where one of $\displaystyle y_i \geq 4$.
    For the case of $\displaystyle y_1 \geq 4$, let $\displaystyle z = y_1 - 4$, the number of solutions to

    $\displaystyle z + y_2 + y_3 + y_4 = 6 - 4 = 2$

    is $\displaystyle \binom{2 + 4 - 1}{4 - 1} = \binom{5}{3}$

    Since exactly one of $\displaystyle y_i$ could be larger than 3 in any solution.
    We have $\displaystyle 4\binom{5}{3}$.

    Subtracting invalid solutions, the number of possible solutions is:

    $\displaystyle \binom{9}{3} - 4\binom{5}{3}$

    Consistent with awkward's solution.
    And is consistent with a direct count!

    CB
    Last edited by CaptainBlack; Dec 20th 2010 at 07:35 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    And not consistent with a direct count!

    CB
    CB, I find 44 solutions, listed below. Do you differ with that list?

    Code:
    1	1	1	4	4
    2	1	2	3	4
    3	1	2	4	3
    4	1	3	2	4
    5	1	3	3	3
    6	1	3	4	2
    7	1	4	1	4
    8	1	4	2	3
    9	1	4	3	2
    10	1	4	4	1
    11	2	1	3	4
    12	2	1	4	3
    13	2	2	2	4
    14	2	2	3	3
    15	2	2	4	2
    16	2	3	1	4
    17	2	3	2	3
    18	2	3	3	2
    19	2	3	4	1
    20	2	4	1	3
    21	2	4	2	2
    22	2	4	3	1
    23	3	1	2	4
    24	3	1	3	3
    25	3	1	4	2
    26	3	2	1	4
    27	3	2	2	3
    28	3	2	3	2
    29	3	2	4	1
    30	3	3	1	3
    31	3	3	2	2
    32	3	3	3	1
    33	3	4	1	2
    34	3	4	2	1
    35	4	1	1	4
    36	4	1	2	3
    37	4	1	3	2
    38	4	1	4	1
    39	4	2	1	3
    40	4	2	2	2
    41	4	2	3	1
    42	4	3	1	2
    43	4	3	2	1
    44	4	4	1	1
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by awkward View Post
    CB, I find 44 solutions, listed below. Do you differ with that list?

    Code:
    1	1	1	4	4
    2	1	2	3	4
    3	1	2	4	3
    4	1	3	2	4
    5	1	3	3	3
    6	1	3	4	2
    7	1	4	1	4
    8	1	4	2	3
    9	1	4	3	2
    10	1	4	4	1
    11	2	1	3	4
    12	2	1	4	3
    13	2	2	2	4
    14	2	2	3	3
    15	2	2	4	2
    16	2	3	1	4
    17	2	3	2	3
    18	2	3	3	2
    19	2	3	4	1
    20	2	4	1	3
    21	2	4	2	2
    22	2	4	3	1
    23	3	1	2	4
    24	3	1	3	3
    25	3	1	4	2
    26	3	2	1	4
    27	3	2	2	3
    28	3	2	3	2
    29	3	2	4	1
    30	3	3	1	3
    31	3	3	2	2
    32	3	3	3	1
    33	3	4	1	2
    34	3	4	2	1
    35	4	1	1	4
    36	4	1	2	3
    37	4	1	3	2
    38	4	1	4	1
    39	4	2	1	3
    40	4	2	2	2
    41	4	2	3	1
    42	4	3	1	2
    43	4	3	2	1
    44	4	4	1	1
    It is a gross typo (or a time slip)it is consistent is what the post should say, and will do presently.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: Oct 7th 2011, 02:32 AM
  2. Replies: 2
    Last Post: Sep 14th 2011, 06:43 PM
  3. Number of solutions to an equation.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 11th 2010, 07:08 PM
  4. [SOLVED] Number of solutions of arctan equation?
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: Sep 24th 2008, 09:24 AM
  5. solutions of systems of linear equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jun 20th 2006, 05:14 AM

Search Tags


/mathhelpforum @mathhelpforum