求解一组合计数问题

javee30

假设一长为L的随机二进制数，其中‘1’的个数为n（n<L），求解包含连续k(k<n)个连续‘1’的二进制数个数

fungarwai

a(L,n,k)=(0...)+(1...)
(0...)=a(L-1,n,k)
(1...)=(10...)+(11...)
这样分下去的话应该会得到\(\displaystyle a(L,n,k)=C_{L-k}^{n-k}+\sum_{m=1}^k a(L-m,n-m+1,k) \)
嗯...怎么解呢...

sheng_jianguo

假设一长为L的随机二进制数，其中‘1’的个数为n（n<L），求解包含连续k(k<n)个连续‘1’的二进制数个数。
解：设满足要求二进制数中，“1”被“0”分成m段，则
m≤L-n+1（因一共有L-n个“0”）
m≤n-k+1（因其中有一段至少有k个“1”，其它段至少有1个“1”，一共只有n个“1”）
令r=min(L-n+1, n-k+1) （即r为L-n+1与n-k+1中小者）
按线性方程的非负整数解个数公式可以推导出：“1”分成m段（和次序有关）共有\(m C_{n-k}^{n-k+1-m}\)种；每种段间加入不同“0”的种数共有\(C_{L-n+1}^{L-n+1-m}\)种。
所以，“1”被“0”分成m（≤r）段，共有\(mC_{n-k}^{n-k+1-m}\) \(C_{L-n+1}^{L-n+1-m}\)种，再将公式从m=1加到m=r，就是所求二进制数个数:\(\displaystyle \sum_{m=1}^r(mC_{n-k}^{n-k+1-m}\) \(C_{L-n+1}^{L-n+1-m} )\)。

fungarwai

sheng_jianguo 发表于 2014-12-31 12:04
假设一长为L的随机二进制数，其中‘1’的个数为n（n

考虑"1"的时候还有些问题
L=7;n=4;k=2;r=min(L-n+1,n-k+1);
for m=1:r
        a(m)=m*nchoosek(n-k,n-k+1-m);
        b(m)=nchoosek(L-n+1,L-n+1-m);
        s(m)=m*nchoosek(n-k,n-k+1-m)*nchoosek(L-n+1,L-n+1-m);
end
sum(s)

$4=1\times 4$
1 1 1 1 0 0 0
0 1 1 1 1 0 0
0 0 1 1 1 1 0  
0 0 0 1 1 1 1

$24=4\times 6 \ne 3\times 6 =18$
1 1 1 0 1 0 0
1 1 0 1 1 0 0
1 0 1 1 1 0 0
1 1 1 0 0 1 0
0 1 1 1 0 1 0
1 1 0 0 1 1 0
0 1 1 0 1 1 0
1 0 0 1 1 1 0
0 1 0 1 1 1 0
1 1 1 0 0 0 1
0 1 1 1 0 0 1
0 0 1 1 1 0 1
1 1 0 0 0 1 1
0 1 1 0 0 1 1
0 0 1 1 0 1 1
1 0 0 0 1 1 1
0 1 0 0 1 1 1
0 0 1 0 1 1 1

$12=3\times 4$
1 0 0 1 0 1 1
0 1 0 1 0 1 1
1 1 0 1 0 1 0
1 0 1 1 0 1 0
1 0 1 0 1 1 0
1 1 0 1 0 0 1
1 0 1 1 0 0 1
1 1 0 0 1 0 1
0 1 1 0 1 0 1
1 0 0 1 1 0 1
0 1 0 1 1 0 1
1 0 1 0 0 1 1

fungarwai

每段"1"的个数为正整数，且至少有1段多于k-1个，即排除所有段的"1"都小于等于k-1个的情况
\(\displaystyle \sum_{t=1}^m (-1)^{t-1} C_m^t C_{n-(k-1)t-1}^{m-1} \)
乘进去是\(\displaystyle \sum_{m=1}^r \sum_{t=1}^m (-1)^{t-1} C_m^t C_{n-(k-1)t-1}^{m-1} C_{L-n+1}^m \)

clc;clear;
L=7;n=4;k=2;r=min(L-n+1,n-k+1);
for m=1:r
        a(m)=0;
        for t=1:m
                if(n-(k-1)*t<m)break;end
                a(m)=a(m)+(-1)^(t-1)*nchoosek(m,t)*nchoosek(n-(k-1)*t-1,m-1);
        end
        b(m)=nchoosek(L-n+1,m);
        s(m)=a(m)*b(m);
end
sum(s)

javee30

L=8,n=6,k=3按楼上公式算出来为0,实际是27

fungarwai

javee30 发表于 2014-12-31 16:59
L=8,n=6,k=3按楼上公式算出来为0,实际是27

我算不出楼上有这个值

javee30

可能是∑的范围搞错了，谢谢

javee30

我是用递归函数计算的，计算速度太慢了

fungarwai

我用母函數方法重新做咗
發現等於$\sum_{m=1}^{L-n+1}(-1)^{m-1}C_{L-n+1}^m C_{L-km}^{L-n}$

Permutation of consecutive items
https://artofproblemsolving.com/ ... f_a_linear_equation