Solve the following problem in three ways:
a) as a principle of inclusion-exclusion problem,
b) using generating functions,
c) using the rule of sums.
How many compositions of $2n+1$ with three parts have no part exceeding the sum of the other two? (Thus we are concerned with compositions $y_1+y_2+y_3=2n+1$ with $y_i\leq y_j+y_k$ whenever $\{i,j,k\}=\{1,2,3\}$).
So I'm a little confused as to how to start any of these problems
For part a) I have the properties
$p_1: y_1>y_2+y_3$
$p_2: y_2>y_1+y_3$
$p_3: y_3>y_1+y_2$
And we want $e(\emptyset)=a(\emptyset)-a(p_1)-a(p_2)-a(p_3)$
Could anyone help me get on the right track? Thank you!
A particular solution of the equation in the nonnegative integers $$y_1 + y_2 + y_3 = 2n + 1 \tag{1}$$ corresponds to the placement of two addition signs in a row of $2n + 1$ ones. For instance, if $n = 5$, $$1 1 1 1 + + 1 1 1 1 1 1 1$$ corresponds to the solution $y_1 = 4$, $y_2 = 0$, $y_3 = 7$. The number of solutions of equation 1 in the nonnegative integers is equal to the number of ways we can place two addition signs in a row of $2n + 1$ ones, which is $$\binom{2n + 1 + 3 - 1}{3 - 1} = \binom{2n + 3}{2}$$ since we must choose which two of the $2n + 3$ positions required for $2n + 1$ ones and two addition signs will be filled with addition signs.
From these, we must subtract those solutions in which one of the numbers exceeds the sum of the other two, which occurs if some $y_i \geq n + 1$.
Suppose that $y_1 \geq n + 1$. Then $y_1' = y_1 - (n + 1)$ is a nonnegative integer. Substituting $y_1' + (n + 1)$ for $y_1$ in equation 1 yields \begin{align*} y_1' + (n + 1) + y_2 + y_3 & = 2n + 1\\ y_1' + y_2 + y_3 & = n \end{align*} which is an equation in the nonnegative integers with $$\binom{n + 3 - 1}{3 - 1} = \binom{n + 2}{2}$$ solutions.
By symmetry, the number of solutions of equation 1 in which $y_1 > y_2 + y_3$ is equal to the number of solutions in which $y_2 > y_1 + y_3$ and the number of solutions in which $y_3 > y_1 + y_2$. Hence, $$\binom{3}{1}\binom{n + 2}{2}$$ solutions violate the restriction that no part exceeds the sum of the other two.
Hence, the number of admissible solutions is $$\binom{2n + 3}{2} - \binom{3}{1}\binom{n + 2}{2}$$
For the generating function, since none of the parts can exceed $n$, we want to find the coefficient of $x^{2n + 1}$ in the expansion of $$(1 + x + x^2 + \ldots + x^n)^3$$