Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm working on some homework right now, and I've gotten stumped. Here's the question I'm on:

How many of the 9000 four-digit integers 1000, 1001, 1002, . . . , 9998, 9999 have four distinct digits that are either increasing (as in 1347 and 6789) or decreasing (as in 6421 and 8653)?

Through some Googling I've already found what they answer may be, but I have no idea how to arrive at the answer, so I wouldn't be learning anything from this hurdle like I'm supposed to. I can use all the help I can get on this one since I don't even know where to start. I think I have to apply the formula for permutations to this somehow, but I don't know what adjustments I have to make for it to work right.

share|cite|improve this question
2  
If you have a number xyza, where x, y, and z are known, and "a" unknown, and xyza is monotonic (either increasing or decreasing), how many choices do you have for a? – Doug Spoonwood Jan 24 '13 at 11:32
    
Have you tried some smaller example, e.g. calculating such numbers between $10$ and $55$ in base $6$ for example and then try to find a general rule. – Julian Kuelshammer Jan 24 '13 at 11:56
    
@DougSpoonwood - Okay, I think I see what you mean, I would have 10 choices there, unless I wasn't counting the zeroes for the ascending group. I don't quite understand how x, y, and z are known though. – Dave Jan 24 '13 at 12:08
    
@JulianKuelshammer - I'll give that a try. That has worked for me on some of the other permutation puzzles we've been doing, but I didn't think it would offer any insight on this one. This is a much more difficult problem than the others due to some base concept I seem to be missing. – Dave Jan 24 '13 at 12:09
up vote 3 down vote accepted

Once you've chosen the four digits, there's only one way to arrange them increasing, and one way decreasing, so it comes down to, how many ways are there to choose four digits? Oh, there's one little tricky bit: if you choose zero, you can't do increasing.

share|cite|improve this answer
    
Hmm, that's a good nudge for me, and helps with part of what I was confused about, but without considering the 0 for increasing permutations I see it as P(9000, 4), which I KNOW isn't right. 9000! would be an absolutely ridiculous number such that dividing it by 4! wouldn't bring it anywhere near the range I'm looking for. – Dave Jan 24 '13 at 11:43
    
Ack! You're choosing $4$ digits (from 10), not $4$ numbers from $9000$. – Gerry Myerson Jan 24 '13 at 11:59
    
Okay, 4 digits from 10. Well, ascending it would be four digits from 9 since no zeroes work. Descending will work with zeroes, though, so that could be 4 digits from 10. So it seems maybe I'm looking at (9 4) + (10 4)? Also, I really don't understand how this could work this way. How does solving for choosing four digits get me the number of compositions that are only ascending? – Dave Jan 24 '13 at 12:05
    
I don't know what you mean by the notation $(9\ 4)$. You choose the four digits. As I wrote, there is only one way to arrange the four digits you have chosen so that they are ascending. So the number of 4-digit integers with increasing digits is the same as the number of ways of choosing 4 digits. Right? – Gerry Myerson Jan 24 '13 at 12:10
    
Better notation to use there might be P(9,4) for ascending, as it's how I usually see nPr written when formula editors are not available, but it could also be written as 9P4 I suppose. So lets say I choose 1234. They are already arranged as ascending. So I use P(9,4). It seems to me that this wouldn't include combinations such as, say, 5678. As I said in reply to one of the comments above, there is something very basic that my mind hasn't accepted yet. – Dave Jan 24 '13 at 12:17

If you're looking for how many 4 digit numbers are increasing or decreasing between 1000 and 9999, the answer has been provided here: How many of the 9000 four digit integers have four digits that are increasing?

If you (or since this was posted 3 years ago, if a discrete math student) are looking for how many non-decreasing or non-increasing 4-digit numbers there are between 1000 and 9999, I believe I have the answer. *the difference is that non-decreasing can have 1226 or 7888 while increasing cannot have repetition.

$\binom{10}{4}$ is the correct answer for decreasing combinations, while $\binom{10}{4} - {9 \choose 3}$ is the answer for increasing combinations because you can't begin the 4 digit segment with (or include) a zero.

The same idea applies to non-decreasing / non-increasing values, this time we allow for repetition, so for every integer after the 1st integer, we have +1 choices in digits.

For decreasing numbers, 3210 was the only option where the 1st digit was 3. This is reflected by $\binom{3}{3}$. Now, since we can have 4-digit numbers like 3332, 3200, and 3111, we have $\binom{3+3}{3}$ combinations. We then have to subtract 1 because 3333 is not a non-increasing number.

So, this same principle applies. We get $\binom{10+3}{4}$ + ($\binom{10+3} {4} - \binom{9+3}{3}$) - 10 = 1200. We subtract ten because 1111,2222,...9999 are not valid options for either non-increasing nor non-decreasing.

Final answer = 1200.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.