Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Lets assume that we have a element, which can have value from 1 till n. (let's set it on 20 to make it easier) And we have the Set, that consists of object, which consists of three elements $\langle e_1, e_2, e_3 \rangle$.

We have also one rule regarding to objects in the set: $e_1 \geq e_2 \geq e_3$ - example of good objects: $\langle n, n, n\rangle$, $\langle n, n-1, n-1\rangle$, $\langle 20, 19, 18\rangle$, $\langle 3, 2, 1\rangle$, $\langle 3, 3, 3\rangle$, $\langle 3, 2, 2\rangle$.
- example of bad objects: $\langle n, n+1, n\rangle$, $\langle 2, 3, 2\rangle$, $\langle 3, 2, 4\rangle$.

Now the question: How to count the amount of all good objects, which pass to this Set (they don't violate the rule ) ? Can you give me any hints?

I can solve this with brute force method. But probably there is a short way.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

If the first number is $k$, and the second number is $j$, where $j \leq k$ then the last number has $j$ choices.

So the number of favorable cases is $$\sum_{k=1}^n \sum_{j=1}^k j = \sum_{k=1}^n \frac{k(k+1)}{2} = \frac{n(n+1)(n+2)}{6}$$

In general, if you have elements from $1$ to $n$ and want to choose an $m$ element set with the ordering you want the answer is $$\binom{n+m-1}{m}$$ which can be seen by induction on $m$ or by a combinatorial argument as proved here.

share|improve this answer

There are many ways. One is first to ask how many 2-element things there are. If $e_1=i$, there are $n+1-i$ of them. So the total number of 2-element things is $$\sum_{i=1}^n(n+1-i)=n^2+n-\frac{n(n+1)}{2}=\frac{n(n+1)}{2}$$
Then the number of 3-element things is $$\sum_{i=1}^n\frac{i(i+1)}{2}$$

share|improve this answer

The simplest way is to simply pick three objects from your set allowing repetitions. Then you'll just list them in nonincreasing order.

This is just a count of combinations with repetitions. You have $n$ possibilities, and you want to pick $r$ elements, then the number of ways of doing it is $\binom{n+r-1}{r}$. See for example Wikipedia's page on the stars and bars problem for a proof.

In your example, $n=20$, $r=3$, so you would want $$\binom{20+3-1}{3} = \binom{22}{3} = 1540.$$

This agrees with Ross's answer: $$\sum_{i=1}^{20}\frac{i(i+1)}{2} = 1540.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.