Integer solutions using PIE

Question

Find the number of integer solutions to $a+b+c+d=18$ with $ 0≤a,b,c,d≤6$.

With no restrictions there are:

$$\binom{21}{3} = 1330$$

Ones that are invalid are: $a, b, c, d \ge 7$.

But how do I take them out?

Answer 1

Setting $p=6-a$, $q=6-b$, $r=6-c$ and $s=6-d$ this comes to the same as finding the number of integer solutions of:

$$p+q+r+s=6$$

This under the condition that $p,q,r,s$ are firstly nonnegative and secondly do not exceed $6$.

Fortunately any solution that satisfies the first condition will automatically satisfy the second condition so we can leave that out, and use the Stars and Bars method.

Doing so we find: $$\binom{6+3}{3}=84$$ solutions.

Answer 2

A different approach:

$[\text{Number of combinations with sum } K] = [\text{Number of combinations with sum } 24-K]$.

So count the number of combinations with sum $6$ instead of $18$:

• Number of permutations of $6000$ is $\binom41\cdot\binom33=4$
• Number of permutations of $3111$ is $\binom41\cdot\binom33=4$
• Number of permutations of $0222$ is $\binom41\cdot\binom33=4$
• Number of permutations of $3300$ is $\binom42\cdot\binom22=6$
• Number of permutations of $2211$ is $\binom42\cdot\binom22=6$
• Number of permutations of $5100$ is $\binom41\cdot\binom31\cdot\binom22=12$
• Number of permutations of $4200$ is $\binom41\cdot\binom31\cdot\binom22=12$
• Number of permutations of $4110$ is $\binom41\cdot\binom32\cdot\binom11=12$
• Number of permutations of $3210$ is $\binom41\cdot\binom31\cdot\binom21\cdot\binom11=24$

Hence the total number of combinations is $4+4+4+6+6+12+12+12+24=84$.

---

EDIT:

To be honest, you don't even need the opening statement.

You can simply edit each bullet, and invert each digit $N$ with $6-N$.

Answer 3

I know that the OP has most likely the Principle of Inclusion-Exclusion as the method, but just as a check you can use generating functions to verify the answer by barak manos. Just consider $$(1+x+x^2+x^3+x^4+x^5+x^6)^4$$ Since we have 7 numbers to use for each $a,b,c,d$ and 4 variables to choose this will do the trick. Then just extract the coefficient from the $x^{18}$ term:
$$[x^{18}](1+x+x^2+x^3+x^4+x^5+x^6)^4=84$$

Answer 4

Since you specified PIE, here's the solution (though drhab's solution is slicker). Use stars and bars and apply PIE putting 7 in one or more "bins" so that it exceeds 6.

$${21\choose 3} - {4\choose 1}{14\choose 3} + {4\choose 2}{7\choose 3} = 84$$