2

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.

Dave
  • 237
  • 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

2 Answers2

3

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.

Gerry Myerson
  • 179,216
  • 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
  • I don't think you know what $P(9,4)$ means. $${}$$ Please read what I've actually written. "You choose the four digits." How many ways are there to choose 4 things from a set of 9 things? Hint: combinations of 9 things taken 4 at a time. $${}$$ Now: having chosen the 4 digits, how many ways are there to put them in ascending order? Hint: One! $${}$$ So: how many 4-digit numbers are there with increasing digits? – Gerry Myerson Jan 24 '13 at 12:27
  • Okay, something clicked that time. So, I'm going to take 4 numbers out of the nine, but I'm going to do this twice. Then, I have to account for the possible zeroes when descending, so I'm going to assume a zero at the end, which means I'll be taking 3 of the 9 numbers, which will be added to the other two where I took 4. And here's my last shot at notation. =) EDIT: Notation didn't work out, it was formatted away. Imagine the numbers in parenthesis vertical: 2(9 4)+(9 3) – Dave Jan 24 '13 at 12:37
  • Got the answer of 336 and I'm pretty sure I understand why. My brain is resisting it for some reason, but I know it's right and I could do it again, so you get credit for the answer. I would vote it up if I had the rep for it, so instead accept my thanks for being patient with me through that. – Dave Jan 24 '13 at 12:46
  • I also got 336. Well done! – Gerry Myerson Jan 24 '13 at 22:33
0

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.

Community
  • 1
adhdj
  • 1