Find the number of n-digit numbers whose sum of the digits is 11.
How do I go about approaching this question, using P.I.E?
This is what I tried.
n = 11, when 1 + 1 + 1 + ... + 1 n = 2 when 5 + 6
-
$\begingroup$ @DonThousand This is not a duplicate since no digit may exceed $9$. $\endgroup$ – N. F. Taussig Nov 25 '19 at 10:04
$\begingroup$
$\endgroup$
This is just stars and bars over the digits of the $n$-digit number, under the condition that the highest digit is non-zero.
So, the question is equivalent to asking how many ways are there to pick non-negative solutions to $$x_1+x_2+...+x_n=10$$To which the answer is $$n+9\choose 10$$
The issue is that we need to ensure that $x_1<9$, $x_2,...,x_n<10$. So, that is a total of $2n-1$ cases to remove. So our final answer is $$\color{red}{{n+9\choose10}-2n+1}$$
answered Nov 25 '19 at 3:44
-
$\begingroup$ I get that the n + 9 comes from n + 10 - 1, but where does the 10 come from? Using stars and bars shouldn't it be $$ {10 + n -1 \choose n -1}$$ $\endgroup$ – hilh Nov 25 '19 at 3:49
-
$\begingroup$ hilh: ${n\choose k}={n\choose n-k}$, Don: I think you are missing that $x_n$ is a digit, so $x_n<10$. Also, it is $11$ not $10$. $\endgroup$ – farruhota Nov 25 '19 at 3:51
-
$\begingroup$ Shouldn't it be n - 1? Not 2n - 1 because there's a total of n numbers? $\endgroup$ – hilh Nov 25 '19 at 4:07
-
$\begingroup$ @hilh There are $n$ cases where one of them is non-zero and the rest are $0$. But, there are $n-1$ cases where the first one is $9$ and one of the others is $1$, and the rest $0$. $\endgroup$ – Don Thousand Nov 25 '19 at 4:10
-
1$\begingroup$ Originally: $x_1+x_2+\cdots+x_n=11, 1\le x_1\le 9,0\le x_i\le 9,2\le i\le n$. $\endgroup$ – farruhota Nov 25 '19 at 4:29
