Special Sequence

For any non-negative integer $n$ , let $f(n)$ be the number of ways can the numbers from $1$ to $2n+1$ be arranged in a row such that )for all $1\leq k\leq n$ , the numbers in the $(2k)$ -th positions are each larger than both of their neighbours. Then $f(0)=1$ . We proceed to deduce a recurrence relation for $f(n)$ , then $f(3)$ is the desired number.

Suppose we already know $f(0), f(1), \cdots, f(n-1)$ , $n\geq 1$ . To arrange $1$ to $2n+1$ so that they satisfy the rule, consider the element $2n+1$ . This element is not less than any other elements, therefore it must be filled at the position $2k$ , for some $1\leq k\leq n$ .

For the rest of $2n$ elements, we need to choose $2k-1$ to fill the first $2k-1$ positions. There are $\binom{2n}{2k-1}$ number of ways to choose, and there are $f(k-1)$ number of ways to arrange them under the rule (Note: $2(k-1)+1=2k-1$ ). For the rest of $2n-(2k+1)=2(n-k)+1$ elements, there are $f(n-k)$ ways to arrange them under the rule. Therefore,

$f(n) = \sum_{k=1}^n \binom{2n}{2k-1}f(k-1)f(n-k).$

Thus $f(1)=2f(0)f(0)=2$ , $f(2)=4f(0)f(1)+4f(1)f(0)=16$ , $f(3)=6f(0)f(2)+20f(1)f(1)+6f(2)f(0)=272$ .

Clearly, $7$ must be in one of the "middle" positions (2nd, 4th, or 6th). Also, $2$ and $1$ can't be middle numbers.

This gives us a few possible arrangements for the middle numbers. Namely, these are $(7, 6, 5), (7, 6, 4), (7, 6, 3), (7, 5, 4),$ and $(7, 5, 3$ ). $(7, 4, 3)$ can't work because either $5$ or $6$ will be neighbors with $4$ or $3$ .

$(7, 6, 5)$ : The middle numbers can be arranged in any way and the other numbers can also be arranged in any way, so there are $3!\cdot4! = 144$ total ways.

$(7, 6, 4)$ : The only problem here is the $5$ , which can't be adjacent to the $4$ . If the $4$ is the 4th number, the $5$ can go either in slot $1$ or $7$ and the other $2$ middle numbers can be arranged in $2$ ways $\to 2\cdot2\cdot3! = 24$ ways. If the $4$ is in slot $2$ , there are again $2$ places for the $5$ to go and $2$ ways to arrange the other middle numbers with $3!$ ways of arranging the remaining numbers, again yielding $24$ arrangements. The case where $4$ is the 6th number is similar. $24 + 24 + 24 = 72$ arrangements.

$(7, 6, 3)$ : No matter where the $3$ is placed, there will be $2$ slots that must be taken up by the $4$ and the $5$ (for example: in $\_7\_6\_3\_$ , they need to go in slots $1$ and $3$ ). There are $3!$ ways to arrange the middle numbers and $2$ ways to arrange the remaining numbers, yielding $24$ total arrangements.

$(7, 5, 4)$ : The $6$ must go by the $7$ and touch nothing else, which means that there are $2$ ways to place the $6$ and the $7$ (slots $1$ and $2$ or $6$ and $7$ ). The remaining middle numbers can be arranged in $2$ ways and the other numbers can be placed in $3!$ ways, yielding $2\cdot2\cdot3! = 24$ arrangements.

$(7, 5, 3)$ : Again, the $6$ must be by the $7$ , which means there are $2$ ways to place these numbers. The $4$ must be next to the $5$ and away from the $3$ , which means that there is $1$ place to put it after placing the $5$ in either one of the $2$ open middle positions. The remaining numbers can be arranged in $2$ ways. The total is $2\cdot2\cdot2 = 8$ arrangements.

The total is then $144 + 72 + 24 + 24 + 8 = 272$ arrangements.

Since the numbers in the 2nd, 4th and 6th positions are each larger than both of the neighbors, the smallest number we can place in any of these three positions is 3, next to which only 1 and 2 can be placed. And 7 must be in one of the three positions.

If a 3 is already in place, 4 cannot be placed in any of the 2nd, 4th or 6th positions since all numbers smaller than 4 (i.e. 1,2,3) have been used once.

Hence we consider the situation where 3,5,7 are put in the three positions. 7 must take either the 2nd or the 6th position because 6 cannot be placed next to any other number in this case. 1 and 2 can switch positions as they are definitely smaller than the rest. As such, there are 2 * 4=8 ways of arranging the numbers in this situation.

Next we consider 3,6,7 being in the three positions. Similarly, 1 and 2 , 4 and 5 can both switch positions. Plus 7 can be place in the middle this time round. Thus there are 2 * 2 * 6=24 ways in this case.

When numbers 4,5,7 are put in the three places. It is again similar to the first scenario (7 cannot be in the middle). So 6 must be in either 1st or 7th position. The other three numbers (1,2,3) can be put in the three positions left in any order. So the number of ways is given by: 1 * 2 * 3 * 4=24

When 4,6,7 are placed in the three positions, the only restriction is that 5 cannot be placed next to 4 so there are only 2 places available. The other three numbers can be placed in any position. So there are 2 * 3 * 2 * 1 * 6=72 ways of arranging it.

