1
$\begingroup$

I came across this question, that how many 4 digit numbers $a_1a_2a_3a_4$ are there such that

$a_1\geq a_2\geq a_3\geq a_4$

I know the answer for this case,

$a_1>a_2>a_3>a_4$

I need a hint to solve that case with equality sign as well. (I have already done this question in class, but since I dont make notes so its lost)

3 Answers 3

6

Hint: Imagine that we have $13$ "digits," the usual $0$ to $9$, and in addition the digits $\alpha$, $\beta$, $\gamma$, to be thought of as representing $10$, $11$, and $12$ respectively.

Pick a strictly descending sequence $x_1, x_2, x_3, x_4$ of length $4$ from this new digit set of $13$ digits. You know how to count how many such strictly descending sequences there are.

Let $a_4=x_4$, $a_3=x_3-1$, $a_2=x_2-2$, $a_1=x_1-3$. Show that this produces every non-increasing sequence $a_1\ge a_2 \ge a_3 \ge a_4$ in one and only one way.

Now we need to adjust for the unpleasant fact that the initial digit of a $4$-digit number cannot be $0$. That translates into the fact that the strictly descending sequence $x_1=3$, $x_2=2$, $x_3=1$, $x_4=0$ is not allowed.

Remark: The above procedure has nothing much to do with digits. The number of never increasing sequences of length $k$ from the set $\{1,2,\dots,n\}$ is the same as the number of strictly decreasing sequences of length $k$ from the set $\{1,2,\dots,n,n+1,\dots, n+k-1\}$.

Added: The number of strictly decreasing sequences of length $4$ from the digits $0, 1,\dots, 9$ is just $\binom{10}{4}$, the number of ways to choose $4$ distinct numbers. If we use the "digits" $0,1,\dots,9,\alpha,\beta,\gamma$, then the number of strictly decreasing sequences is $\binom{12}{4}$. We must subtract $1$ because $3,2,1,0$ is not allowed.

  • 0
    Its a cute technique. Clearly I have large gaps in my combinatorics education! Obviously (as in after the fact) one can also go the 'other way' as well (ie, knowing the formula for decreasing sequences, you can use this sort of trick to get the formula for strict sequences by removing digits).2012-04-27
1

I assume you solved the first case by noting that order was predetermined, so you only had to figure out how many ways you could pick 4 distinct digits.

Well, order is still determined by which digits you pick, you just have the possibility of picking the same digit multiple times. So, how many ways can you pick 3 digits, with one of them occurring twice? Two digits, each occurring twice? Two digits, one occurring 3 times? One digit? (Be careful in the one-digit case if you don't want to count 0000 as a 4-digit number).

  • 0
    Thanks, that was really helpful.2012-04-27
1

Here is a far more laborious approach:

Let $T_{k,n}$ be the number of $k$ digit 'decreasing digit numbers' starting with the digit $n$. It should be clear that $T_{1,n} = 1$, and that $T_{k+1,n} = \sum_{i=0}^n T_{k,j}$. Now 'all' we have to do is to find a formula for $T_{k,n}$, and then our answer will be $T_{4,9}+...+T_{4,0} = T_{5,9}$.

My pedestrian approach is to figure out a few terms and make an educated guess as to the formula. A few summations gives: $T_{1,n} = 1$, $T_{2,n} = n+1$, $T_{3,n} = \frac{(n+1)(n+2)}{2}$. So, I posit $T_{k,n} = \binom{n+k-1}{k-1}.$ To check, I verify that this satisfies the recurrence and boundary condition using the binomial coefficient recursion identity. So, the answer is $T_{5,9} = \binom{12}{4} = 495$.

Correction: I believe there is a mistake in the above computation. The symbol $n$ is the starting digit. To get the correct result, one needs the the number of $k+1$ digit 'decreasing digit numbers' starting with the (fictitious) symbol $n+1$. Thus the answer should be $T_{5,10} = \binom{13}{4} = 715$. I believe the same mistake was made in the other answer as well (there are 13 symbols).