How many strings of six lowercase letters contain the letters a and b in consecutive positions with a preceding b, with all letters distinct?
Can someone give me a general method for thinking about this problem?
Thank you.
[Math] How many strings of six lowercase letters contain the letters a and b in consecutive positions…
combinatoricsintuition
Related Solutions
In my experience, if it is difficult to calculate a probability, it is sometimes easier to calculate the inverse.
So how many 10 digit strings do not contain consecutive 0s?
We can ignore the first digit since one digit in of itself will have no impact on the probability.
From there, the probability that a single digit does not cause that string to contain consecutive 0s is inverse of the the probability that both the previous and the current digits are 0.
So if we were solving for 2 digit strings, the probability would simply be the inverse of the probability of having 0 digit followed by another 0 digit, or $1 - (\frac{1}{10\times10})$.
If we were to then apply this to a 3 digit string, the probability would be compounded with the inverse of the probability of the last digits having 0. This simply means to find the probability of not finding 0s in the first two digits and not finding 0s in the second two digits. This also covers the case of both finding digits in the first 2 digits as well as finding digits in the last 2 digits.
The probability of the first two digits not both having 0 is $1 - (\frac{1}{10\times10})$, and the probability of the last two digits not both having 0 is $1 - (\frac{1}{10\times10})$. Compounded, you would get $$1 - \frac{1}{\frac{1}{1 - (\frac{1}{10\times10})}\times\frac{1}{1 - (\frac{1}{10\times10})}}$$ Simplying a bit, we get: $$1 - (1 -\frac{1}{10\times10})^{2}$$
Why the 2? Because we have 3 digits and 2 pairs of digits to consider. Generalizing, we would have: $$1 - (1 - \frac{1}{10\times10})^{n-1}$$ Where $n$ is the number of digits. Take this probability and multiply times $10^n$ or in this case $10^{10}$ (total number of possible combinations) and you get the number of digits containing consecutive zeros.
It would seem that you're making the mistake of assuming the pattern is linear. When you're finding all configurations of non-0 digits in the case in which m is 1, there should be just as many configurations of 0 digits in the case in which m is 9. So: $$xxxxxxxxx0,0xxxxxxxxx$$
If your linear calculation were accurate, then there should be 10000000000 ways to place that singular 0 digit! Hope that helps!
Let $W(c,n)$ denote the number of words of length $c$ from an alphabet of $n$ letters. Then $W(c,n)=n^c$.
Out of these, the number of words of the same size that do not contain one of the letters is $W(c,n-1)=(n-1)^c$. The number of ways of choosing which letter is missing is $\binom{n}{1}$.
The number of words of the same size that do not contain two letters is $W(c,n-2)=(n-2)^c$. The number of ways of choosing which two letters are missing is $\binom{n}{2}$... and so on ...
Now we use inclusion-exclusion principle: (subtract the number of words missing one of the letters, then add the number missing two of the letters, subtract the number missing three of the letters,...)
We get:
$$W(c,n)-\binom{n}{1}W(c,n-1)+\binom{n}{2}W(c,n-2)-\binom{n}{3}W(c,n-3)+\cdots+(-1)^{n-1}\binom{n}{n-1}W(c,n-(n-1)).$$
This is
$$n^c-\binom{n}{1}(n-1)^c+\binom{n}{2}(n-2)^c-\binom{n}{3}(n-3)^c+\cdots+(-1)^{n-1}\binom{n}{n-1}1^c.$$
or
$$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}(n-k)^c.$$
Another way could be: Denote $S_c^n$ the number of ways to partition the word of length $c$ into $n$ pieces. Then we just need to choose which letter goes to each of the $n$ pieces. This number is $n!$. So the number of words we are looking for is
$$n!S_c^n.$$
The numbers $S_c^n$ are called Stirling's numbers of the second kind.
Best Answer
Think about the following different cases:
ab[][][][]
[]ab[][][]
[][]ab[][]
[][][]ab[]
[][][][]ab
How many possibilities are there for case 1?
Can you see why there are the same number of possibilities for each of the five cases?
If so, take the number of possibilities for case 1 and multiply by 5.