# How do I generate a set of n-tuples containing integral solutions to a linear equation provided certain constraints?

Let $m,k,p$ be fixed positive integers. I want to create a table of k-tuples $(x_1,x_2,\ldots,x_k)$ comprised of solutions in positive integers to the equation below:

$$x_1+x_2+\cdots+x_k=m\quad\text{where }1\leq{}x_1,x_2,\ldots,x_k\leq{}p$$

For example, if I set $m=16,k=3$, and $p=6$. How can I make mathematica generate the set (table) of integer triples $(x_1,x_2,x_3)$ such that $$x_1+x_2+x_3=16$$ where $1\leq{}x_1,x_2,x_3\leq{}6$.

Also, how would I seperately generate a table of positive integral triples $(x_1,x_2,x_3)$ for which $$x_1+x_2+x_3\geq{}16 \quad \text{and } 1\leq{}x_1,x_2,x_3\leq{}6.$$

-

Try to read Documentation on functions Solve and Reduce and tutorial Solving Equations. Look through this forum, I bet this is a duplicate question. There is also a guide: Diophantine Equations.

{x1, x2, x3} /.
Solve[x1 + x2 + x3 == 16 && 1 <= x1 <= 6 && 1 <= x2 <= 6 &&
1 <= x3 <= 6, {x1, x2, x3}, Integers]


{{4, 6, 6}, {5, 5, 6}, {5, 6, 5}, {6, 4, 6}, {6, 5, 5}, {6, 6, 4}}

or alternatively

Reduce[x1 + x2 + x3 == 16 && 1 <= x1 <= 6 && 1 <= x2 <= 6 &&
1 <= x3 <= 6, {x1, x2, x3}, Integers]


(x1 == 4 && x2 == 6 && x3 == 6) || (x1 == 5 && x2 == 5 && x3 == 6) || (x1 == 5 && x2 == 6 && x3 == 5) || (x1 == 6 && x2 == 4 && x3 == 6) || (x1 == 6 && x2 == 5 && x3 == 5) || (x1 == 6 && x2 == 6 && x3 == 4)

{x1, x2, x3} /.
Solve[x1 + x2 + x3 >= 16 && 1 <= x1 <= 6 && 1 <= x2 <= 6 &&
1 <= x3 <= 6, {x1, x2, x3}, Integers]


{{4, 6, 6}, {5, 5, 6}, {5, 6, 5}, {5, 6, 6}, {6, 4, 6}, {6, 5, 5}, {6, 5, 6}, {6, 6, 4}, {6, 6, 5}, {6, 6, 6}}

-
Thanks for the code and references. – Black Milk Mar 31 '13 at 5:34
I don't know why but when I try to upvote your answer it gives me a -1 instead. – Black Milk Mar 31 '13 at 6:07
@EdwinMontufar Strange... you just have to click "upper" arrow for up-vote. Not sure if you experiencing a bug or clicking on a wrong thing. I hope I won't go negative 25K suddenly ;) – Vitaliy Kaurov Mar 31 '13 at 6:14
I'm definitely clicking that upper arrow =) – Black Milk Mar 31 '13 at 6:23
@EdwinMontufar you got it now, a +1 from you, thanks. I think that -1 is from someone else. – Vitaliy Kaurov Mar 31 '13 at 6:28

It seems to me that for your first stated problem there is a much better method than Solve or Reduce:

{m, k, p} = {16, 3, 6};
IntegerPartitions[m, {k}, Range@p]

{{6, 6, 4}, {6, 5, 5}}


If you want all permutations just use Permutations:

Join @@ Permutations /@ %

{{6, 6, 4}, {6, 4, 6}, {4, 6, 6}, {6, 5, 5}, {5, 6, 5}, {5, 5, 6}}


For your second stated problem I believe this will be more efficient than Solve or Reduce:

Join @@ Table[IntegerPartitions[x, {k}, Range@p], {x, m, k*p}]

{{6, 6, 4}, {6, 5, 5}, {6, 6, 5}, {6, 6, 6}}

-

Just for completeness, don't forget about one of @Artes' favourite functions: FrobeniusSolve. The Pick statements select solutions with positive integers less than or equal to p.

kTuples[m_Integer, k_Integer, p_Integer] :=
Block[{s = FrobeniusSolve[ConstantArray[1, k], m]},
s = Pick[s, UnitStep[Apply[Sequence, Table[p - s[[All, i]], {i, k}]]], 1];
Pick[s, Map[FreeQ[#, 0] &, s]]
]


For your second question generating solutions greater than or equal to m:

kTuples2[min_Integer, k_Integer, p_Integer] :=
Block[{s},
Flatten[Table[
s = FrobeniusSolve[ConstantArray[1, k], m];
s = Pick[s, UnitStep[Apply[Sequence, Table[p - s[[All, i]], {i, k}]]], 1];
Pick[s, Map[FreeQ[#, 0] &, s]],
{m, min, k*p}], 1]
]


The method becomes inefficient as m, k, and p increase because valid solutions must be selected from a possibly very large number of solutions returned by FrobeniusSolve.

-