# Inclusion Exclusion combinatorics 101 question

I have a simple question from text-book about this subject to see if I got it right.

Say I have a natural number below 1000, and I need to find all combinations of it's digits that their sum will be 14.

Now it basically:

0<=x1,x2,3<=9, with x1 + x2 + x3 = 14.


Going the inclusion - exclusion way, the solution seems to be:

|U| = D(3,14)
|S1|=|S2|=|S3| = D(3,4)


|U|-|S1|+|S2|-|S3| = D(3,14) - D(3,4)


Seems a bit too easy, can anyone comments

Thanks!

-
What do you mean by $D(k,n)$? – Brian M. Scott Feb 2 '13 at 23:01

I count $\binom{14+3-1}{3-1}=\binom{16}2$ unrestricted solutions to $x_1+x_2+x_3=14$ in non-negative integers. The equation $x_1+x_2+x_3=4$ has $\binom{4+3-1}{3-1}=\binom62$ such solutions, so there are $\binom62$ solutions to the first equation that have $x_1>9$. Thus, there are $3\binom62$ solutions to $x_1+x_2+x_3=14$ in which one of the variables exceeds $9$. It’s impossible for two to exceed $9$, so the final total is
$$\binom{16}2-3\binom62=75\;.$$
@SyBer: I want (first) to exclude those solutions that have $x_1>9$. If I have such a solution, $x_1\ge 10$, and the numbers $y_1=x_1=10,y_2=x_2$, and $y_3=x_3$ are a solution to $y_1+y_2+y_3=14-10=4$ in non-negative integers. Conversely, if $y_1+y_2+y_3=4$, where $y_1,y_2$, and $y_3$ are non-negative integers, then setting $x_1=y_1+10,x_2=y_2$, and $x_3=y_3$ gives me a solution to $x_1+x_2+x_3=14$ with $x_1>9$. Thus, there are exactly as many solutions to $x_1+x_2+x_3=14$ with $x_1>9$ as there are non-negative solutions to $y_1+y_2+y_3=4$, and we know that there are $\binom62$ of those. ... – Brian M. Scott Mar 17 '13 at 16:59
... There are another $\binom62$ solutions to $x_1+x_2+x_3=14$ that have $x_2>9$, and yet another $\binom62$ that have $x_3>9$, so there are altogether $3\binom62$ of these unwanted solutions. – Brian M. Scott Mar 17 '13 at 17:00