Combinatorics and inequalities

Question

I've ran across a few combinatoric problems with inequalities in them and I'm curious to know just how to do them or if they aren't different from combinatorics with the equality symbol.

For example: How many solutions are there for non-negative integers $a, b, c$, and $d$ such that $a + b + c + d \leq 35$?

Answer 1

Solve a general case for:

$$m\le a+b+c+d=n\leq k$$

in terms of $n$, where $m$ and $k$ are the minimum and maximum values of the expression.

Then your answer is: $$\sum_{n=m}^{k}<\text{number of solutions of a+b+c+d=n}>$$

Can you understand why this works?

Answer 2

This is the only method I was taught for solving this kind of problems, and it's, to be quite honest, time consuming. But it works (I'm convinced it does, if it doesn't please tell me because my finals on this are coming up) so here it is:

I'm going to solve the particular case and not the general case

We can think of the problem as a stars and bars problem. We want all the solutions with no stars + the ones with one star + two stars... all the way up to 35 stars. That is, we want to compute $$\sum_{i=0}^{35}{i+3 \choose i} = \sum_{i=0}^{35} \frac{(i^3 +6i^2+11i+6)}{6} = \frac 16 \sum_{i=0}^{35} (i^3 +6i^2+11i+6) $$ (we get this polynomial by computing ${i+3 \choose i} $)

Now is where my method is quite unefficient as I'm sure there must be an easier way of solving this. Here's mine:

Let $ S_n = \sum_{i=0}^{n}(i^3 +6i^2+11i+6)$

Then $S_n - S_{n-1} = (n^3 +6n^2+11n+6) \cdot 1^n$ (which is the $n$th term of the sum)

This is a recurrence relation of first order that has 1 as a root for its characteristic polynomial $n-1$. So the solution for the homogenous equation is $E \cdot 1^n$ where E is a constant number

By proposing a solution of the type $n^sq(n)1^n$ where s is the multiplicity of $1$ as a root in the characteristic polynomial and $q(n)$ is a polynomial of the same degree as the one in the recurrence relation. We propose a solution of the type $S_n = An^4 + Bn^3 + Cn^2 + Dn $ and replace in the recurrence relation to get values for A,B,C,D

After getting those values we get the general solution $\frac {n^4}{4} + \frac{5n^3}{2} + \frac{35n^2}{4} + \frac{25n}{2} + E $ where E is a constant. We equal this to $S_0 $ to get a value for E ($E=6)$ since $S_0 = 6$

So we have $$S_n = \frac {n^4}{4} + \frac{5n^3}{2} + \frac{35n^2}{4} + \frac{25n}{2} + 6 =\frac {n^4 + 10n^3 + 35n^2 + 50n +24}{4}$$

So now we can compute $$\sum_{i=0}^{35}{i+3 \choose i} = \frac {S_{35}}{6} = 82251$$ Polynomials are easily computable but I must admit that this method is really long. But it's just another way of solving this problem

Answer 3

$a+b+c+d\le 35, a,b,c,d \in Z^+_0$ Suppose $e = 35-a-b-c-d, \Rightarrow e \in Z^+_0$ $a+b+c+d+e = 35, a,b,c,d,e \in Z^+_0$.

For each value of e, $a+b+c+d$ has a unique value and each solution of new equation gives us a unique solution of $a+b+c+d\le 35, a,b,c,d \in Z^+_0$

So, we thus have ${39\choose 4}$ = 82251 required solutions.

Reference

You can also adopt the alternative method: $a+b+c+d = n, a,b,c,d\in Z^+_0, 0\le n \le 35$ to get ${3 \choose 3} + {4 \choose 3} \cdots {38 \choose 3} = {39\choose 4}$ by the Hockey Stick Identity. But this method is not only more time consuming but also difficult to understand.

1. You can prove that $x_1 + x_2 + \cdots + x_r = n$ has ${n+r-1 \choose r-1}$ solutions, either by induction or by the Combinatorial method.

Suppose you have n distinct objects and r-1 separators. Your objective is to separate these n objects into r parts using r-1 separators. You may have empty sets. Let $x_i$ be the number of objects in the $i^{th}$ partition. Then $0\le x_i$ and $x_1 + x_2 +\cdots + x_r = n$. Hence, each way of making these partitions corresponds to an arrangement of the r-1 separators and n distinct objects, exactly equal to ${n+r-1 \choose r-1}$. Thus, $x_1 + x_2 +\cdots + x_r = n, x_i \in Z^+_0$ has ${n+r-1 \choose r-1}$ solutions.

2. Analogously, each solution of $x_1 + x_2 +\cdots + x_r = n, x_i \in Z^+$ corresponds to r non-empty partitions of n distinct objects. For this, we need to place the separators between any two objects, thereby making sure, no 2 separators are placed next to each other and no partition is empty. This can be done in ${n-1 \choose r-1}$ as there are n-1 placed between these n aligned objects.

You may also want to note, that $x_1 + x_2 +\cdots + x_r = n, x_i \in Z^+$ may be replaced by $(y_1+1) + (y_2+1) + \cdots + (y_r+1) = n$ where $y_i = x_i -1, \Rightarrow y_i\in Z^+_0$. Thereby yielding $y_1 + y_2 + \cdots + y_r = n-r, y_i\in Z^+_0$ which clearly has ${(n-r)+r-1 \choose r-1}$ i.e., ${n-1 \choose r-1}$ solutions. This is just a cross check between the two derived identities.