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$

2 Answers 2

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$
1
  • 2
    $\begingroup$ Nice explantion (+1) $\endgroup$
    – Robert Z
    Feb 16, 2020 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$
2
  • $\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, 2020 at 16:07
  • $\begingroup$ @ChungSeng You are welcome!! $\endgroup$
    – Robert Z
    Feb 17, 2020 at 16:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .