n为偶数,an表示长为n且含偶数个0,偶数个1的二进制序列的个数,求an.

Question

n为偶数,an表示长为n且含偶数个0 ,偶数个1 的二进制序列的个数,求an.

Answer 1

这里有点会让我感觉歧义,这个长为n的二进制序列是数呢还是序列：
比如n=2,这时00算不算一个满足的二进制序列?
如果这个算得话,我想这个就很容易了.
这等于在n个位置中选出偶数个位置放入0,偶数个位置放入1.
由于n是偶数,因此放了偶数个0必定有偶数个1.所以从n中取出0,2,4...n个位置放入0.
总数为:
an=sum(C(n,2i))=2^(n-1)
如果不算(那就是说那是数),要求第一个数字必须是1.这个时候就稍微麻烦一点点.
我在这写一种证法.
我们把条件放宽:n可以是奇数,bn表示的是长度为n的0,1序列(不是数)中,含有偶数个0的序列个数.
显然题目的an与这个放宽了的bn相去甚远.放宽后bn=2^(n-1).就是前面的结果,我们要从中把第一个数为0的序列全部剔除.这样剩下的就是题目所要的结果an了.
考虑前2位为00的序列有:bn-2个,前3位为010的序列有bn-3个.前4位为0110的序列有bn-4...前n-1位为01...10的有b1个,当然前n位为0111...10的,就它本身1个.
于是首位为0,含有偶数个0的序列数为:
b(n-2)+...+b1+1=2^(n-2)
因此满足的应该是:
an=bn-2^(n-2)=2^(n-2)
有人说首位为1的和首位为0的序列数应该是一样的,然后直接除2便得结果了.我只想说如果是这样,抱这种想法的人本身就没理解题目.