Integer solutions to an equation using combinatorics

How many nonnegative integer solutions are there to the equation $$A_1 + A_2 + A_3 + A_4 = 25$$ such that $$A_1 \leq 12$$ and $$A_4 \leq 10$$?

I am completely lost on how to solve such a question.
If someone could give me a detailed solution, I would greatly appreciate it.

• I feel that there's a mistake in the phrasing of the question - what's $A_5$? Dec 6, 2018 at 6:25
• Sorry about that, its fixed now Dec 6, 2018 at 6:29
• How many choices are their for A1? 12 (13 if you include 0 I suppose). How many choices are there for A4? 10? So how many pairs of A1 and A4 can you have? Dec 6, 2018 at 6:36
• I'm not quite sure....The question was stated exactly as above. Dec 6, 2018 at 6:40
• @DanielOnMSE More is needed since have to assign $A_2,A_3.$ Dec 6, 2018 at 7:04

We can think of it in this way:

We find all cases for the equation without restriction of $$A_1\leq12$$ and $$A_4\leq10$$. Then we fill in these cases with a 2-circle Venn Diagram, the first circle ($$P$$) with cases satisfying $$A_1>12$$ (yes, $$>$$), and the second circle ($$Q$$) with cases satisfying $$A_4>10$$. Then what we want to find is $$P'\cap Q'$$ i.e. $$\xi - P - Q + P\cap Q$$.

Now we have to solve for

$$A_1 + A_2 + A_3 + A_4 = 25\ \fbox*$$ when $$\fbox1\ A_1>12\ (A_1\geq13)$$, when $$\fbox2\ A_4>10\ (A_4\geq10)$$, and when $$\fbox3$$ both occurs.

From now, we think of those 4 "$$A$$"s as bins, and numbers as "balls".

For $$\fbox*$$

Using stars and bars we get $${28\choose3}=3276$$

Case $$\fbox1$$

Then it's easy to eliminate the restriction. We fill in box $$A_1$$ with 13 balls, and then we get an equation we need to solve for (with no restrictions!): $$A_1 + A_2 + A_3 + A_4 = 12$$

Using stars and bars the answer is $${15\choose3}=455$$

Case $$\fbox2$$

Similarly we get $$A_1 + A_2 + A_3 + A_4 = 14$$ and hence we get $${17\choose3}=680$$

Case $$\fbox3$$

Similarly we get $$A_1 + A_2 + A_3 + A_4 = 1$$ and hence we get $${4\choose3}=4$$

Hence we have $$3276-455-680+4=2145$$ which is what we want.$$\ \square$$

• I understand your process, but i'm a bit confused about why you can't make a substitution for A1 and A2 after you make A1≥13 and A≥11 Dec 6, 2018 at 16:16
• yeah I can make a substitution of $x=A_1-13$ and $y=A_4-11$ (the process is similar) Dec 7, 2018 at 11:42
• May I know where did you get this question (which topic are you studying) so I can give you a proof related to the topic? :) Dec 7, 2018 at 11:43
• It was from a past midterm so i'm not exactly sure. But i've found that using generating functions to solve these problems are easier. Dec 7, 2018 at 19:07
• Well you can use generating functions by expanding $(\sum_{k=0}^{12}x^k)(\sum_{k=0}^{25}x^k)^2(\sum_{k=0}^{10}x^k)$ (I suggest doing it with WolframAlpha) Dec 8, 2018 at 3:49

Sum for $$A_1$$ from $$0$$ to $$12$$ aand $$A_4$$ from $$0$$ to $$10$$ of $$25-A_1-A_4+1$$ where the last part is from stars and bars for the possible values of $$A_2,A_3.$$ [There's only one bar.] If I entered it right it's $$2145.$$

It's lucky that $$12+10=24\le 25$$ here. [edit-- lucky that $$12+10=22 \le 25.$$]

More explanation: You can have any of the possible values up to $$12$$ for $$A_1$$ and up to $$10$$ for $$A_4$$ (including $$0$$ for each.) These are distinct possibilities for assigning two of the four letters. Once $$A_1$$ and $$A_4$$ have been assigned, the overall sum of $$25$$ needs $$25-A_1-A_4$$ more to go, between $$A_2$$ and $$A_3$$, and this can be completed in $$[25-A_1-A_4+1]$$ ways, hence that is the value summed.

One more thing-- I just put this sum in a calculator to get the number, but it may be possible to do it formally using sum formulas applied to parts of the thing summed.

• yea that answer matches the answer key. But would it possible for you to make your solution more explicit? Dec 6, 2018 at 7:27
• @Steve Just added some explanation at end. Dec 6, 2018 at 7:55