6
$\begingroup$

Here is the question:

In how many ways we can construct a $11-$digit long string that contains all $10$ digits without $2$ consecutive same digits.

Initially, I came up with $10!9$. I thought that there are $10!$ ways to construct $10-$digit number with all $10$ digits. And I can add one more digit at the end of each number in $9$ ways.

However, I found that may wrong. Because I when applied the same rule to $4-$ digit number with $3$ digits $(0,1,2)$, the answer is not $3!2$. For example, it doesn't contain $1210, 2120, 0102, ...$

So how to approach this problem?

$\endgroup$
0

3 Answers 3

Reset to default
10
$\begingroup$

All your desired strings have one digit that occurs twice, while the others occur once. So here is a method to get all those strings:

  1. Place all ten digits into a ten-digit string. This can be done in $10!$ ways.
  2. Choose one digit to be the repeated digit. This can be done in $10$ ways.
  3. Choose a position in the ten-digit string from step $1$ to insert that repeated digit. The ten-digit string has $11$ places to insert, but $2$ of them are next to the same digit, so there are $9$ allowable places to insert the digit.

Inserting the digit into the position in the ten-digit string gives us an allowable eleven-digit string. However, we have double-counted every eleven-digit string, since we could have inserted the other occurrence of the repeated digit. So we must divide our count by two.

Our final count is then

$$\frac{10!\cdot 10\cdot 9}2=163,296,000$$

In your check of $4$-digit strings with $3$ digits, that would be

$$\frac{3!\cdot 3\cdot 2}2=18$$

A quick check of that in MS Excel confirms that is correct. (For the $4$-digit strings: even Excel doesn't easily handle over one hundred million lines!)

$\endgroup$
2
  • 2
    $\begingroup$ Very nice and clear. As an aside, a slight alteration evades the double-counting: 1. Choose a digit to repeat (10), 2. Place the remaining 9 into a string (9!), 3: Choose 2 different positions from the available 10 positions (including start and end) - since these are different positions, we will not double count or get the 2 next to each other, (10C2 = 10!/(8!.2!)= 10*9/2 = 45. $\endgroup$
    – Phil H
    Jun 29, 2015 at 14:45
  • $\begingroup$ @PhilH: Yes, your method is very nice. I did not think of that particular method, but I did design mine to be close to what the OP had tried. $\endgroup$
    – Rory Daulton
    Jun 29, 2015 at 14:48
3
$\begingroup$

You have to repeat exactly one digit.

So, first choose the digit that you repeat (how many possibilities?), then choose where those two digits go in the number (how many possibilities?), and finally choose the order for the remaining $9$ digits (how many possibilities?)

(The answer is $163,296,000$.)

$\endgroup$
4
  • $\begingroup$ I got $10$ ways to select the digit I want to repeat, $C(11,2)$ ways to place the repeated digit, and $9!$ ways for the remaining 9 digits. And the result was wrong. Where is my problem? $\endgroup$
    – PHPIsTheBestLanguage
    Jun 29, 2015 at 14:05
  • $\begingroup$ You don't have C(11,2) ways to place the repeated digit because you can't place the repeated digit next to each other. $\endgroup$
    – Amy B
    Jun 29, 2015 at 14:09
  • $\begingroup$ Oops you are right, I forgot it. :P $\endgroup$
    – PHPIsTheBestLanguage
    Jun 29, 2015 at 14:21
  • $\begingroup$ Right: $10 \cdot (_{11}C_2 - 10) \cdot 9!$ $\endgroup$
    – John
    Jun 29, 2015 at 18:41
1
$\begingroup$

How many repeat digit $1$? There are $\frac{11!}{2}$ orders total but $10!$ of those have both $1$'s together (put the two $1$'s together forming a single object). Hence there are $\frac{11!}{2}-10!=\frac{9\cdot10!}{2}$ that repeat digit $1$, which implies there are $\frac{10\cdot9\cdot10!}{2}=5\cdot9\cdot10!$ total.

$\endgroup$
2
  • $\begingroup$ I'm not quite understanding $11!/2$ orders for a repeat digit. How did you get that? $\endgroup$
    – PHPIsTheBestLanguage
    Jun 29, 2015 at 14:07
  • $\begingroup$ There are $11!$ ways to order $11$ objects. But you have the number one twice, so each arrangement is being counted two times. hence there are $\frac{11!}{2}$ ways. $\endgroup$
    – Asinomás
    Jun 29, 2015 at 14:10

You must log in to answer this question.

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