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} & & s_{2} & & & & s_{n}\\<br /> \shortparallel & & \shortparallel & & & & \shortparallel\\<br /> a_{11} & + & a_{12} & + & ... & + & a_{1n} & = & k_{1}\\<br /> + & & + & & & & +\\<br /> a_{21} & + & a_{22} & + & ... & + & a_{2n} & = & k_{2}\\<br /> + & & + & & & & +\\<br /> \vdots & & \vdots & & & & \vdots\\<br /> + & & + & & & & +\\<br /> a_{m1} & + & a_{m2} & + & ... & + & a_{mn} & = & 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} & & s_{2} & & s_{3}\\<br /> \shortparallel & & \shortparallel & & \shortparallel\\<br /> a_{11} & + & a_{12} & + & a_{13} & = & 5\\<br /> + & & + & & +\\<br /> a_{21} & + & a_{22} & + & a_{23} & = & 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} & & a_{21}\: a_{22}\: a_{23}\\<br /> \\<br /> 500 & & 300\\<br /> 050 & & 030\\<br /> 005 & & 003\\<br /> 410 & & 210\\<br /> 401 & & 201\\<br /> 140 & & 120\\<br /> 104 & & 102\\<br /> 041 & & 021\\<br /> 014 & & 012\\<br /> 320 & & 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 the$s$ 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} & & a_{21}\: a_{22}\: a_{23}\\<br /> \\<br /> 500 & & 210\\<br /> 410 & & 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 & \rightarrow & 1\\<br /> 710 & \rightarrow & 2\\<br /> 620 & \rightarrow & 3\\<br /> 611 & \rightarrow & 4\\<br /> 530 & \rightarrow & 4\\<br /> 521 & \rightarrow & 6\\<br /> 431 & \rightarrow & 7\\<br /> 422 & \rightarrow & 8\\<br /> 322 & \rightarrow & 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$...