5
$\begingroup$

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.

$\endgroup$

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ eleborated and clear !! and better than my answer +1 $\endgroup$ Commented Nov 5, 2021 at 21:04
  • 1
    $\begingroup$ Minor comment: funny you said you can let $x_{10}$ refer to the number of zeros, when you could've just written $x_0$! $\endgroup$
    – qwr
    Commented Nov 6, 2021 at 5:53
  • $\begingroup$ @qwr That approach would have muddied the waters. It was important to stay exactly within the framework of the variables being indexed as $x_1, x_2, \cdots, x_k$, so that the stark application of the theory in the cited Stars and Bars articles would have been immediately inescapable. This is better than forcing the reader (who might be very unfamiliar with the theory) to infer that when the variables are indexed $x_0, x_1, \cdots, x_9$, that then $k = 10$ rather than $k = 9$. $\endgroup$ Commented Nov 6, 2021 at 7:41
  • $\begingroup$ I think the reindexing makes things clearer but I see your point $\endgroup$
    – qwr
    Commented Nov 6, 2021 at 23:17
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ +1 for the creative of finding the Combination with repetition article/approach. See also my answer. $\endgroup$ Commented Nov 5, 2021 at 21:01
  • $\begingroup$ I think this answer is indeed correct! Much appreciation for both you and user266193 (answered below)! That makes much more sense! Also, thanks for introducing the idea of combinations with repetition to me. I learned both a new theory and formula! Thanks again! $\endgroup$
    – JJD
    Commented Nov 5, 2021 at 23:57
1
$\begingroup$

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?

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .