# Number of combination of incremental numbers for a number

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.

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

• Nice explantion (+1) – Robert Z Feb 16 at 15:38

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

• 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. – Chung Seng Feb 17 at 16:07
• @ChungSeng You are welcome!! – Robert Z Feb 17 at 16:50