# B Combinatorics problem

1. Nov 29, 2016

### Chan Pok Fung

If I have k positive integers, x1, x2, ..., xk and n(also an integer) where
$$x_1≤x_2≤x_3≤...≤x_k≤n$$
How can I get the total combinations? I am trying to find the distinct components of a symmetric tensor. But I stuck here.

2. Nov 29, 2016

### chiro

Hey Chan Pok Fung.

Hint - Try fixing a case for n = 2 and then do an inductive argument.

3. Nov 29, 2016

### Chan Pok Fung

I tried that but I couldn't get a simple mathematical form.
$$n=1, \#= 1$$
$$n=2, \#= 1+k$$
$$n=3, \#= \sum_{i=0}^k (1+k-i)= \frac{(k+1)(k+2)}{2}$$
$$n=4, \#= \sum_{i=0}^k \frac{(k+1)(k+2)}{2} = .....$$
I can't even get the n=4 term :( and I don't how how to generalize it. :(

4. Nov 29, 2016

### Chan Pok Fung

I also tried starting from k = 1, and I still failed...

5. Nov 30, 2016

### haruspex

I hope this is not homework.
How many ways are there of choosing k out of n items?

6. Nov 30, 2016

### Chan Pok Fung

um... I have this doubt after doing my homework. Choosing k out of n items is nCk if they don't repeat. If they can repeat, then it is n^k.

7. Nov 30, 2016

### haruspex

Right, so which applies here?

8. Nov 30, 2016

### Chan Pok Fung

should be n^k and I need to find some ways to minus those counted repeatedly. For example, in the case of three objects, 123, 132, 213, 231, 312, 321 are the same. 122, 212, 221 are the same. But combination with "abc" forms are counted as 6 times, "abb" forms are counted as 3 times. Things even become more complicated for larger n and k. That's why I got stuck :(

Last edited: Nov 30, 2016
9. Nov 30, 2016

### haruspex

No, there's an easier way.
The trick is to map it into the distinct values case. Consider the sequence yi=xi+i.

10. Dec 1, 2016

### Chan Pok Fung

I still can't get a clue on that

11. Dec 2, 2016

### haruspex

Consider an arbitrary sequence of positive integers x1 to xn such that xi<=xi+1.
Now add 1 to the second term, 2 to the third term and so on to produce the sequence yi satisfying yi<yi+1.
It is clear that each x sequence produces a y sequence in a deteministic manner.
We can reverse the process. Given a y sequence, i.e. strictly increasing, we can subtract 1 from the second term, 2 from the third etc. to produce an x sequence. Again, a given y sequence can only produce one possible x sequence.
We have established a bijection, or 1 to 1 correspondence, whatever terminology you are familiar with. Thus there is the same number of x sequences as there is of y sequences.
If the set of x sequences was constrained by xn<=N, what is the constraint for the y sequences?

12. Dec 2, 2016

### Chan Pok Fung

That sounds to be a clever method! I will try it after finishing my work on hand! Thanks!