NOTE: This is a homework question, so I only ask for hints and suggestions to nudge me in the correct direction.
Question:
Let $n \in \mathbb{N}$. How many binary strings of length 2n + 1 have more 1's than 0's? Use bijection to prove.
Progress so far:
We need a set of known size, B, along with a bijective function $f: A \rightarrow B$, where A is the set with binary strings of length $2n + 1$ and where each element in A has more 1's than 0's.
I tried to find a pattern by setting n = 1:
$$
\begin{align*}
000 \rightarrow &\lbrace empty set \rbrace \\
001 \rightarrow &\lbrace 1 \rbrace \\
010 \rightarrow &\lbrace 2 \rbrace \\
011 \rightarrow &\lbrace 1,2 \rbrace \\
100 \rightarrow &\lbrace 3 \rbrace \\
101 \rightarrow &\lbrace 1,3 \rbrace \\
110 \rightarrow &\lbrace 1,2 \rbrace \\
111 \rightarrow &\lbrace 1,2,3 \rbrace \\
\end{align*}
$$
I realized that binary strings with more 1's than 0's map to elements in B where the elements are of size $\geq 2n$.
Therefore the size of set $S$ where $S = \lbrace x : |x| \geq 2n\rbrace$ is the number of binary strings of length $2n+1$ with more 1's than 0's.
This is where I am stuck. I don't know how to fit bijection into this solution. Also I think my mapping from set A to set B is incorrect since set A it should only contain the binary strings that have more 1's than 0's.
Any help would be greatly appreciated.
Best Answer
Hint: First, note that since your string has odd length, every binary string has either more 1's or more 0's (no ties). Suppose that a string has more 0's than 1's... what happens when you flip all the bits? The new string has more 1's than 0's. So, for your bijection, consider pairing up a string with it's complement (i.e. the string with all the 1's and 0's flipped).
What you see by this bijection is that for every string with more 1's than 0's there is a corresponding string with more 0's than 1's.
Following your example, what you would pair up are the following:
$000 \to 111$
$001 \to 110$
$010 \to 101$
$100 \to 011$
That accounts for all 8 binary strings of length 3. Note that he LHS are the strings with fewer 1's than 0's and the RHS are the strings with more 1's than 0's.