Looking for an alternative elegant solution to this Combinatorial Problem.....

Question

We were asked to find the number of five digit numbers $N=d_1d_2d_3d_4d_5$, where $d_i$ is the $i$th digit of the number and $d_1 < d_2 < d_3 < d_4 < d_5 $. The solution was trivial as for a given selection of five random distinct digits, there is only one way to arrange them in strict increasing order. Now to raise the difficulty level of the question, our teacher changed all the "less than" signs into "less than or equal to" signs, thus yielding the new constraint $d_1 \leq d_2 \leq d_3 \leq d_4 \leq d_5$.

I proceeded as follows .....

Let $x_i = d_{i+1} - d_i$. So, $$ x_1 + x_2 + x_3 + x_4 = d_5 - d_1,$$ or $$d_1 + x_1 + x_2 + x_3 + x_4 = d_5 \leq 9.$$ But $d_1 \geq 1, x_i \geq 0$ for all $i $ belonging to the set ${1,2,3,4} $. So, the problem reduces to find the number of non negative integral solutions of the inequality $$d_1 + x_1 + x _2 + x_3 + x_4 \leq 8,\quad (*)$$ which comes out to be $^{13} C_ {5}$.

But looking at the simplicity of the answer, I am bound to think that there must exist some elegant approach to this problem. In Combinatorics, every one thinks differently, which is why I ask this question. I just want to explore the different ways one can approach a problem. Please note that I am just a beginner in Combinatorics. I am familiar with Permutations and Combinations, but I do not know a single thing in Graph Theory and all those "advanced" concepts. So please answer accordingly.

Answer 1

Here's an essentially equivalent approach that may be what you're looking for. Instead of looking for possible values $d_1,...,d_5\in\{1,...,9\}$ such that $d_1\leq d_2...\leq d_5$, try setting $c_i=d_i+i$ for each $i$. Now $c_1,...,c_5\in\{2,...,14\}$ and $c_1<c_2<...<c_5$, so there are ${}^{13}C_5$ ways to choose the $c_i$. Each of these choices can be converted back to a (different) valid choice for the $d_i$.

Answer 2

Let $F(n)$ be the number of $n$-digit numbers whose digits are strictly increasing from L to R. The answer to your Q is $$(F(5)+4F(4)+3F(3)+2F(2)+F(1))+(3F(3)+2F(2))=$$ $$=F(5)+4F(4)+6F(3)+4F(2)+F(1).$$

Explanation:

(i). $F(5)$ ways with $5$ different digits.

(ii). Given $4$ strictly increasing digits, there are $4$ different numbers obtained by inserting a $5$th digit equal to and adjacent to one of those $4$ digits, giving $4F(4) .$

(iii). Given $3$ strictly increasing digits $d_1d_2d_3,$ there are $3$ numbers obtained by inserting $2$ identical digits, equal to and adjacent to one of those three (i.e. $d_1d_1d_1d_2d_2d_3$ or $d_1d_2d_2d_2d_3$ or $d_1d_2 d_3d_3d_3$), giving $3F(3).$

(iv). Given increasing $d_1d_2$ there are $2$ numbers obtained by inserting $3$ digits adjacent to and equal to $d_1$ or to $d_2,$ giving $2F(2).$

(v). Given one digit, adding $4$ more equal to it gives $F(1)$ different numbers of the form $ddddd.$

(vi). Given $3$ increasing digits there are $3$ numbers obtained by repeating one of those $3$ digits and repeating another of those $3$ digits, giving $3F(3).$

(vii). Given increasing $d_1d_2$ there are two numbers obtained by inserting $2$ copies of $d_1$ and one copy of $d_2$ or vice-versa (i.e. $d_1d_1d_1d_2d_2$ and $d_1d_1d_2d_2d_2),$ giving $2F(2).$

The expression $F(5)+4F(4)+6F(3)+4F(2)+F(1)$ is suggestive of the formula $(x+1)^4=x^4+4x^3+6x^2+4x+1,$ so there may be a slicker generalization involving generating polynomials. If it were not 4 a.m. here, I might think of one (if there is one).

Answer 3

Your approach can maybe streamlined somewhat, but it is the textbook solution for this problem.

I'd put it this way: Look at weakly ascending seven letter words $\ 1\ d_1\ d_2\ d_3\ d_4\ d_5\ 9\ $. There are six slots for an increment $x_k\geq0$, and the sum of the increments should be $9-1=8$. By "stars and bars" you can choose these increments in ${8+5\choose 5}=1287$ ways.