Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

So the answer:

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

Seems a bit too easy, can anyone comments

Thanks!

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

1 Answer 1

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

share|improve this answer
    
Brian thanks for the answer. D(k,n) = ((n-1+k)/(k-1)) –  Daniel pltk Feb 3 '13 at 15:49
    
Brian, after reviewing your answer I have a question about the 1+x2+x3=4 part. As you basically want to exclude cases where there are 14 per x, how excluding x1 + x2 + x3 = 4 (which basically distributing 4 over x's, including case of x1=1, x2=3 and so on) helps you here? Thanks again. –  SyBer Mar 17 '13 at 16:32
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.