Algorithm to get the number of sorted combinations?

Question

Say there are "n" numbers from which we select "p" numbers (p less than n) such that the selected "p" numbers are sorted. A selected number can be repeated. How can we calculate the number of combinations we can select? For example if we have a set of numbers say {1,2,3,4,5,6} (n=6) and we are to select 3 numbers from the set (p=3) which are sorted. So we can have {1,2,3}, {1,1,2}, {2,3,6}, {4,5,5}, {5,5,5} ........ Since all of these combinations are sorted they are valid. How can we find the number of such sorted combinations we can get?

---

What I mean from the word sorted, is that when we select p elements from a set of numbers of n elements, the selected p elements should be sorted.

Take this small example:

If the set is {1,2,3,4} (so n = 4) and we are to select 3 elements (p = 3), the number of ways we can select p elements (with replacement) will be 4*4*4=64. So the selections will have {1,1,1},{1,1,2},{1,1,3}{1,1,4},{1,2,1}.....{3,1,1}...{4,4,4}. But in these selections, not all are sorted. In this example, {1,2,1} and {3,1,1} are not sorted.

I want to get the number of sorted selections.
Thanks.

Answer 1

I fail to see how the sorting affects the result. For each possible combination with repetitions, there will be a corresponding sorted permutation.

Hence the question boils down to number of combinations of n elements taken p at a time with replacement. That is the straight forward formula, (n-1+p)C(p) = factorial(n-1+p) / (factorial(p) * factorial(n-1) )

Here is an explanation of the formula, and another one from wolfram.

Answer 2

@BiGYaN's answer here, is correct but lacks the humor in journey to get this result (even on the links provided), so I decided to add this -

1. Firstly OP should not take the analogy of set, because by definition the set doesn't consider the order, and moreover contains unique items.

2. If we take the same example in question where n = 6 or [1,2,3,4,5,6], now we're to get the sequence of length 3, such that -

   pattern = d1<=d2<=d3 (d is for digit).

We need sequences such as: {[1,1,1], [1,1,2], .... , [2,2,3], [2,2,4],...}. Now, for such a sequences scan the pattern from left and try to reason if we want to increment digits or not.

For ex: start from just left of d1 and reason if you want to increment d1 right here or not, if you decide not - d1 would be '1' and now moving ahead ask the same question just before d2, if you again decide not to up, d2 is '1' again.

You can choose to up 5 times anytime because range is [1-6] and d1 should be 6 at least, if you decide to raise it 5 times to get [6,6,6].

So, the problem becomes to select proper place for 5 ups among

[up up up up up d1 d2 d3]

This could be [up d1 up up up up d2 d3] which yields [2,6,6], or [d1 up up up d2 up d3 up] which yields [1,4,5] or any combination like this.

So, actually the answer is - C(5 up's + 3 d's, 5 up's) or, more generally

C(n-1 up's + k digits, n-1 up's) or C(n-1+k, n-1)

where, k things are to be selected in sorted order out of n things.

Answer 3

The number of ways you can choose k elements with replacement from a set of n elements is the same as the number of ways you can choose k elements without replacement from a set of n + k - 1 elements. The latter value is the binomial coefficient n+k-1 choose k whose value is (n+k-1)!/(k! (n-1)!)

Informal demonstration:

Suppose I have n blue boxes. I put them in a row (so they're sorted), and then take k red balls. I put the red balls anywhere I like in the row except at the end, so the row must still end with a blue box. Now, for each red ball I select the following blue box. If two or more red balls are side-by-side, they both correspond to the same blue box.

So every arrangement of red balls and blue boxes corresponds to some selection with replacement of blue boxes, and every selection of blue boxes corresponds to some arrangement of red balls and blue boxes.

How many ways can I arrange the red balls and blue boxes? My row must end with a blue box, so I take that one away, and now I can arrange the remaining n-1 blue boxes and k red balls in any way I choose. Or, in otherwords, I can choose k of the k + n-1 positions and put red balls at those positions, filling in the remaining positions with the blue boxes.