0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Just remove $6!$. It's the same as the combinations of 6 elements out of 49. $\endgroup$
    – brick
    Oct 28, 2014 at 19:54
  • $\begingroup$ Thanks, I just figured it out. $\endgroup$ Oct 28, 2014 at 19:55

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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\;.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.