5
$\begingroup$

I'm doing a bit of revision and want to make sure I'm doing these two questions correctly. They are as follows:

Two n-digit (leading zeros allowed) numbers are considered to be equivalent if one is a rearrangement of the other.

a) What is the largest number of 5-digit numbers that can be produced so that no two are equivalent?

I think this just an unordered selection of 5 numbers from 10 options with repetition allowed. So $ {{10+5-1} \choose {5}} = { 14 \choose 5} = 2002$

b) What is the largest number of 5-digit number that can be produced so that no two are equivalent and none on the digits 1, 3, 7 appear more than once.

Assuming part a) is correct we can use inclusion-exclusion with the conditions:

$c_1: 1 $ appears more than once

$c_2: 3 $ appears more than once

$c_3: 7 $ appears more than once

$\bar{N} = {14 \choose 5} - 3{12 \choose 3} + {3 \choose 2}{10 \choose 1} = 1372$

Is this correct? If not could you point out where I went wrong?

Thanks

  • 1
    Yes, it looks fine.2012-06-06

1 Answers 1

0

I know this was a while ago, but I just did the same problem for my math homework. The first part (part a) is correct. Part B is different than what I came up with (double-checked in the back of my textbook). However, mine says

If the digits 1, 3, and 7 can appear at most once, how many non-equivalent five-digit integers are there?

I'm posting my answer in case a word was forgotten in your question? Or someone else is looking up the answer - like how I found this one!

The answer is ${11 \choose 5} + (3){10 \choose 4} + (3){9 \choose 3} + {8 \choose 2}$

I wanted to start with ${14 \choose 5}$, too, but you start off with 10 options (the digits 0 through 9) to be able to repeat. However, subtract 3 from 10 because you can only use 1, 3, and 7 once each if they appear. That leaves you with 7, so

${7+5-1 \choose 5} = {11 \choose 5}$

Part one of our answer!

Think of the following 4 cases:

  1. When the number has no 1's, 3's, or 7's (1 option)
  2. When the number has one of 1, 3, or 7 (3 options)
  3. When the number has two of either 1, 3, or 7 (so pairs of 1 and 3, 1 and 7, or 3 and 7)
  4. When the number has all three of 1, 3, and 7 (1 option)

We already figured out case #1. For case #2, we will have $(3){10 \choose 4}$ because there are 3 ways we can have one 1, one 3, or one 7. The ${10 \choose 4}$ comes from ${6+5-1 \choose 5-1}$ because we eliminate one of the options.

For case #3, we get $(3){9 \choose 3}$ because we keep removing options as we work our way down.

There is only one option left for case #4, so we get ${8 \choose 2}$.

This gives us ${11 \choose 5} + (3){10 \choose 4} + (3){9 \choose 3} + {8 \choose 2}$.