4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) $\endgroup$ – Jack D'Aurizio Dec 19 '17 at 7:07
  • $\begingroup$ @Jack D'Aurizio I am sorry Sir but I am not able to understand the connection between my problem and the link You gave. I would be grateful if you explain your thought process in a few lines. $\endgroup$ – user399078 Dec 19 '17 at 7:11
  • $\begingroup$ The number of $(a,b,c,d,e)\in\mathbb{N}_+^5$ such that $a+b+c+d+e=n$ is the number of ways for putting four bars in the spaces between $n$ stars. In particular the cardinality of the set of $(a,b,c,d,e)\in\mathbb{N}^5$ such that $a+b+c+d+e=n$ is $\binom{n+4}{4}$. By combining this result with the hockey stick identity you can easily get that the number of $(a,b,c,d,e)\in\mathbb{N}^5$ such that $a+b+c+d+e\leq n$ is $\binom{n+5}{5}$. $\endgroup$ – Jack D'Aurizio Dec 19 '17 at 7:42
  • $\begingroup$ @Jack D'Aurizio I already know how to deal with such scenarios. I am actually asking for an alternative approach to solve the problem where you have to find the number of five digit numbers of the form $N=d_1d_2d_3d_4d_5$ such that $d_1 \leq d_2 \leq d_3 \leq d_4 \leq d_5$. $\endgroup$ – user399078 Dec 19 '17 at 8:48
  • $\begingroup$ It is the same problem :D $\endgroup$ – Jack D'Aurizio Dec 19 '17 at 9:42
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Super simple (+unity). Thank You so much for this amazing insight into the problem. $\endgroup$ – user399078 Dec 20 '17 at 1:18
  • $\begingroup$ How would you approach the problem if the constraint on digits was $d_1 \geq d_2 \geq d_3 \geq d_4 \geq d_5$ ? $\endgroup$ – user399078 Dec 21 '17 at 16:26
  • 1
    $\begingroup$ @Nirbhay if you just reverse the digits, that is the same problem except that you're now choosing digits from $\{0,...,9\}$, so the same approach gives ${}^{14}C_5$. $\endgroup$ – Especially Lime Dec 21 '17 at 17:16
  • $\begingroup$ Thank You so much for your help. My all doubts have been cleared now. $\endgroup$ – user399078 Dec 22 '17 at 16:16
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy