3
$\begingroup$

I'm working on what I think is a very simple problem, but I think I'm approaching it incorrectly.

Background: String length = 8, consists of X, Y, Z (must have one and only one occurrence each) and the digits 0 through 9 (can have any number of occurrences each).


I think I have the right idea for the first part? It asks for the total possibilities. So I made a table with each digit and the possible positions of that digit: \begin{array}{|c|c|} \hline Digit&Possible\ Positions \\ \hline X& 8 \\ \hline Y& 7 \\ \hline Z& 6 \\ \hline Numbers(10)& 5\\ \hline \end{array}

So then the possibilities are $8 * 7 * 6 * 5^{10} = 3,281,250,000$, right? Or do I have the wrong idea?


The second part I found a lot more difficult. It asked how many possibilities if no two letters can be consecutive.

The "X" has 8 possible positions. But after, that, the letters get harder: If my string is X _ _ _ _ _ _ _ , then there are 6 places where Y could go. But, if the string is _ X _ _ _ _ _ _, then there are only 5 places where Y could go.

\begin{array}{|c|c|} \hline Digit&Possible\ Positions \\ \hline X& 8 \\ \hline Y& *** \\ \hline Z& *** \\ \hline Numbers(10)& 5\\ \hline \end{array}

I'm just getting started with this, so simple/intuitive explanations are most welcome! :)

$\endgroup$

3 Answers 3

2
$\begingroup$

So, for the second part you will always have $5$ digits ($d_1$ to $d_5$) with $6$ interstices:

$$\_\,d_1\,\_\,d_2\,\_\,d_3\,\_\,d_4\,\_\,d_5\,\_$$

there will be $10$ possible digits for each of $d_1$ to $d_5$, so that's $10^5$ ways to replace $d_1$ to $d_5$.

Then if you place letters X,Y and Z in the interstices so that there is only one letter per space we fulfil the non-consecutive letter requirement.

There are $6$ spaces to place X, then $5$ spaces to place Y then $4$ spaces to place Z, so we get:

$$6\cdot 5\cdot 4\cdot 10^5\tag{Answer}$$

$\endgroup$
1
$\begingroup$

The number of ways to choose where the $X$ goes is $8$. Given this there are $7$ choices for the $Y$, and given that, there are $6$ choices for the $Z$. In the remaining $5$ slots, there are $10$ choices for each of them (the $10$ digits). This is $$8 \cdot 7 \cdot 6 \cdot 10^5 = 33600000$$

You were correct except that you wrote $5^{10}$ instead of $10^5$.

$\endgroup$
2
  • $\begingroup$ Thank you! If you or someone else has time, I also am looking for an explanation of the follow-up question: how many possibilities in which no two letters can be consecutive. $\endgroup$ Feb 21, 2018 at 20:43
  • 1
    $\begingroup$ For that follow-up question you should use complementary counting - it's easier to count the number of possibilities in which some two letters are consecutive (or all three) than it is to count the possibilities in which none are consecutive. $\endgroup$ Feb 21, 2018 at 20:49
0
$\begingroup$

For the second part you can follow the stars and bars method. If you set it up for your problem you should get ${8-3+1 \choose 3} 3!$ for the letters and same as first part for the numbers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .