An algorithm to get the number of sorted combinations?

Question

Let's say that there are digits "n" from which we select "p" numbers (p is less than n) , so the selected "p" is sorted. The selected number can be repeated. How can we calculate the number of combinations that we can choose? For example, if we have a set of numbers, say {1,2,3,4,5,6} (n = 6), and we must select 3 numbers from the set (p = 3) that are sorted. Thus, 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 ?

---

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

Take this small example:

If the set is {1,2,3,4} (so n = 4) and we have to select 3 elements (p = 3), the number of ways we can select p elements (with replacement) will be 4*4*4=64 . Thus, the choice 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 samples, not everyone is sorted. In this example, {1,2,1} and {3,1,1} not sorted.

I want to get the number of sorted selections.
Thank you

Answer 1

I do not see how sorting affects the result. For each possible combination with repetitions, an appropriate sorted permutation will be created.

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

Here is a description of the explanation of the formula and more from tungsten .

Answer 2

@BiGYaN the answer here is correct, but there isn’t enough humor on the trip to get this result (even from the links provided), so I decided to add this -

• First, the OP should not take an analogy with the set, because by definition the set does not take into account the order and, in addition, contains unique elements.

• If we take the same example in which n = 6 or [1,2,3,4,5,6], now we need to get a sequence of length 3 such that -

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

We need sequences such as: {[1,1,1], [1,1,2], ...., [2,2,3], [2,2,4], ...}. Now for such sequences, scan the template on the left and try to reason if we want to increase the numbers or not.

For example: start from the left edge of d1 and reason, if you want to increase d1 right here or not, if you don’t decide, d1 will be “1”, and now go ahead and ask the same question immediately before d2, if you decide not to go up again , d2 is again "1".

You can select up to 5 times at any time, because the range is [1-6], and d1 should be 6, at least if you decide to increase it 5 times to get [6,6,6].

So, the problem is to choose a suitable place for 5 ups among

 [up up up up up d1 d2 d3] 

It can be [up d1 up up up d2 d3], which gives [2,6,6], or [d1 up up d2 up d3 up], which gives [1,4,5], or any combination like this.

So, in fact, the answer is C (5 up + 3 d's, 5 ups) or, in general

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

where, k things should be selected in sorted order from n things.

Answer 3

The number of ways to select elements k with a replacement from a set of elements n coincides with the number of ways to select elements k without a replacement from a set of elements n + k - 1 . The last value is the binomial coefficient n+k-1 choose k whose value is (n+k-1)!/(k! (n-1)!)

Unofficial Demonstration:

Suppose I have n blue boxes. I put them in a row (so they are sorted), and then take the red balls. I put red balls wherever I like in the line, except at the end, so the line should end with a blue square anyway. Now for each red ball, I select the next blue square. If two or more red balls are side by side, they both correspond to the same blue square.

Thus, each arrangement of red balls and blue boxes corresponds to a choice with the replacement of blue boxes, and each selection of blue boxes corresponds to a certain arrangement of red balls and blue boxes.

How many ways can I arrange red balls and blue boxes? My line should end with a blue frame, so I select it, and now I can arrange the remaining n-1 blue boxes and red balls in any way. Or, in other words, I can select k positions k + n-1 and apply red balls to these positions, filling the remaining positions with blue squares.