Find all possible $\{ x_1,x_2,...x_n \}$ permutations of $ \{1,2,...,n \}$ so that when $1\le i \le n-2 $ then we have $x_i < x_{i+2}$ and when $1 \le i \le n-3$ then we have $x_i < x_{i+3}$ . Here $n \ge 4$.
Problem
Source:
Tags: factorial
10.01.2015 14:30
Find the number of permutations and combinations: n=6; r=4. Find the factorial of 6. 6! = 6*5*4*3*2*1 = 720 Find the factorial of 6-4. (6-4)! = 2! = 2 Divide 720 by 2. Permutation = 720/2 = 360 Calculate Permutations for any sample data here https://www.easycalculation.com/statistics/permutation-combination.php
11.01.2015 04:18
Here is the answer: The n-1th Fibonacci number. Refresh to see if I'm done. Here's what I have of the solution, but I'm still typing Okay. So our problem states that the nth number has to be less than the n+2th number and the n+3th number. So since $x_r < x_r_+_2 < x_r_+_4$, we can show that $x_r < x_r_+_m$, where m is the sum of any combination of 2s and 3s. By the Chicken McNugget Theorem, $m$ can be any integer $m \ge 2$. So $x_r$ must be greater than the first r-2 numbers in the sequence, and less than the last n-r-2 numbers in the sequence. So $x_r$ cannot be in the r+2th position, because it would need to be greater than r numbers on its left, but there are only r-1 positive integers less than r. For the same reason, $x_r$ cannot be in the r-2th position. So $x_r$ can only be in the r-1th position, the r+1th position, or the rth position. But now that we've proven that this is the only possibility that might work, we have to prove that it does work. This is relatively simple. If $x_r$ is in the r-1th position, every number on its left must be less than it, because otherwise a number that was at least $x_r_+_1$ would have had to move 3 spaces to be on its left. And since no greater number is on its left, every greater number must be on its right, and since a smaller number would have had to move at least 2 spaces to be 2 to the right of $x_r$, every number at least 2 to the left is less, and every number at least 2 to the right is greater. This method also works if you move the number to the right. Now it seems useful to start with the sequence 1,2,3...n, and change what we can from there. So let's try moving something over one space, let's say the number 7. How about we move it to the left. Now we have \[...5,7,-,8,9...\] and the 6 needs to be put somewhere. If we tried moving it to the left, in place of the 5, the 5 would have to go left, so that the 7 is still moving to the left, and all of the numbers would have to go left, and the 1 would have nowhere to go. So let's move 6 to the right, into the empty space. Now every space is filled, and we have \[...5,7,6,8,9...\] Go through those steps again. Since moving left and moving right are the only moves, you can see that there are no other ways to rearrange the numbers, except for the mirror image, where we move a number to the right (keeping in mind that the number must be at most 1 space away from its initial position, from what we proved earlier). So now we know that the only move we can make is switching two numbers that have not been switched (otherwise a number would be too far away from its initial spot). And we know that it will always work because of what we proved earlier. So to change the sequence, we have to swap 2 consecutive numbers. Let's put those numbers in a box, so that we don't switch a number twice. Now the question boils down to "How many ways can n numbers fit into boxes of 2 consecutive numbers, where every number is in at MOST 1 box?". f(2): If there are 2 numbers, there are 2 ways: they're in a box or they're not. f(3): If there are 3 numbers, there are 3 ways: put 1 and 2 in a box, 2 and 3 in a box, or neither. For the remaining cases, the only thing that changes is the possibility of putting the last 2 numbers in a box. So for these cases, there are two cases inside of it: whether or not the last numbers are in a box. Let's use 4 numbers now: you'll see why in a second... f(4): If the last numbers aren't in a box, we can ignore the last number and we have f(3) ways. If the last numbers are in a box, we have to ignore the last 2 numbers (since they're in a box and can't be bothered) and we have f(2) ways. Adding the last two terms gets the next one... sound familiar? It's the Fibonacci sequence! Now let's just put it where it goes, so we don't have it off by 1 Fibonacci number or something: f(2): 2 3rd Fibonacci number f(3): 3 4th Fibonacci number f(4): 5 (because of what we just showed) 5th Fibonacci number So it looks like f(n) is the n+1th Fibonacci number. And since we showed that f(n) is the answer to our problem, our answer is $\boxed{\mathcal{F}_n_+_1}$.
11.01.2015 13:41
Well, let's do away with the condition $n\geq 4$, and also allow $n\in \{1,2,3\}$. Denote by $p_n$ the number of such permutations. Then $\bullet$ for $n=1$ we get $\{1\}$, so $p_1=1$; $\bullet$ for $n=2$ we get $\{1,2\},\{2,1\}$, so $p_2=2$; $\bullet$ for $n=3$ we get $\{1,2,3\}, \{1,3,2\}, \{2,1,3\}$, so $p_3=3$. If a permutation counted by $p_n$ has as last element $n$, then its first $n-1$ elements are a permutation counted by $p_{n-1}$. If a permutation counted by $p_n$ has as last element $n-1$, then its second-to last element must be $n$, and then its first $n-2$ elements are a permutation counted by $p_{n-2}$. No permutation counted by $p_n$ has as last element some $n-k$ with $k\geq 2$, since then both $n-1$ and $n$ must occupy the second-to last position. Thus we obtain the recurrence relation $p_{n}=p_{n-1}+p_{n-2}$, which is the same with that for the Fibonacci numbers $F_n$; moreover, the starting values are Fibonacci numbers (just shifted by one), so $\boxed{p_n = F_{n+1}}$, and that works for any $n\geq 1$. As to actually finding all these permutations, the above shows precisely how they inductively are generated.
30.12.2016 16:36
This is an easy problem to use Recurrence Relations