Combinatorics Two n-digit integers Question

[space_borscht]

Homework Statement

Two n-digit integers (leading zeros allowed) are considered equivalent if one is a rearrangement of the other. (For example, 12033, 20331, and 01332 are considered equivalent five-digit integers.) If the digits 1, 3, and 7 can appear at most once, how many
nonequivalent five-digit integers are there?

(Problem 11 from Chapter 1.4 of Grimaldi's DISCRETE AND COMBINATORIAL MATHEMATICS)
Noted for any future use it might serve.

Homework Equations

?

The Attempt at a Solution

I know that effectively only 7 integers are being considered. That would give a base number to our solution of C(11, 5) where 7 (before the n + r -1 procedure in the combination formula) is the number of distinct items in our combination and 5 the number of repetitions. What I don't know is what to do with the remaining 3 integers. I know the answer from looking at the back of the book, but can't reason how it was derived.


The answer (forgive me if my notation isn't correct):
C(11, 5) + 3*C(10, 4) + 3*C(9, 3) + 3*C(8, 2)

I guess the further additions after the initial C(11, 5) account for them, but I don't have the faintest idea why that is so. Thanks.

 

[lanedance]

the hint is in the 4 terms - think of the following 4 cases:
- when the number has no 1, 3, or 7s
- when the number has one of 1,3,7
- when the number has two of 1,3,7
- when the number has all three of 1,3,7

 

[space_borscht]

the hint is in the 4 terms - think of the following 4 cases:
- when the number has no 1, 3, or 7s
- when the number has one of 1,3,7
- when the number has two of 1,3,7
- when the number has all three of 1,3,7

Hi,

I've tried everything I know. There has to be some fundamental aspect of these types of arrangements that I just don't comprehend.

This is about as far as I get:

It's obvious that only unique combinations are being quantified. Therefore, 12345 is the same as 54321. But let us add a variable to a 4 digit string, like x to x1234. This will count as the same integer for any position it should take, so the strings 1x234 and 4231x are all the same, for example. What I don't know is, whether it is safe to assume that this extra variable will mean that there are now an additional C(11, 5) nonequivalent integers. Because this is the only thing that makes sense to me, but it isn't congruent with the above answer, or not entirely. I am just so lost here. Please help.

 

[Office_Shredder]

You might have some success if you start by ignoring the restriction on 1 3 and 7. How many non-equivalent five digit integers are there? Now find out how many of them have two 1's, two 3's or two 7's and subtract that from your total count

 

[space_borscht]

You might have some success if you start by ignoring the restriction on 1 3 and 7. How many non-equivalent five digit integers are there? Now find out how many of them have two 1's, two 3's or two 7's and subtract that from your total count

Thanks! I'm going to try it out and see where I end up.

 

[albert_s]

here is the solution:

first let's count the number of nonequivalent integers WITHOUT 1,3,7
using the formula C(n+r-1,r)
that number is C(7+5-1,5) = C(11,5)

now let's count the number with only 1 but not 3 and not 7
which means we only have to fill in 4 remaining spots
that number is: C(7+4-1,4) = C(10,4)
by the same calculation there is the same number of nonequivalent integers with only 3 (but not 1,7) and also the same number with 7 (but not 1,3)
so the total with only one of (1,3,7) is 3*C(10,4)

the next case to examine is integers with pairs of the numbers (1,3) (1,7) (3,7)
there is again 3 such cases.
the number of 1 case is C(7+3-1,3) = C(9,3)
so total is 3*C(9,3)

now, the last case is when all three of (1,3,7) appear in the number
the number here is C(7+2-1,2) = C(8,2)so our final answer is the sum of all these:

C(11,5) + 3*C(10,4) + 3*C(9,3) + C(8,2)

and that is the answer at the back of the book.

hope this helps