How many $6$-lentgh increasing sequence are there from $1$ to $49$?

Question

I have to figure out a way to count how many sequences are there s.t:

1. My alphabet is $1$ up to $49$.
2. Each number that is chosen, is chosen only once.
3. The sequence is $6$ digits long.

4. The sequence is in increasing order.

   e.g that is a valid sequence: $(1, 2, 40, 42, 43, 49)$

   and this is not: $(1, 2, 40, 25, 25, 12)$

I know that for the first 3 rules the answer is: $\binom{49}{6}\cdot 6!$

How do I deal with the fourth?

Answer 1

I think I got it, I would say it's $\binom{49}{6}$, because once you chose your 6 numbers, there is only 1 way to order them.

Answer 2

You’ve found the nicest and easiest solution. Just for fun, here’s another (much less efficient!) approach showing how to convert this problem into a more familiar one.

Let the sequence be $\langle a_1,a_2,a_3,a_4,a_5,a_6\rangle$. Let $x_1=a_1$, let $x_k=a_k-a_{k-1}$ for $k=2,\ldots,6$, and let $x_7=49-a_6$. Then you want the number of integer solutions to

$$x_1+x_2+x_3+x_4+x_5+x_6+x_7=49$$

subject to the conditions $1\le x_k$ for $k=1,\ldots,6$ and $0\le x_7$. Let $y_k=x_k-1$ for $k=1,\ldots,6$ and let $y_7=x_7$, and the problem becomes counting the solutions in non-negative integers to

$$y_1+y_2+y_3+y_4+y_5+y_6+y_7=43\;.$$

This is a standard stars and bars problem whose solution is

$$\binom{43+7-1}{7-1}=\binom{49}6\;.$$