# Permuting and finding combinations of bit strings

I am working on typical computer science math and one theme in many text books is to find different permutations/combinations of binary strings:

1011011101 is an example op a binary number of length 10. How many binary numbers of length 10 end up with 111 and contain exactly two zeros.

The example above is a typical question and the question is often harder than the maths/math:

*The solution above is : The number is completely defined if we know the places of the 2 zeros. The number starts with 1 and ends up with 111. There are still six digits to be determined. Once we identify two locations for the zeros, the number is fixed. The number of ways to choose 2 places out of the 6, is $\bf\binom{6}{2}$.

I got $\binom{7}{2}$.

for example what about the sting 1111111100, which does not have a 1 in th efirst place?.

I sort of almost get it then slip up one one of the assumptions: do you have any way of solving these binary string questions eg by drawing them out so you don't slip up tha will help me from slipping up?

• I don't regard this question as typical, and you don't explain why you got $\binom{7}{2}$. Please try to broaden the question. – frafl May 30 '13 at 20:18
• The questioner probably intended that strings such as $01111$ not be allowed, i.e. that the language of "binary numbers" consists of $\{0,1.{*}\}$. – András Salamon May 31 '13 at 11:03
• Typical: I got it from a departmental end of term questions sheet on counting,probably first year and have seen a lot of these questions before. I don't get why a binary number starts with 1? What about zero? I am wondering if it is maybe I am confusing internal representation of binary with just binary?In IEE floating point standard zero is represented as 52 zeros in the mantissa? If this is the case my raeding of the question is the problem. – pythonMan May 31 '13 at 11:31
• I visualised the number as 1110000000 so there are seven other places : I did not get why the first digit must be a 1 eg 1110000001? As this excludes the number 1110000000? I am new to this , working in isolation so no other place to bounce ideas off. – pythonMan May 31 '13 at 13:00

I think the trick is that the question specifies a binary number, rather than a string, so the normal assumption would be that a number has no leading zeroes (in this case a $10$ digit binary number must start with a $1$).

Of course a binary string is just a sequence of characters from $\{0,1\}$, so $01$ is clearly a different string to $1$, whereas we would consider them the same number.

There is an argument here about numbers vs. their representations, so we could consider that $01$ and $1$ are both representations of the same number, much as $2$ base ten is the same number as $10$ base two, it's just that we have some rules of usage that we often forget we are using when we discard leading zeroes and identify a number with its representation.

So given that it starts with a $1$, and the last three digits are $111$, there's only six spots left that could be a $0$.

• Is zero not a number in binary? Surely 0000000000 is a number as the question does not specify which set of numbers it represents eg naural numbers etc? Also would assuming it starts with 1 mean there is only 1 choice for place 1 but what about 1001 and 1000 whch shows it has two possibilitie? You r answewr makes sense but I am still not convinced? – pythonMan May 30 '13 at 8:07
• $0000\ldots$ is a number, but by convention we reduce it to its "smallest" represention of $0$ by removing the leading zeroes, so we would not normally consider, say $000$ as a binary number of length 3, it would become a binary number of length 1, namely $0$. So if you want to get ten bits (or anything greater than one bit) in the number, you need a $1$ at the start. With $1001$ and $1000$, there is still only one choice for the first bit, which is $1$ (just to be clear, by first I mean the leftmost, most significant, leading bit). – Luke Mathieson May 30 '13 at 10:31
• +1 You provide a perfectly reasonable and almost certainly correct explanation for why the string representing a binary number of length $n$ must begin with a $1$: if it didn't, it would be a string representing a binary number of length less than $n$. – Patrick87 May 30 '13 at 23:53
• I notice from your profile you ar epost doc so I am apt to accept and the comment below your agrees so I should be happy, I am happy you answered, however it is bugging me still probably my lack of understanding. It is by "by convention" bit because I have read many discrete math books and missed that one,. I sthere any kind of proof to put his to bed that you know of that abinary number must begin with 1?Apolgies for being pedantic but my brain won't let me settle this one! – pythonMan May 31 '13 at 11:20
• @pythonMan, never accept something simply because someone holds a position of "authority" (not that a postdoc is much of an authority on anything anyway!). There's no proof of this, as it's just a convention - an agreed way of doing things, not a mathematical truth. For example in decimal we wouldn't normally write 023 when we wanted to write twenty three, we'd write the shortest representation in the number system we're using and write 23, so the "default" assumption is that unless the number is zero, the leading digit isn't 0. So when they write number in the question, they're likely... – Luke Mathieson May 31 '13 at 12:50