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.

How would you go about calculating the number of permutations in ascending order.

Obviously if you had (a set of) 3 numbers you have $ 3! $ permutations:

(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1)

But only one of these is in ascending order (1,2,3).

Consider the lottery - picking 6 numbers from 49. Normally the order for this doesn't matter you just calculate '49 choose 6' but if the numbers have to be in ascending order how would you calculate that?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

In the same way: The number of (strictly) ascending sequences of $6$ numbers chosen from $49$ is $\binom{49}{6}$. For as you have pointed out, once the $6$ numbers have been chosen, there is precisely one way to arrange them in ascending order.

share|improve this answer
    
Does this remain unchanged even if we have repeating numbers among the 6 chosen ones? –  Phonon yesterday
    
It changes. If we are looking for non-descending (weakly ascending) sequences, for $i=1$ to $49$ let $x_i$ be the number of times we use $i$. Then we want the number of solutions of $x_1+\cdots+x_{49}=6$ in non-negative integers. By Stars and Bars (please see Wikipedia) this number is $\binom{49+6-1}{6-1}$ or equivalently $\binom{49+6-1}{49}$. –  André Nicolas yesterday
    
The sum is $6$ because we are choosing $6$ (not necessarily different) numbers. Another way of saying it is that we are counting the number of $6$-element multisets. (I am mentioning the word to help you search). –  André Nicolas yesterday
    
Yes sorry, I wrote that comment in haste, realized right after it what you'd meant. Thanks for the keywords, very helpful, +1 –  Phonon yesterday
    
You are welcome. –  André Nicolas yesterday

Hint: A combination is a permutation where order does not matter.

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.