Total positive solution of a linear equation?

I have a linear equation in four variable

$a + b + c + d = 10$

given that $a, b, c, d > 0$ and $a,b,c,d <= 6$ and $a,b,c, d$ are integer

what are total possible solution ?

-
@Clayton - yes! –  AppDeveloper Jan 30 '13 at 23:38

Let's first enumerate the solutions with $a \le b \le c \le d$.
You must have $d \ge 10/4 = 2.5$, so $d = 3$, $4$, $5$ or $6$.

With $d=6$, $a+b+c=4$, and it's easy to see that $a=1$, $b=1$, $c=2$.

With $d=5$, $a+b+c=5$, and you could have $a=1$, $b=1$, $c=3$ or $a=1$, $b=2$, $c=2$.

With $d=4$, $a+b+c=6$, and you could have $a=1$, $b=1$, $c=4$, or $a=1$, $b=2$, $c=3$ or $a=2$, $b=2$,$c=2$.

With $d=3$, $a+b+c=7$, and you could have $a=1$, $b=3$,$c=3$ or $a=2$,$b=2$,$c=3$.

Thus the solutions with $a \le b \le c \le d$ are $[a,b,c,d] = [1,1,2,6]$, $[1,1,3,5]$, $[1,2,2,5]$, $[1,1,4,4]$, $[1,2,3,4]$, $[2,2,2,4]$, $[1,3,3,3]$, $[2,2,3,3]$. Take all permutations of those and you get all the positive integer solutions.

-
This is too painful. 7 is close enough to 10 that you should consider counting the complement. –  Calvin Lin Jan 30 '13 at 23:59

Hint: Use the Principle of Inclusion and Exclusion. In a general solution of positive integers $w + x + y + z = 10$, notice that at most one of the them can be at least 7.

Additional Hint: If $a\geq 7$, there is only 1 solution.

Hence, by PIE, there are ${9 \choose 3} - 1 - 1 - 1 - 1 = 80$ solutions.

For Poseidonium. Assuming we want to solve $a+b+c+d = 20, a, b, c, d \leq 6$.

Let sets $A, B, C, D$ be the ways such that $a \geq 7$, etc. By PIE, we have

$$|A \cup B \cup C \cup D| = \sum |A| - \sum |A\cap B| + \sum |A \cap B \cap C| - |A \cap B \cap C \cap D|$$

This is equal to $4 \times { 13 \choose 3} - 6 \times {7 \choose 3} + 6 \times {1 \choose 3} - 0 = 934$. Hence, the number of ways is ${19 \choose 3} - |A \cup B \cup C \cup D| = 35$.

[I would have approached this by solving $w + x + y + z = 4$, using the substitution $w =6-a$ etc, subject to $0 \leq w \leq 5$, which is clearly a non-restriction since the sum is only 4, thus there are ${4+3 \choose 3} = 35$ solutions.]

-
a lil more help? –  AppDeveloper Jan 30 '13 at 23:46
@AppDeveloper Do you know what PIE is? Have you applied it before? –  Calvin Lin Jan 30 '13 at 23:55
@Poseidonium Thanks! Strangely I'm not used to the positive integer version, and much more familiar with the $\geq 0$ complicated version lol. –  Calvin Lin Jan 31 '13 at 0:03
@Poseidonium Do you mean replace 10 by 30? If so, I'd do it directly by saying there are no solutions. –  Calvin Lin Jan 31 '13 at 1:03
@Poseidonium I've shown how to 'properly' apply PIE using $a+b+c+d = 20$ as an example. –  Calvin Lin Jan 31 '13 at 1:11

I would do by a combinatorial approach.

Let's say you have 10 books a bookshelf and you have 3 stands to partition the books. (a/b/c/d books and each / being the stand)

You don't put stands next to each other. (a,b,c,d > 0)

You don't want a partition bigger than 6.. (a,b,c,d <= 6)

We further break it down into simpler parts and slowly work to our solution.

Part 1

If we are not restricted to a maximum of 6 books, we can put the 3 dividers between any 2 books and that gives us 9 options, ie. ${}^9{C_3}=84$

Unfortunately, this is not our answer as there will be some cases when the partitioning has more than 6 books.

Part 2 (which are the cases which are not acceptable?)

If there is more than 6, it has to be the partitions of 1/1/1/7, 1/1/7/1, 1/7/1/1 or 7/1/1/1.

So, there are 4 unacceptable cases