# String counting questions

• February 25th 2010, 10:17 AM
Runty
String counting questions
There are two parts to this one. They are listed word for word.

1. How many 12 lowercase letter strings are there that contain at least 2 vowels (a vowel is one of {a,e,i,o,u})?
2. How many bit strings
1. of length 12 contain 8 consecutive zeros?
2. are there of length at least 5 and at most 10?
• February 26th 2010, 06:06 AM
Hello Runty
Quote:

Originally Posted by Runty
There are two parts to this one. They are listed word for word.

1. How many 12 lowercase letter strings are there that contain at least 2 vowels (a vowel is one of {a,e,i,o,u})?
2. How many bit strings
1. of length 12 contain 8 consecutive zeros?
2. are there of length at least 5 and at most 10?

1. Assuming that repetition is allowed, there are $26^{12}$ strings altogether. Of these, there are $21^{12}$ that contain no vowels.

To construct a string containing exactly one vowel:
there are $12$ positions in which the vowel might be placed;

there are $5$ choices of vowel;

there are then $21^{11}$ choices of consonant for the remaining $11$ places.
Total: $12\times5\times21^{11}$

So the number of $12$ letter strings that contain $2$ or more vowels is:
$26^{12}-21^{12} - 12\times5\times21^{11}$
which is quite a lot!

2a. I am assuming this means exactly $8$ consecutive zeros. So consider the 'block' containing these $8$ zeros. This is to be positioned along with $4$ other bits.

If the block is at one end of the bits:
there are two choices of end;

the bit immediately adjacent to the block must be a $1$;

there are then $2^3 = 8$ choices of the remaining 3 bits.
Total: $2\times8 = 16$

If the block of $8$ zeros is not at one end:
there are $2$ choices of position for the block;

the bit on either side of the block must be a $1$;

there are then $2^2=4$ choices for the remaining two bits.
Total: $2\times 4 = 8$

So the overall total is $16+8 = 24$.

2b. There are $2^n$ bit strings of length $n$. So there are:
$\sum_{n=5}^{10}2^n$
bits strings of length $5$ to $10$ inclusive.

I reckon that adds up to $2016$.