Counting non-decreasing sequences of k positive integers up to n

[Mayan 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.

 

[chiro]

Hey Chan Pok Fung.

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

 

[Mayan 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. :(

 

[Mayan Fung]

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

 

[haruspex]

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

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

 

[Mayan 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.

 

[haruspex]

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.

Right, so which applies here?

 

[Mayan 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 :(

 

[haruspex]

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 :(

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

 

[Mayan Fung]

I still can't get a clue on that

 

[haruspex]

I still can't get a clue on that

Consider an arbitrary sequence of positive integers x₁ to x_n such that x_i<=x_i+1.
Now add 1 to the second term, 2 to the third term and so on to produce the sequence y_i satisfying y_i<y_i+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 x_n<=N, what is the constraint for the y sequences?

 

[Mayan Fung]

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