Permuation and Combination: Selecting n numbers such that such that sum is less than m

The value of n can be 0,1,2,3....and so on

For example

If we have to select 2 numbers such that the sum of all them can be less than 2

Manually the combinations can be (0,0), (0,1), (1,0), (2,0), (0,2) and (1,1) So there are 6 ways

How do we solve it using permutation and combination for n numbers and sum m. I can't seem to understand this problem.

Thank you

The number of pairs less or equal to $n$ is $$\frac{(n+1)(n+2)}{2}$$

We see the following

• If the first number is $n$, there is one possibility for the second number.

• If the first number is $n-1$, there are two possibilities for the
second number.

• ...

• If the first number is $0$, there are $n+1$ possibilities for the
second number.

Summing gives the $n+1$th triangle number, or the formula I gave.

• Thanks :) I understood. But instead of 2 numbers if I want to choose 3 what will it be like? Thanks! – Sanchit Kapoor Jun 13 '15 at 17:45

I think the answer is:

$$a_0 = 1$$ $$a_{n+1} = a_n + (n+2)$$

each number contains all the previous + $(n+1)$ new ways. so $a_{n}-a_{n-1} = n+1$, and $a_{n+1}-a_{n} = n+2$

you can solve it to $a_n = \dfrac{(n+2)(n+1)}{2}$

• Thanks :) But what if I want to choose 3 numbers? – Sanchit Kapoor Jun 13 '15 at 18:48