What is the number of non-increasing 4 digit numbers?

Question

This problem, though quite simple, has stumped my teenage mind. How many 4-digit numbers are there whose digits are non-increasing? This seemed quite simple at first, meaning I have the digits [9 8 7 6 5 4 3 2 1 0], and I just pick four numbers from that which gives me the answer of 10C4, 210, but this fails to include the fact that a possible solution could be 9999, or 9988, or 6332, a number with repeating digits. How would I go about including this in an equation? What would that equation look like? I presume the solution would be something relating to the casework method, but I'm not very familiar with it in the first place.

Answer 1

Instead of normal combination , you should use combination with repetition , because the some digits may be equal such as $8888,6655$ etc if you use normal combination you find the digits of strictly increasing or decreasing. Then , $$C(10+4-1,4)=C(13,4)$$ by the formula of combination with repetition ,but realize that $C(13,4)$ counts the digit of $0000$ , so subtract it from total. Then asnwer is $C(13,4)-1$

Look at : Combination with repetition

Answer 2

So far you've counted all the options where there are four different digits making up the number, and realized that that isn't actually all of them. Now you need to figure out what the other options can look like.

I think that the cases you're close to identifying are the answers to the question "which digits are repeated?". So far, you've done the "all digits are different" case. Another one might be "the first digit is repeated three times, and the last digit is different". Another might be "all digits are the same". Think through all these cases, and for each one count them up in the same way as you did the "all digits are different" case.

Alternatively, you don't need to use cases if you want to think about it a bit differently. You started by picking four numbers out of [9,8,7,6,5,4,3,2,1,0], but you made them all different. So you were never going to get something with repeated digits. What happens if you still pick four numbers, but let yourself pick the same number again?

Answer 3

Alternative approach that reaches the same answer as that of Bulbasaur.

Actually, his Combination with Repetition article can be construed to be an alternative presentation of Stars and Bars which is also discussed here.

Consider any specific solution to

$$x_1 + x_2 + \cdots + x_{10} = 4, \tag1 $$

where $x_1, x_2, \cdots, x_{10}$ are all required to be
non negative integers,
and $x_k$ refers to the number of occurrences of the digit $k$
in the 4 digit number, when $k \in \{1,2,\cdots, 9\}$.
You can then let $x_{10}$ refer to the number of zeroes in the 4 digit number.

For each such solution, there is exactly one way that the 4 digits that correspond to the solution may be permuted into a non-increasing order.

Therefore, the enumeration of the possible satisfying number of 4 digit numbers is the same as the enumeration of the number of solutions to the equation in (1) above.

Per the linked articles, the number of solutions to
$x_1 + x_2 + \cdots + x_k = n$,
where $x_1, \cdots, x_k$ are required to be non-negative integers is
$\displaystyle \binom{n + [k-1]}{k-1}.$

In the present problem, $n = 4$ and $k = 10$.

Further, as suggested in the answer by Bulbasaur, since having the leftmost digit equal $0$ is normally prohibited, the specific 4 digit string of $0-0-0-0$ may or may not be required to be deducted from the overall count.