0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The sum of the totals for each Machine is 46, not 45. Because of this, no solution is possible. Did you copy one of the machine totals wrong? $\endgroup$ – Paul Sinclair Aug 17 at 15:04
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.