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

Question

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

d_e · Answer 1 · 2015-06-13T16:34:05.137

1

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

edited Jun 13 '15 at 16:34

answered Jun 13 '15 at 16:14

d_e

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

score 1 · Answer 2 · answered Jun 13 '15 at 16:18

1

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.

answered Jun 13 '15 at 16:18

wythagoras

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

2 Answers2