Problem:
All possible 6-digit numbers, in each of which the digits occur in non-increasing order (from left to right, e.g., ) are written as a sequence in increasing order. Find the -th number in this sequence.
Problem:
All possible 6-digit numbers, in each of which the digits occur in non-increasing order (from left to right, e.g., ) are written as a sequence in increasing order. Find the -th number in this sequence.
Solution:
Consider a 6-digit number whose digits from left to right are in non-increasing order. If is the first digit of such a number, then the subsequent digits cannot exceed . The set of all such numbers with initial digit equal to is
There are elements in this set.
Let us consider 6-digit numbers with initial digit . Starting from , we can go up to . We count these numbers as follows:
| - | ||||
|---|---|---|---|---|
| - | ||||
| - | ||||
| - | ||||
| - | ||||
| - |
Similarly we count numbers with initial digit ; the sequence starts from and ends with . We have
| - | ||||
|---|---|---|---|---|
| - | ||||
| - | ||||
| - | ||||
| - | ||||
| - |
Similarly,
It is known that the number of ways of choosing objects from different types of objects (with repetitions allowed) is . In particular, if we want to write -digit numbers using digits allowing for repetitions with the additional condition that the digits appear in non-increasing order, we see that this can be done in ways.
Now we group the given numbers into different classes and write the number of ways in which each class can be obtained. To keep track we also write the cumulative sums of the number of numbers so obtained. Observe that the numbers themselves are written in ascending order. So we exhaust numbers beginning with , then beginning with and so on.
| Numbers | Digits used other than the fixed part | Cumulative sum | |||
|---|---|---|---|---|---|
| beginning with | |||||
| from to | |||||
| from to |
Hence the -th number in the sequence is .