Number of 11 digit positive integers with non decreasing digits and finding the sum of digits of N
Citing the above question previously asked on this site, I have an alternate approach to this. I have used a systemic approach, analyzing what happens in different cases:
Case-I: Numbers formed only by 1 digit: The number of numbers, in this case, becomes $^9C_1(\times^{10}C_{10})=9,$ i.e, $9$ ways to choose the number from the set $\{1,\,2,\,…,\,9\}$ and $^{10}C_{10}=1$ way to choose the position where we increment the number, i.e. no increment is possible (as we have chosen the numbers formed only by 1 digit).
Case-II: Numbers formed by 2-digits: The number of numbers, in this case, becomes $^9C_2\times^{10}C_{9}=9.$
Similarly, casing for the rest we, find the general formula.
$\therefore N=\sum_{i=1}^{9} {9}C_i\times^{10}C_{11-i}$
But, using this summation, I am getting a wrong answer compared to what is given in the book. Can anyone please highlight the fault in my method above?
Edit: Thanks for the helpful answer for that alternate approach. I found out that my mistake just boiled down to a miscalculation. Anyways, thanks a ton!
Best Answer
You have correctly counted the number of eleven-digit positive integers with non-decreasing digits. However, you have not found the sum of those numbers (if that is your goal).
Let's do the problem another way first. Observe that a positive integer with non-decreasing digits is completely determined by how many times each digit appears. For instance, if the digits of the $11$-digit number include one $6$, one $7$, two $3$s, three $5$s, and four $8$s, it must be the number $33555678888$ since the digits are non-decreasing.
Let $x_i$ be the number of times the digit $i$ appears in the eleven-digit positive integer with non-decreasing digits. Observe that the integer cannot include the digit $0$ since a string with leading digit $0$ would not represent an $11$-digit positive integer. Since there are a total of $11$ digits, $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 11 \tag{1}$$ is an equation in the nonnegative integers.
A particular solution of equation 1 corresponds to the placement of $9 - 1 = 8$ addition signs in a row of $11$ ones. For instance, $$++11++111+1+1+1111+$$ corresponds to the solution $x_1 = x_2 = 0, x_3 = 2, x_4 = 0, x_5 = 3, x_6 = x_7 = 1, x_8 = 4, x_9 = 0$ and the $11$-digit positive integer $33555678888$. The number of $11$-digit positive integers is the number of solutions of equation 1 in the nonnegative integers, which is $$\binom{11 + 9 - 1}{9 - 1} = \binom{19}{8} = 75,582$$ since we must select which $8$ of the $19$ positions required for eleven ones and eight addition signs will be filled with addition signs.
As you observed, if we use $k$ distinct digits in the eleven-digit number, there are $\binom{9}{k}$ ways to select the digits which are used in that number. If there are $k$ distinct digits, then $k - 1$ transitions must occur. There are $10$ possible transition points in an $11$-digit number. Thus, the number of ways we can select where these $k - 1$ transitions can occur is $\binom{10}{k - 1}$. Hence, the number of $11$-digit positive integers with non-decreasing digits is $$\sum_{k = 1}^{9} \binom{9}{k}\binom{10}{k - 1} = 75,582$$ Since $$\binom{10}{k - 1} = \binom{10}{10 - (k - 1)} = \binom{10}{11 - k}$$ your formula yields the correct answer for the number of $11$-digit positive integers with non-decreasing digits.