1
$\begingroup$

This must be basic, but my Mathematica (and overall programming) skill level is too low to find a handy solution:

I need to generate all possible lists of $m$ integers (I call these integers $x_i$'s, where $i=1, \dots, m$, with $0 \leq m \leq X$) such that $$\sum_{i=1}^m x_i = X.$$

For each list generated, I then need to count how many of the $x_i$'s are $0$'s, $1$'s, etc., up to $X$.

I can tell that these $m$ integers will be arranged in the following possible configurations:

$$ \frac{(m+X-1)!}{(m-1)! \ X!}.$$

Also, that for a given $x_i$, there will be the following number of possible configurations: $$\frac{(N+W-x_i-2)!}{(N-2)! (W-x_i)!}.$$

Say, $m=3$ and $X=3$. Then the possible configurations are $$\{3, 0, 0\},$$ $$\{2, 1, 0\},$$ $$\{2, 0, 1\},$$ $$\{1,2,0\},$$ $$\{1,0,2\},$$ $$\{1,1,1\},$$ $$\{0,3,0\},$$ $$\{0,2,1\},$$ $$\{0,1,2\},$$ $$\{0,0,3\}.$$

So, here, there is one 3 and two 0's in the first list, etc.

Now, I need Mathematica to help me generate these lists (10 in my example), but for arbitrary (though not very large) values of $m$ and $X$.

Again, my next step is to make Mathematica take each list in turn and count the $x_i$'s that are zeroes, ones, etc. up to $X$. But that I think I can try and figure out myself.

I did look up similar questions in the archive but couldn't find a pointer to the solution.

$\endgroup$
4
$\begingroup$

You can use IntegerPartitions and Permutations for this:

partitions[m_, X_] := Catenate[
    Permutations /@ IntegerPartitions[X, {m}, Range[0,X]]
]

For your example:

partitions[3, 3]

{{3, 0, 0}, {0, 3, 0}, {0, 0, 3}, {2, 1, 0}, {2, 0, 1}, {1, 2, 0}, {1, 0, 2}, {0, 2, 1}, {0, 1, 2}, {1, 1, 1}}

$\endgroup$
0
$\begingroup$

You can simply Select from the generated set of Tuples:

x = 3; m = 3;
lists = Select[Tuples[Range[0, m], m], Total@# == x &];

This will give you your lists:

lists // Grid

0   0   3
0   1   2
0   2   1
0   3   0
1   0   2
1   1   1
1   2   0
2   0   1
2   1   0
3   0   0

To count the occurrences of the digits, just use Tally:

Tally /@ lists // Grid

{0,2}   {3,1}   
{0,1}   {1,1}   {2,1}
{0,1}   {2,1}   {1,1}
{0,2}   {3,1}   
{1,1}   {0,1}   {2,1}
{1,3}       
{1,1}   {2,1}   {0,1}
{2,1}   {0,1}   {1,1}
{2,1}   {1,1}   {0,1}
{3,1}   {0,2}   

The first line means: "0 occurs 2 times and 3 occurs once". The next line has three different digits...

For longer lists or different Totals, just change x or m in the first line.

$\endgroup$
0
$\begingroup$

A bit slow but this might work:

soln1[m_, X_] := 
Module[{}, n = (m + X - 1)!/(m - 1)!/X!; 
FindInstance[
Sum[x[i], {i, 1, m}] == X && And @@ Thread[Array[x, m] >= 0], 
Array[x, m], Integers, n]]

Array[x, 3] /. soln1[3, 3]

(* {{0, 0, 3}, {0, 1, 2}, {0, 2, 1}, {0, 3, 0}, {1, 0, 2}, {1, 1, 1}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}, {3, 0, 0}} *)

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