Generation of restricted increasing integer sequences
Since we can map such sequence
$$0\leq a_1\leq a_2\leq a_3 \leq \cdots \leq a_{n-1}\leq a_n < m $$
to
$$0 < b1=a_1+1 < b2=a_2+2 < b3=a_3+3 <\cdots < b_n=a_n+n < m+n $$
and
$\{b_1,b_2,\cdots b_n\}$ is the n
subsets of Range[m+n-1]
And we can get $\{a_1,a_2,\cdots a_n\}$ from $\{b_1,b_2,\cdots b_n\}-\{1,2,\cdots,n\}$
m = 8;
n = 5;
list = Subsets[Range[m+n-1], {n}]
Subtract[#, Range[n]] & /@ list
With a small trick, we can do this using the Table
function. This is necessary because Table
has the attribute HoldAll.
For a small example, we first set m and n:
m=4;
n=2;
We then create a list of variables and a list of iterators and join them into the body of Table
:
var = Table[x[i], {i, n}];
iter = Table[{x[i], x[i - 1] + 1, m-1}, {i, n}] /. x[0] -> -1;
body = PrependTo[iter, var]
Finally we apply Table
to the body and Flatten to get ride of superfluous braces:
Flatten[Table @@ body, 1]
This gives:
{{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}}