Which satisfy the system of inequalities below:

Question

For each nonnegative integer $n$, calculate the number of triples $(a, b, c)$ of nonnegative integers which satisfy the system of inequalities below:

$ \begin{cases} a + b \leq 2n \\ a + c \leq 2n \\ c + b \leq 2n \\ \end{cases}$

What I thought: We can solve this by plotting the inequalities with the bounds $x,y,z\geq0$ and getting that all such $(a,b,c)$ are lattice points bounded by the axis and $x+y+z=2n$.

Answer 1

The constraints define an $n$-fold dilation of the 3-dimensional polytope with vertices $(0,0,0)$, $(1,1,0)$, $(1,0,1)$, and $(0,1,1)$. The number of lattice points is hence a cubic Ehrhart polynomial. By inspection, the counts are $1, 11, 42, 106$, for $n=0,1,2,3$, respectively. The resulting polynomial is hence $$2n^3 + \frac{9n^2}{2} + \frac{7n}{2} + 1.$$

Answer 2

Consider the triples $ (a, b, c) $ of nonnegative integers that satisfy the following relationships: $$\begin{cases} \, a + b = x \\ a + c \leq 2n \\ b + c \leq 2n \end{cases} $$Let's divide the count of these triples into two steps. In the first we consider $ x = 2k $, while in the second we consider $ x = 2k + 1 $. Thus, the $ (a, b) $ pairs that satisfy $ a + b = 2k $ are $ (2k, 0), ..., (k, k),..., (0.2k) $.

For each of these pairs, $ c $ will have to obey $ c \leq 2n - M $ where $ M = \max (a, b) $, which gives us $ 2n - M + 1 $ solutions. Assuming that among the $ (a, b) $ pairs that satisfy the equation, the value of $ M $ ranges from $ k + 1 $ to $ 2k $ twice and then goes to $ k $, so the number of solutions for this case it will be: $$\left(2\sum_{M=k+1}^{2k} (2n-M+1)\right)+ 2n - k + 1 $$$$= -3k^2+4nk+2n+1 $$For the second case, be $ n = 2k + 1 $. The difference is that we will not have the extra solution in which the components of pair $ (a, b) $ are equal. Like this: $$\left(2 \sum_{M=k+1}^{2k+1}(2k+1-M+1)\right) $$$$= -3k^2+(4n-3)k+4n $$So just calculate the sum of all cases where $ a + b = 0 $, $ a + b = 1 $,… up to $ a + b = 2n $ and just get the sums for when $ 2k + 1 = 1, 3, 5, \dots, 2n-1 $ and sum with the sums for when $ 2k = 0, 2, 4, \dots, 2n $: $$\sum_{k=0}^n 3k^2+4nk+2n+1 + \sum_{k=0}^{n-1} -3k^2+(4n-3)k+4n $$$$= 2n^3 + \frac{9n^2}{2} + \frac{11n}{2} + 1 $$