permutation/combination with specific condition

Question

Let us we have binary number to fill out 9 spots with specific condition: 0 always comes before 1. the possible conditions is 10:

1 1 1 1 1 1 1 1 1

0 1 1 1 1 1 1 1 1

0 0 1 1 1 1 1 1 1

0 0 0 1 1 1 1 1 1

0 0 0 0 1 1 1 1 1

0 0 0 0 0 1 1 1 1

0 0 0 0 0 0 1 1 1

0 0 0 0 0 0 0 1 1

0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0

Now lest us extent it to 0, 1, 2 with same rule. 0 should be always before 1 and/or 2. 1 should be before 1. Again, 9 spots are available to fill out. I know that this yields to 55 combinations.

Question:

(1) what is the mathematical formulation to generalize this?

(2) How can I store all those 55 combinations? [any matlab code?]

Thanks

Answer 1

As the commenter said, the answer comes down to stars and bars. You can also think of this as counting the number of non-decreasing sequences i_1 <= i_2 <= ... <= i_k, where k is the number of symbols available and each i_j is a number between 0 and 9.

That said, here's a matlab script that generates all possibilities. Each row of the output matrix is one possible string of digits.

function M = bin_combs(L,k)
% L: length
% k: number of symbols

if k == 1
    M = zeros(1,L);
else
    M = zeros(0,L);
    N = bin_combs(L,k-1);
    for i = 1:size(N,1)
        row = N(i,:);
        for j=find(row==k-2)
            new_row = row;
            new_row(j:end) = new_row(j:end) + 1;
            M = [M;new_row];
        end
        M = [M;row];
    end
end

Some sample output:

>> size(bin_combs(9,3))

ans =

    55     9

>> size(bin_combs(9,4))

ans =

   220     9