Counting combinations in a table/matrice with fixed row sums and column sums

Question

I have a problem which I can't seem to google my way to. I have a table where all the sums for the rows and columns are fixed. I would like to know how to find how many possible combinations/solutions there are to the table where x$\,n$ can be any non-negative integer number. I have looked at Stars and Bars but can't find it for tables and also contingency tables but I can't find any similar examples.

Preferably I would like a general approach to this solution where I can specify any type of table $(n \times m)$ given any number of row and column sums to find the potential combinations. Could you guys help me?

Additional special case: What would happen if I forbid the combination Machine 2 and Attribute B (x5) to be manufactured in the table so that it always must be set to zero. Would that change anything in the solution above?

Answer 1

Let me recast your table as $$\begin{array}{l|ccc|c}&\text{A}&\text{B}&\text{C}&\text{Total}\\\hline \text{Machine 1} & x_{1a} & x_{1b} & x_{1c} & 8\\ \text{Machine 2} & x_{2a} & x_{2b} & x_{2c} & 15\\ \text{Machine 3} & x_{3a} & x_{3b} & x_{3c} & 9\\ \text{Machine 4} & x_{4a} & x_{4b} & x_{4c} & 13\\\hline \text{Total} & 10 & 15 & 20 & T_{all}\end{array}$$

where I have arbitrarily subtracted $1$ from the Machine 2 total so that a solution is actually possible (if you communicate a different correction, I'll update this).

We have 7 equations: $$x_{1a} + x_{1b} + x_{1c} = 8\tag 1$$ $$x_{2a} + x_{2b} + x_{2c} = 15\tag 2$$ $$x_{3a} + x_{3b} + x_{3c} = 9\tag 3$$ $$x_{4a} + x_{4b} + x_{4c} = 13\tag 4$$ $$x_{1a} + x_{2a} + x_{3a} + x_{4a}= 10\tag 5$$ $$x_{1b} + x_{2b} + x_{3b} + x_{4b}= 15\tag 6$$ $$x_{1c} + x_{2c} + x_{3c} + x_{4c}= 20\tag 7$$

But they are not all independent. If we sum equations $(1)-(4)$, we get that the sum of all the $x_{ij}$ must be $45$. If we then subtract off $(5)$ and $(6)$ the result is exactly equation $(7)$. That is, any solution for the first six equations automatically is a solution for the seventh. Thus the seventh equation adds no new information, so we can ignore it.

We can use each of the equations to express one of the variables in terms of the rest. Solve for the Attribute $C$ and Machine 4 variables : $$x_{1c} = 8 - x_{1a} - x_{1b}\tag{1a}$$ $$x_{2c} = 15 - x_{2a} - x_{2b}\tag{2a}$$ $$x_{3c} = 9 - x_{3a} - x_{3b}\tag{3a}$$ $$x_{4c} = 13 - x_{4a} - x_{4b}\tag{4a}$$ $$x_{4a}= 10 - x_{1a} - x_{2a} - x_{3a}\tag{5a}$$ $$x_{4b}= 15 - x_{1b} - x_{2b} - x_{3b}\tag{6a}$$

We can substitute from $(5a)$ and $(6a)$ back into $(4a)$: $$x_{4c} = 13 - (10 - x_{1a} - x_{2a} - x_{3a}) - (15 - x_{1b} - x_{2b} - x_{3b})$$ $$x_{4c} = x_{1a} + x_{2a} + x_{3a} + x_{1b} + x_{2b} + x_{3b} - 12\tag{4b}$$

So we can pick any value for each of $x_{1a}, x_{2a},x_{3a},x_{1b},x_{2b},x_{3b}$ and then use the formulas above to find values for the other six variables that will produce a solution.

Now we have constraints on the values we are allowed to pick: all twelve variables must be $\ge 0$: $$x_{1a} \ge 0, \quad x_{2a} \ge 0, \quad x_{3a}\ge 0, \quad x_{1b} \ge 0, \quad x_{2b} \ge 0, \quad x_{3b}\ge 0\tag8$$ $$x_{1a} + x_{1b} \le 8\tag 9$$ $$x_{2a} + x_{2b} \le 15\tag{10}$$ $$x_{3a} + x_{3b} \le 9\tag{11}$$ $$x_{1a} + x_{2a} + x_{3a} \le 10\tag{12}$$ $$x_{1b} + x_{2b} + x_{3b} \le 15\tag{13}$$ $$x_{1a} + x_{2a} + x_{3a} + x_{1b} + x_{2b} + x_{3b} \ge 12\tag{14}$$

Now things can get complicated. As long are your systems are relatively simple, it might be easiest just to count them by brute force:

count = 0
for x1a = 0 to 8 
for x1b = 0 to 8 - x1a
for x2a = 0 to 15
for x2b = 0 to 15 - x2a
for x3a = 0 to 9
for x3b = 0 to 9 - x3a
   if  x1a + x2a + x3a <= 10
      and x1b + x2b + x3b <= 15
      and x1a + x2a + x3a + x1b + x2b + x3b >= 12
   then
      count = count + 1

Answer 2

$ \def\l{\ell} \def\o{{\tt1}} $The components of the single-entry matrix $E_{ij}\in{\mathbb R}^{n\times m}\,$ are all zero, except for a $\o$ as the $(i,j)$ element. Using four such matrices, one can build a parametric matrix $$G(i,j,k,\l) = E_{ij} + E_{k\l} - E_{i\l} - E_{kj} \qquad (1\le i,k\le n,\quad 1\le j,\l\le m)$$ For example, for $\,(n,m)=(4,3)$ $$G(1,1,4,3) = \pmatrix{ +1 & \;\;0 & -1 \\ \;\;0 & \;\;0 & \;\;0 \\ \;\;0 & \;\;0 & \;\;0 \\ -1 & \;\;0 & +1 \\ }$$ The interesting thing about such a matrix is that both its rows and columns sum to zero.

Therefore, given any contingency table $M$ which satisfies the marginal totals, we know that $$M+\alpha G(i,j,k,\l)$$ has the same marginal totals.

Not only that, but you can transform a non-integer solution into an integer solution by using a sequence of parametric matrices with fractional $\alpha$-values to clear the fractions element-by-element.

Let $x$ and $x$ be vectors containing the row and column sums respectively. A simple non-integer solution to the problem is given by $$M = \frac{xy^T}{\sum_k x_k} = \frac 19\pmatrix{ 16 & 24 & 32 \\ 30 & 45 & 60 \\ 18 & 27 & 36 \\ 26 & 39 & 52 \\} = \pmatrix{ 1.778 & 2.667 & 3.556 \\ 3.333 & 5.000 & 6.667 \\ 2.000 & 3.000 & 4.000 \\ 2.889 & 4.333 & 5.778 \\ } $$ A sequence of $\,(\alpha G)\,$ matrices will clear the fractions, leaving an integer solution such as $$N = \pmatrix{ 2 & 2 & 4 \\ 3 & 6 & 6 \\ 2 & 3 & 4 \\ 3 & 4 & 6 \\ } $$ It is straightforward to verify that $$N+3\,G(1,1,4,3) = \pmatrix{ 5 & 2 & 1 \\ 3 & 6 & 6 \\ 2 & 3 & 4 \\ 0 & 4 & 9 \\ } $$ is also a solution.

Therefore, all possible solutions can be represented by $$N+\alpha G(i,j,k,\l)$$ and restricting $\alpha$ to be an integer will yield the integer solutions.