Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics Two n-digit integers Question

  1. Jun 23, 2010 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Jun 23, 2010 #2


    User Avatar
    Homework Helper

    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
  4. Jun 23, 2010 #3

    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.
  5. Jun 23, 2010 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
  6. Jun 23, 2010 #5
    Thanks! I'm going to try it out and see where I end up.
  7. Jan 18, 2011 #6
    here is the solution:

    first lets 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 lets 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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook