permutation/combination 具有特定条件

Question

让我们有二进制数来填写9个具有特定条件的点：0总是在1之前。可能的条件是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

现在让我们用相同的规则将它扩展到 0、1、2。 0 应该总是在 1 and/or 2 之前。1 应该在 1 之前。同样，有 9 个位置可供填写。我知道这会产生 55 种组合。

问题：

(1) 概括这个的数学公式是什么？

(2) 如何存储所有这 55 种组合？ [任何 matlab 代码？]

谢谢

Answer 1

正如评论者所说，答案归结为星星和酒吧。您也可以将此视为计算 non-decreasing 序列的数量 i_1 <= i_2 <= ... <= i_k，其中 k 是可用符号的数量每个 i_j 都是 0 到 9 之间的数字。

也就是说，这是一个生成所有可能性的 matlab 脚本。输出矩阵的每一行都是一个可能的数字串。

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

一些示例输出：

>> size(bin_combs(9,3))

ans =

    55     9

>> size(bin_combs(9,4))

ans =

   220     9

permutation/combination 具有特定条件

permutation/combination with specific condition

matlab

combinations

permutation

matrix