If a vector has $d$ zeroone-entries, and $d\leq n/2$, then delete as many ones as you can,
(and further zeros if necessary).
Conversely Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can,
(and further ones if necessary).
Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ zeroesones. The number of such vectors with exactly $n/6$ zerosones in $2n/3$ positions is $\binom{2n/3}{n/6}$. For the final sum, one needs to sum over bimomial coefficients $2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ and such a sum can be approximated: Note that the largest entry, with $d=n/6$ gives by far the greatest contribution. The binomial coefficient in this region can be approximated by $\binom{k}{l}=2^{k H(l/k)+o(k)}$, where $H$ denotes the entropy function $H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, (for $x\in [0,1]$, and $\log $ is the natural logarithm).
IfEdit: In view of Yuri's comment, I am not mistakencorrect this: (Thank you, thenYuri!)
As $H(1/4)$ is about $0.811$
,
givingthis is about $2^{n/6 \times 0.811...+o(1)}=2^{0.1352\ldots n}$, which$2^{2n/3 \times 0.811...+o(1)}=2^{0.54\ldots n}$.
This upper bound is considerably smallercertainly weaker than the bound $2^{n/3}$, but uses a quite different method. It would be interesting to see, whether the "optimum" uses a deterministic construction, or a random construction (like Shannon's bounds in coding theory), or a combination of methods.
Some backgroundexplanation why this worksthe method above gives some saving over the trivial $2^{2n/3}$: most of the original vectors have about $n/2+ O(\sqrt{n})$ zero and one entries. Going Going away from this symmetric centre reduces (by the binomial distribution) the number of possibilities drastically. In other words the tail of this distibution is small.