2

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?

Jake Burton
  • 65

2 Answers2

5

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.

André Nicolas
  • 507,029
  • Does this remain unchanged even if we have repeating numbers among the 6 chosen ones? – Ellie Aug 31 '15 at 16:34
  • 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 Aug 31 '15 at 16:45
  • 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 Aug 31 '15 at 17:01
  • You are welcome. – André Nicolas Aug 31 '15 at 17:11
3

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

Calvin Lin
  • 68,864