2
$\begingroup$

I had been trying to calculate the number of possible combinations for:

$x_1+x_2+x_3=20$ where $x_i > x_{i-1}$ and $x_i$ are positive whole numbers including zeros.

I had managed to solve a simpler version of this (with only two variables) with star and bar method. But I am having issue with anything with more than two variables.

$x_1 + x_2 = 20$

I know that $x_2 \gt x_1$ therefore $x_2 \gt 20 - x_2$ which simplifies to $x_2 - 10 \gt 0$ or $x_2 - 11 \ge 0$

Let $x'_2 = x_2-11$

The new equation will be $x_1 + x'_2 = 9$

This can be solved using star and bar method which gives me 9 combinations.

I was not able to apply the same technique to the equation on top.

It'll be great if someone and hint me in the right direction. I am sorry if I format the equation wrongly. Math is not my expertise.

$\endgroup$
3
$\begingroup$

Start with Stars and Bars to see that there are $\binom {22}2=231$ ways to do it if you ignore the inequality.

Naively, we'd like to divide by $3!=6$ to put them in increasing order, but this won't work because you might have ties between the $x_i$. So let's deal with the ties.

It is impossible for all three to be equal, since $20$ is not divisible by $3$.

If $x_1=x_2$ there are $11$ possible triples, since $x_1$ can be anything from $0$ to $10$ and $x_1$ determines the triple. Similarly, there are $11$ possible triples with $x_1=x_3$ and another $11$ with $x_2=x_3$. Thus $33$ "tied" triples all in all.

It follows that there are $231-33=198$ triples with no ties.

Now the naive idea works and we can divide by $6$ to put the remaining triples in order. thus the answer is $$\boxed {\frac {198}6=33}$$

$\endgroup$
  • 2
    $\begingroup$ Nice explantion (+1) $\endgroup$ – Robert Z Feb 16 at 15:38
1
$\begingroup$

You have to compute the so-called number of partitions of n into 3 distinct parts, where 0 is allowed as a part. You may take a look at OEIS-A001399 for more references. There is a nice closed formula: $$\text{round}( n^2/12 ).$$ Therefore for $n=20$ we get $\text{round}(20^2/12 )=\text{round}(100/3)=33.$

$\endgroup$
  • $\begingroup$ Although the other answer was easier to understand, and aided with my initial research. Your answer actually led me to solution of my actual problem. What I actually needed was number of partitions of n into distinct parts. Took some research to figure out what partition was, and it paid off. I really want to thank you for that. $\endgroup$ – Chung Seng Feb 17 at 16:07
  • $\begingroup$ @ChungSeng You are welcome!! $\endgroup$ – Robert Z Feb 17 at 16:50

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.