Lucky number 13?

Probability Level 4

How many ways can you arrange the integers 1 through 13 ( $a_1$ through $a_{13}$ ) such that $a_{n+2} > a_n$ for $n = 1 \to 11$ ?

The answer is 1716.

1 solution

Geoff Pilling
Sep 24, 2018

Essentially, this problem boils down to splitting the numbers into two groups, odd and even $n$ . So, we need to choose 6 numbers for even $n$ and 7 numbers for the odd $n$ , then we sort them and shuffle the two groups into their corresponding place in the original list.

So, the number of ways is:

$\binom{13}{6} = \boxed{1716}$

This solution is only correct if n>0 (or n>=1). If n>1, then the first digit doesn't has to be smaller, than the third, so we can choose the first digit out of 7, and put the rest of the "odd" (and "even") digits into ascending orders.

Hence, the answer of the question in its current form shoul be 7 × 1716 = 12012

Zee Ell - 2 years, 8 months ago

Ooops, good point... I've updated the question wording.

Geoff Pilling - 2 years, 8 months ago

Potential follow-up: Same scenario but with $a_{n+3} \gt a_{n}$ for $n = 1 \to 10$ . I get an answer of $\dfrac{13!}{5!4!4!} = 90090$ .

P.S.. I normally understand "digits" as the integers 0 to 9, so it might be an idea to change "digits" to "integers".

Brian Charlesworth - 2 years, 8 months ago

Good catch with the digits... I've changed it to integers. The follow up question is interesting... I'm not sure if you mixed the answer up with my question, tho, as it appears that would be the answer for n going from 1 to 13.

Geoff Pilling - 2 years, 8 months ago

Well, I figured that there would be three subsequences, namely $(a_{1}, a_{4}, a_{7}, a_{10}, a_{13}), (a_{2}, a_{5}, a_{8}, a_{11})$ and $(a_{3}, a_{6}, a_{9}, a_{12})$ . The first subsequence can be filled in $\dbinom{13}{5}$ ways, then the second in $\dbinom{8}{4}$ ways, locking in the final subsequence. This results in $\dbinom{13}{8} \dbinom{8}{4} = \dfrac{13!}{5!4!4!}$ arrangements.

Brian Charlesworth - 2 years, 8 months ago

@Brian Charlesworth – Looks reasonable!

Geoff Pilling - 2 years, 8 months ago

@Geoff Pilling – And that appears to hint at the general solution for $n$ numbers where $a_{m+i} > a_m$

Geoff Pilling - 2 years, 8 months ago

Lucky number 13?

The answer is 1716.

1 solution

0 pending reports