已知Sn={A|A=(a1,a2,a3,...,an),ai=0或1,i=1,2,...,n}(n≥2),对于U,V∈Sn,d(U,V)表示U和V中相对应的元素不同的个数．给定U=(a1,a2,a3,...,an),若V∈Sn,则所有的d(U,V)之和为?

Question

已知Sn={A|A=(a1,a2,a3,...,an),ai=0或1,i=1,2,...,n}(n≥2),对于U,V∈Sn,d(U,V)表示U和V中相对应的元素不同的个数．
给定U=(a1,a2,a3,...,an),若V∈Sn,则所有的d(U,V)之和为?

Answer 1

d(U,V)这里指的其实是对应两个向量U和V的距离.或者更准确的说这里的d(U,V)定义出了一个度量空间.不管这个.考虑每一个数位ai,在U中它有一个给定的值,那么在Sn中有多少种情况呢,又能有多少被累计呢?Sn的序,也就是Sn集合的元素个数,不难发现是2^n个.而显然,对于任意给定的一个数位,应该会有一半是和U的这一位不同,一半相同.那么可以被累计的次数就是2^n-1,而这样的数位总共有n位.所以答案是n*(2^n-1)