# Number of four digit numbers?

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)

-

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.

-
Sir , I still dont get it, –  Tomarinator Apr 27 '12 at 17:00
You are dealing with small numbers, so the approach by Bert Frankel may work out better for you. But I will add some material in the way of explanation. –  André Nicolas Apr 27 '12 at 17:07
Thanks I get it now, after some thinking,our teacher had another interesting way to solve this question, which I cant seem to remember though. –  Tomarinator Apr 27 '12 at 17:10
I think you have a typo. or two. Presumably $a_4 = x_4$, $a_3=x_3+1$, etc.? –  copper.hat Apr 27 '12 at 19:00
@copper.hat: Thank you, there were a few, perhaps more than two. Maybe all fixed. It should be $a_4=x_4$, $a_3=x_3-1$, $a_2=x_2-2$, $a_1=x_1-3$. I had special troubles because indices run the "wrong" way. –  André Nicolas Apr 27 '12 at 19:08

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).

-
Thanks, that was really helpful. –  Tomarinator Apr 27 '12 at 17:10

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).

-