Finally when 5,6,7 are placed in the three positions. Each of the number 1,2,3,4 can be placed in any position. So there are 1 * 2 * 3 * 4 * 6=144 ways of arranging it in this case.

Adding them up, we get 144+72+24+24+8=272 ways in total.

We will count this recursively. We first observe that the choice of numbers does not affect the number of arrangements (as long as the numbers are distinct). Let $A_n$ represent the number of ways to arrange $n$ distinct integers such that the numbers in even positions are larger than their neighbours.

When arranging 7 integers, the largest one must go in position 2, 4, or 6. If it goes in position 2, there are $\binom{6}{1} = 6$ choices for the number in position 1 and $A_5$ ways to arrange the remaining numbers. If the 7 is in position 6 we have an equal number of possibilities. When the 7 is in position 4, there are $\binom{6}{3} = 20$ possibilities for which 3 numbers are in the first 3 positions, and $A_3$ ways to arrange them. So $A_7 = 20 (A_3)^2 + 2 \times 6 A_5.$

We calculate $A_5$ in a similar manner. The 5 must be in the 2nd or 4th position. There are $\binom{4}{1} = 4$ ways to choose the number that is in the side with 1, and $A_3$ ways to arrange the other 3 numbers, so $A_5 = 2 \times 4 \times A_3,$ and $A_7 = 20 (A_3)^2 + 96 A_3.$

We see that $A_3 = 2$ since the largest number is in the middle and the other elements can be arrange in 2 ways. This gives us that $A_7 = 20 (2)^2 + 96 \times 2 = 272$ .

7 must be at b or d or f if 7 is at d, then b=max(a,b,c),f=max(e,f,g), there are 6!/3/3=80 ways if 7 is at b, WLOG assume "cdefg" are {1,2,3,4,5}. 5 must be at d or f, suppose 5 is at d, then f must be 4 or 3. if f=4, there are 3! ways; if f=3, then c=4, {e,g}={2,1}, there are 2 ways. so if 7 is at b, there are 6 (2 (3!+2))=96 ways. if 7 is at f, there are 96 ways. altogether there are 96+96+80=272 ways

Observe that there are 8 positions possible for 6 and 7. The first 4 are:

6 7 _ _ _ _ _

_ 7 _ 6 _ _ _

_7 _ _ _ 6 _

_ 6 _ 7 _ _ _

and the other 4 can be obtained by reflection about the middle number.

We denote the above as cases 1,2,3,4. Notice that the number of possibilities in case 2 and 4 are equal.

Case 1: we either have

6 7 4 5 _ _ _ (2 possibilities)

6 7 _ 5 _ 4 _ (6 possibilities)

6 7 _ _ _ 5 4 (2 possibilities)

6 7 _ 4 _ 5 _ (6 possibilities)

for a grand total of 16.

In case 2:

5 7 _ 6 _ _ _ (2+6 possibilities depending on where 4 is placed)

_ 7 5 6 _ _ _ (again, 2+6)

_ 7 _ 6 _ 5 _ (24)

giving a total of 40

In case 3:

_7 _ 5 _ 6 _ (24)

5 7 _ _ _ 6 _ (2+6)

_ 7 _ _ _ 6 5 (2+6)

Giving 40 as well.

Thus the answer is just 2(16+40+40+40) = 2(136) = 272

Let us denote the numbers in the 1st, 2nd, 3rd, 4th, 5th, 6th and 7th as A, B, C, D, E, F and G. </p>

Case 1: {6,7} in {B,D or F} </p>

Note that there are 6 possible permutations for ordering {6,7} in {B,D or F}. WLOG, let 6 be at B, 7 be at D. If 5 is at F, we have $4!=24$ ways. If 4 is at F, we have $2*3!=12$ ways. If 3 is at F, we have $2*2!=4$ ways. Hence, total ways $=40*6=240$ . </p>

Case 2: {6} not in {B,D or F} </p>

Note that 7 cannot be at D, and thus there are 2 ways. WLOG, let 7 be at F. Thus, 6 is at G. Then, 5 is at B or D. WLOG let 5 be at B. If 4 is at D, there are $3!=6$ ways. If 4 is at A, there are $2!=2$ ways. Hence, total ways $=2*2*(6+2)=32$ . </p>

Therefore, amount of ways is 272 .

To find the total type of digit arrangment for the 2nd,4th and 6th position , we have (7-2)!/(2!)(2!)(3!) by using the elimination method. Firstly and abviosly, the digit "1" and "2" cannot fulfill the problem's request. So we have (7-2)!. The digit "7" must be in the 2nd,4th and 6th position and we also.know that "3" and "4" cannot be used at the same time. Hence,we get (2!)(2!)(3!).

Now,we can carry on by case-by-case analysis . The first case is 3,5 and 7. We have 2!(2!)(2!)=8. This is because the digit 7 must be put at the second or sixth position . And the number around digit 3 can change position with each other. And the digit 3 and 5 can exchange their postion. But of course with their neighbours. Case 2 is the set of number 3,6,7. By using the same method of elimination, we can have 3!×2×2=24. Case 3 is the set of 4,5,7. We also can have 3!×2×2=24. Case 4 is the set of 4,6,7. We can have 3!×3!×2=72. Case 5, the last case, we have just 4!×3!=144.

Now, total up of the numbers of arrangment , we have 8+24+24+72+144=272.

The problem had been solved . By GP.