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

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

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

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

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} a_{11}\: a_{12}\: a_{13} & & a_{21}\: a_{22}\: a_{23}\\ \\ 500 & & 210\\ 410 & & 300 \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} 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}$

(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$...