{0,1}上的序列数,使得序列至少包含一半

Question

如何计算{0,1}上的序列数,使每个序列至少包含一半？

Answer 1

长度为n的序列总数为2 ^ n.如果n是奇数,那么它们的一半(2 ^(n-1))至少有一半.对于偶数n,你必须考虑到n!/((n/2)!^ 2)序列恰好有一半.所以在这种情况下,我认为你总共有(1/2)*(2 ^ n + n!/((n/2)!^ 2)).