Results 1 to 13 of 13

Math Help - 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,527
    Thanks
    773
    One way is to find the coefficient of x^{10} in the expansion of (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,527
    Thanks
    773
    You could also try brute force. Consider the following table. Let a_{i,j} be the element at row i and column j. We want a_{i,j} be the number of solutions of x_1+\dots+x_i=j where 1\le x_k\le 4 for all 1\le k\le i.

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

    The non-bold elements of the table are computed directly. Next, for i>1 and j>4, we have 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,527
    Thanks
    773
    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 y_i's, namely, 6, and let m be the maximum of y_i's, namely, 3. What makes it easy to subtract the number of variants where some y_i>m is that s\le 2m+1. In this case, when y_1=m+1, y_2+y_3+y_4=s-(m+1)\le m, so the restriction that y_i\le m does not have to be taken into account and the number of solutions of 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

    f(x) = (x + x^2 + x^3 + x^4)^4
    = x^4 (1 + x + x^2 + x^3)^4
    =x^4 \left( \frac{1-x^4}{1-x} \right) ^4
    =x^4 (1-x^4)^4 (1-x)^{-4}
    =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

    \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
    11,707
    Thanks
    626
    Hello, Ginsburg!

    A slight variation of emarakov's solution . . .


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

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

    . . \begin{array}{ccc}<br />
x_1,x_2,x_3,x_4 & \text{Permutations} \\ \hline \\[-4mm]<br />
(1,1,4,4) &  \frac{4!}{2!\,2!} \;=\;6 \\ \\[-3mm]<br />
(1,2,3,4) & 4! \;\;=\;24 \\ \\[-3mm]<br />
(1,3,3,3) & \frac{4!}{1!\,3!} \;=\;4 \\ \\[-3mm]<br />
(2,2,2,4) & \frac{4!}{3!\,1!} \;=\;4 \\ \\[-3mm]<br />
(2,2,3,3) & \frac{4!}{2!\,2!} \;=\;6 \\ \\[-4mm] \hline \\[-4mm]<br />
\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

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

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

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

    Number of solutions to

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

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

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

    z + y_2 + y_3 + y_4 = 6 - 4 = 2

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

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

    Subtracting invalid solutions, the number of possible solutions is:

    \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
    4
    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

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

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

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

    Number of solutions to

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

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

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

    z + y_2 + y_3 + y_4 = 6 - 4 = 2

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

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

    Subtracting invalid solutions, the number of possible solutions is:

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

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

    CB
    Last edited by CaptainBlack; December 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
    4
    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: October 7th 2011, 02:32 AM
  2. Replies: 2
    Last Post: September 14th 2011, 06:43 PM
  3. Number of solutions to an equation.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 11th 2010, 07:08 PM
  4. [SOLVED] Number of solutions of arctan equation?
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: September 24th 2008, 09:24 AM
  5. solutions of systems of linear equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 20th 2006, 05:14 AM

Search Tags


/mathhelpforum @mathhelpforum