Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of solutions

  1. Aug 9, 2012 #1
    Hi there,
    I know that the number of solutions of [itex]a_{1}+a_{2}+...a_{n}=k [/itex] where [itex]a_{i} [/itex] are non-negative integers is just [itex]\binom{n+k-1}{k} [/itex].

    Now, given a [itex]m\times n [/itex] matrix with non negative integers [itex]a_{ij}[/itex], how many solutions are there for the following kind of system?
    [itex]\begin{array}{ccccccccc}
    s_{1} & & s_{2} & & & & s_{n}\\
    \shortparallel & & \shortparallel & & & & \shortparallel\\
    a_{11} & + & a_{12} & + & ... & + & a_{1n} & = & k_{1}\\
    + & & + & & & & +\\
    a_{21} & + & a_{22} & + & ... & + & a_{2n} & = & k_{2}\\
    + & & + & & & & +\\
    \vdots & & \vdots & & & & \vdots\\
    + & & + & & & & +\\
    a_{m1} & + & a_{m2} & + & ... & + & a_{mn} & = & k_{m}
    \end{array} [/itex]

    The sum of each row and each column is constrained by the known non-negative integers [itex]k_{i}[/itex] and [itex]s_{i}[/itex].

    Without the column restriction we would have [itex]\prod_{i=1}^{m}\binom{n+k_{i}-1}{k_{i}} [/itex].

    Thanks a lot.
     
  2. jcsd
  3. Aug 9, 2012 #2

    Bacle2

    User Avatar
    Science Advisor

    I would say that the size of the solution decreases the more constraints you put on

    the values. If my generic a_mn has to satisfy two equations ; horizontal and vertical,

    then it becomes harder to find such a value.
     
    Last edited: Aug 9, 2012
  4. Aug 9, 2012 #3
    Shouldn't there be a combinatorial trick? I mean here is an example for [itex]\left(i_{1},i_{2}\right)=\left(5,3\right)[/itex] and [itex]n=3[/itex] . The system becomes

    [itex]\begin{array}{ccccccc}
    s_{1} & & s_{2} & & s_{3}\\
    \shortparallel & & \shortparallel & & \shortparallel\\
    a_{11} & + & a_{12} & + & a_{13} & = & 5\\
    + & & + & & +\\
    a_{21} & + & a_{22} & + & a_{23} & = & 3
    \end{array} [/itex]

    Starting considering only the horizontal equations, trivially the solutions are any combination of the following two columns

    [itex]\begin{array}{ccc}
    a_{11}\: a_{12}\: a_{13} & & a_{21}\: a_{22}\: a_{23}\\
    \\
    500 & & 300\\
    050 & & 030\\
    005 & & 003\\
    410 & & 210\\
    401 & & 201\\
    140 & & 120\\
    104 & & 102\\
    041 & & 021\\
    014 & & 012\\
    320 & & 111\\
    302\\
    230\\
    203\\
    032\\
    023\\
    311\\
    131\\
    113\\
    221\\
    212\\
    122
    \end{array} [/itex]

    which has, as expected [itex]\binom{3+5-1}{5}\binom{3+3-1}{3}=21\cdot10 [/itex] solutions.
    Now lets consider also the vertical equations. For fixed [itex]\left(s_{1},s_{2},s_{3}\right) [/itex] some of those 210 solutions will be our final solutions. First of all in order to have solutions it must be [itex]s_{1}+s_{2}+s_{3}=5+3=8[/itex], so only the[itex]s[/itex] which satisfy this condition will contribute. For example, for [itex] \left(s_{1},s_{2},s_{3}\right)=\left(7,1,0\right)[/itex] from the previous table we select only

    [itex]\begin{array}{ccc}
    a_{11}\: a_{12}\: a_{13} & & a_{21}\: a_{22}\: a_{23}\\
    \\
    500 & & 210\\
    410 & & 300
    \end{array} [/itex]

    and thus we have two solutions. The number of solutions for all other possible [itex]\left(s_{1},s_{2},s_{3}\right) [/itex] are

    [itex] \begin{array}{ccc}
    s_{1}\: s_{2}\: s_{3}\\
    800 & \rightarrow & 1\\
    710 & \rightarrow & 2\\
    620 & \rightarrow & 3\\
    611 & \rightarrow & 4\\
    530 & \rightarrow & 4\\
    521 & \rightarrow & 6\\
    431 & \rightarrow & 7\\
    422 & \rightarrow & 8\\
    322 & \rightarrow & 9
    \end{array} [/itex]

    (permutations of the [itex]s[/itex] give the same number of solutions).
    How would one generalize all this? If [itex]\gamma[/itex] is the number of solutions of the general system, this identity is valid:

    [itex] \sum_{s_{1}+..s_{n}=k_{1}+..k_{m}}\gamma\left(s_{1},..s_{n};k_{1},..k_{m}\right)=\prod_{i=1}^{m} \binom{n+k_{i}-1}{k_{i}} [/itex]

    The point is to find that [itex]\gamma[/itex]...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number of solutions
  1. A number (Replies: 4)

  2. Lucas numbers (Replies: 1)

  3. SDE solution (Replies: 1)

Loading...