Solutions to Matrix System with Integer Constraints

[srodniki]

Hi there,
I know that the number of solutions of a_{1}+a_{2}+...a_{n}=k where a_{i} are non-negative integers is just \binom{n+k-1}{k}.

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

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

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

Thanks a lot.

 

[Bacle2]

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.

 

[srodniki]

Shouldn't there be a combinatorial trick? I mean here is an example for \left(i_{1},i_{2}\right)=\left(5,3\right) and n=3 . The system becomes

\begin{array}{ccccccc}<br /> s_{1} &amp; &amp; s_{2} &amp; &amp; s_{3}\\<br /> \shortparallel &amp; &amp; \shortparallel &amp; &amp; \shortparallel\\<br /> a_{11} &amp; + &amp; a_{12} &amp; + &amp; a_{13} &amp; = &amp; 5\\<br /> + &amp; &amp; + &amp; &amp; +\\<br /> a_{21} &amp; + &amp; a_{22} &amp; + &amp; a_{23} &amp; = &amp; 3<br /> \end{array}

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

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

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

\begin{array}{ccc}<br /> a_{11}\: a_{12}\: a_{13} &amp; &amp; a_{21}\: a_{22}\: a_{23}\\<br /> \\<br /> 500 &amp; &amp; 210\\<br /> 410 &amp; &amp; 300<br /> \end{array}

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

\begin{array}{ccc}<br /> s_{1}\: s_{2}\: s_{3}\\<br /> 800 &amp; \rightarrow &amp; 1\\<br /> 710 &amp; \rightarrow &amp; 2\\<br /> 620 &amp; \rightarrow &amp; 3\\<br /> 611 &amp; \rightarrow &amp; 4\\<br /> 530 &amp; \rightarrow &amp; 4\\<br /> 521 &amp; \rightarrow &amp; 6\\<br /> 431 &amp; \rightarrow &amp; 7\\<br /> 422 &amp; \rightarrow &amp; 8\\<br /> 322 &amp; \rightarrow &amp; 9<br /> \end{array}

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

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

The point is to find that \gamma...