4
$\begingroup$

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$?

$\endgroup$
2
  • 1
    $\begingroup$ What about $a+b+c+d = 35$? Represent it like $1+1+\dots + 1 + 1 = 35$ and you want to place brackets between 1-s. How manycombinations do you have? $\endgroup$
    – openspace
    Dec 12, 2017 at 2:38
  • $\begingroup$ After that idea you've got : $\binom{35+1}{3}$ and you should summarize your binoms. $\endgroup$
    – openspace
    Dec 12, 2017 at 2:41

3 Answers 3

5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ I don't understand how it works. Mind explaining? $\endgroup$
    – Archer
    Dec 30, 2017 at 19:55
  • $\begingroup$ @Abcd Sure! Suppose you've solving $a+b+c\leq5\forall a,b,c\in W$. In high school, we were taught solving equations of this type ($a+b+c$ $=$ $k$), but this is an inequality, what do we do now? Note that here you'll want to cover all the cases of equations, starting from $a+b+c=0$ and all the way till $a+b+c=5$. You know how to find the number of solutions to each equation. That is what I mean when I said "solve a general case for". Now to get the total count of solutions for our initial inequality, we'll sum up the individual solutions since they are all are distinct. $\endgroup$ Dec 31, 2017 at 2:46
  • $\begingroup$ @Abcd I hope this was helpful? $\endgroup$ Dec 31, 2017 at 2:48
  • $\begingroup$ Yes, thank you. $\endgroup$
    – Archer
    Dec 31, 2017 at 13:02
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Forgot to mention but if, for example, the solution 0+0+35+0 is the same as 35+0+0+0, then this method fails. Horribly $\endgroup$ Dec 12, 2017 at 4:11
2
$\begingroup$

$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.

  1. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.