Strings made from six $1$'s and six $0$'s

Question

I haven't thought about permutations and combinations in quite a while, and I came across an interesting problem that I am not sure how to approach.

Say you are given six $1$'s and six $0$'s. How many possible ways can you arrange those $1$'s and $0$'s into a string if the length of that string is from $1$ to $12$?

So, some valid arrangements are: ${{0}, {1}, {001}, {11000110}, {000000111111}}$

How would one approach solving this problem?

Thanks!

Answer 1

Rephrasing Phicar's approach into a direct combinatorial argument:

There are $\binom{14}{7}$ ways to create a string of length $14$ from seven $1$s and seven $0$s. For each string, consider the substring that appears immediately after the first $1$ that appears after the first $0$. For example, $101\mathbf{01010101010}$ or $00000001\mathbf{111111}$ or $11111101\mathbf{000000}$ (substring in bold). Any such substring consists of at most six $0$s and at most six $1$s. I claim this is [almost] a bijection.

• Given a string of $n$ $1$s and $m$ $0$s, we can construct the corresponding string of length $14$ by pre-pending it with $\underbrace{1\cdots 1}_{7-n-1} \underbrace{0 \cdots 0}_{7-m} 1$. This establishes the inverse mapping. (Note that the string $1111110000001$ maps to the empty string.)
• The map is not defined for the string $11111110000000$ since no $1$ appears after a zero.

The degenerate case and the empty string are thrown away, leaving $\binom{14}{7} - 2$.

---

I think Phicar's approach is the simplest, provided you know the hockey stick identity. The final answer looked too tidy not to have a direct combinatorial argument, but in the end my combinatorial argument ended up being the combinatorial proof of the hockey stick identity applied twice, which is more cumbersome to explain than I thought.

Answer 2

So, fix the number of $1's$ and the number of $0'$s (if you fix them to be $n$ and $m,$ the number of sequences is $\binom{n+m}{n}$ because you just have to know where to put the 1's) and iterate over them $$\sum _{n=0}^{6}\sum _{m=0}^6\binom{n+m}{n}=\sum _{n=0}^6\binom{n+7}{n+1}=\sum _{n=0}^6\binom{n+7}{6}=\binom{14}{7}-1.$$ here we use twice the well known HockeyStick identity. Notice that actually you do not want $n=0$ and $m=0$ so the answer is $\binom{14}{7}-2=3430.$