Consider a fresh permutation $P$ on $n$ numbers. Remove the largest number, $n$; we are left with a permutation $P'$ of $n - 1$ numbers. Let $i$ be the first index for which the first $i$ elements are $1, 2, \ldots, i$ in some order. Note that if we were to insert $n$ back into $P'$, we have $i$ places to put $n$ to create a fresh permutation. Thus if $S_j$ is the set of permutations on $n - 1$ numbers with $i = j$, then we have $$f_n = \sum_{j = 1}^{j} j \cdot |S_j|.$$Now if $i$ is minimal and the first $i$ elements are $1, 2, \ldots, i$ in some order, these $i$ elements must be a fresh permutation on $i$ numbers. As there are $(n - i - 1)!$ to order the other $n - i - 1$ numbers, we have $|S_i| = (n - i - 1)! \cdot f_i$, so $$f_n = \sum_{i = 1}^{n - 1} i \cdot f_i\cdot (n - 1 - i)!.$$ Now it remains to show \begin{align*} \sum_{i = 1}^{n - 1} i \cdot f_i \cdot (n - i - 1)! &\ge n \sum_{i = 1}^{n - 2} i \cdot f_i \cdot (n - i - 2)! \\ (n - 1) f_{n - 1} &\ge \sum_{i = 1}^{n - 2} i \cdot f_i \cdot (n \cdot (n - i - 2)! - (n - i - 1)!) \\ \sum_{i = 1}^{n - 2} i \cdot f_i \cdot (n - i - 2)!\cdot (n - 1) &\ge \sum_{i = 1}^{n - 2} i \cdot f_i \cdot(n - i - 2)!\cdot (i + 1), \end{align*}which is true since $n - 1 \ge i + 1$ for all $1 \le i \le n - 2$.

Unless I'm misreading or misunderstanding, this recurrence has appeared in AIME 2018 II #11, as well as a past WOOT practice AIME.

"in some order" - does this just mean in order or am I missing something?

It means that it can be in any order. See the examples that the organizers gave.

CantonMathGuy wrote: Imayormaynotknowcalculus wrote: CantonMathGuy wrote: Unless I'm misreading or misunderstanding, this recurrence has appeared in AIME 2018 II #11, as well as a past WOOT practice AIME. The difference is that they don't have to be in order; for example, the sequence $(2,1,3,5,4,6)$ does not work in this problem, but works in 2018 AIME II Problem 11. I think that permutation doesn't work in the AIME problem either; it fails the condition for $k = 3$ (none of $2$, $1$, $3$ are greater than $3$). Nevermind, @CantonMathGuy is right, they are equivalent statements.

For every fresh permutation on $(1, 2, \dots, n-1)$ we generate $n$ fresh permutations on $(1, 2, \dots, n)$ in the following way: Insert $n$ in the $k$th position for $k=1, 2, \dots, n-1$ Replace $n-1$ with $n$ and append $n-1$ to the end. For example, $3142$ would generate $53142$, $35142$, $31542$, $31452$ and $31524$. All permutations generated this way are distinct. Indeed, the only thing to note is that the second type of permutation yields a non-fresh permutation when $n$ is deleted (because $n-1$ is at the end). This implies the result.

Imayormaynotknowcalculus wrote: CantonMathGuy wrote: Unless I'm misreading or misunderstanding, this recurrence has appeared in AIME 2018 II #11, as well as a past WOOT practice AIME. The difference is that they don't have to be in order; for example, the sequence $(2,1,3,5,4,6)$ does not work in this problem, but works in 2018 AIME II Problem 11. I think that permutation doesn't work in the AIME problem either; it fails the condition for $k = 3$ (none of $2$, $1$, $3$ are greater than $3$).

CantonMathGuy wrote: Imayormaynotknowcalculus wrote: CantonMathGuy wrote: Unless I'm misreading or misunderstanding, this recurrence has appeared in AIME 2018 II #11, as well as a past WOOT practice AIME. The difference is that they don't have to be in order; for example, the sequence $(2,1,3,5,4,6)$ does not work in this problem, but works in 2018 AIME II Problem 11. I think that permutation doesn't work in the AIME problem either; it fails the condition for $k = 3$ (none of $2$, $1$, $3$ are greater than $3$). Sorry, you're right; they are equivalent statements.

v_Enhance wrote: For every fresh permutation on $(1, 2, \dots, n-1)$ we generate $n$ fresh permutations on $(1, 2, \dots, n)$ in the following way: Insert $n$ in the $k$th position for $k=1, 2, \dots, n-1$ Replace $n-1$ with $n$ and append $n-1$ to the end. For example, $3142$ would generate $53142$, $35142$, $31542$, $31452$ and $31524$. All permutations generated this way are distinct. Indeed, the only thing to note is that the second type of permutation yields a non-fresh permutation when $n$ is deleted (because $n-1$ is at the end). This implies the result. Similarly, you can generate $n$ new fresh permutations by replacing $n-1$ with $n$ and then insert $n-1$ in any of the $n$ positions between two consecutive numbers. This way, $3142$ would generate $43152,\ 34152,\ 31452,\ 31542$ and $31524$. Even more generally, you may choose any $k\in\{2, 3,...,n-1\}$, increase every number greater than $k$ by $1$ and then insert $k$ in any of the $n$ positions, still resulting in a fresh permutation.

alifenix- wrote: A permutation of the integers $1, 2, \ldots, m$ is called fresh if there exists no positive integer $k < m$ such that the first $k$ numbers in the permutation are $1, 2, \ldots, k$ in some order. Let $f_m$ be the number of fresh permutations of the integers $1, 2, \ldots, m$. Prove that $f_n \ge n \cdot f_{n - 1}$ for all $n \ge 3$. For example, if $m = 4$, then the permutation $(3, 1, 4, 2)$ is fresh, whereas the permutation $(2, 3, 1, 4)$ is not. Solution. Define a fresh permutation of $n$ distinct real numbers $a_1<a_2<\cdots<a_n$ as a permutation such that the indices $i$ of $a_i,$ forms a fresh permutation of $S_n=\{1,2,\ldots, n\}$. Consider a permutation $\sigma$ of $S_n$ with $\sigma(n-1)=k$ where $k$ is fixed, let $\pi$ be the permutation of $S\backslash \{k\}$ obtained after deleting $k.$ Notice that if $\pi$ is fresh then $\sigma$ is also fresh. Therefore there are at least $f_{n-1}$ fresh permutations such that $\sigma(n-1)=k.$ Thus $f_n\ge nf_{n-1}.~~\blacksquare$

Posting for storage; solved with TheUltimate123 and eisirrational. From any fresh permutation of size $n-1$, we construct $n$ fresh permutations of size $n$ as follows: Insert $n$ in the first, second, $\ldots$, $(n-1)$-th position. Replace $n-1$ with $n$, and append $n-1$ at the end. We can quickly verify that both of these are valid operations, and that moreover they cannot overlap (as no fresh permutation of size $n-1$ has last entry $n-1$). We thus have the desired.

Call a permutation anti-fresh if there exists and integer $k$ such that in a permutation of the numbers $1,2,3,...,m$, in the first $k$ numbers we encounter a permutation of the number $1,2,...,k$. Call the number of anti-fresh permutations $g_m$. We will calculate the number of anti-fresh permutations. We will devise an algorithm that will calculate this for us. The algorithm takes first $1$ and fixes it to the first place, so now we don't really want to have a $2$ next to the $1$, since then we would then count double. So the $2$ has really $m-2$ positions, since the first place is already taken, and it cannot have the second place. So the number $2$ has ${m-2 \choose 1}$ places to choose, and the other numbers can permutate $(m-2)!$, so by $MP$, we have that the total is ${m-2 \choose 1}(m-2)!$ The the algorithm fixes the number $2$ and $1$, in some order (), now we don't want a $3$ on the third spot, so the places number $3$ can choose is ${m-3 \choose 1}$, the others can permutate $(m-3)!$. also if we premutate $1,2$ the configuration is still anti-fresh so we multiply by $2!$.So by $MP$ the total is $2!{m-3 \choose 1}(m-3)!$. We can go on and on... So here is the formal definition of the algorithm The algorithm: It will take a number $k$ and then fix all the numbers less than or equal to $k$ in the first $k$ positions.Next it will send the number $(k+1)$ away from the $(k+1)^{th}$ place, and it will permutate the rest of the $(m-k-1)$ numbers. By this algorithm we get that for a number $k$ which is less than to $m$ ($m \geqslant k \geqslant 0$), we get that the total number of anti-fresh permutations is $(m-1-k)!{k \choose 1}k!$ So by $AP$ we get that: $$ g_m = \sum_{k=0}^{m-1} (m-k-1)!{m-k-1 \choose 1} k! $$ Since an anti-fresh permutation can't be a fresh permutation we have that $f_m + g_m = m!$ So from here we have that $f_m = m! - g_m$, or in other terms we get that: $$ f_m = m! - \sum_{k=0}^{m-2} (m-1-k)!{m-k-1 \choose 1}k! $$ So if we plug that in we must show that: $$g_n \leqslant ng_{n-1}$$Which is true, because when we compare the same elements with the same $k!$, and flip everything over to the other side, we can apply regressive induction and we are done. (because we don't have the same number of elements on each side we must use regressive induction) So we got that $g_n \leqslant ng_{n-1}$ which implies that $f_n \geqslant nf_{n-1}$.....

Remark

Take a fresh permutation of $(1, 2, \dots, n-1)$ and add 1 to all terms greater than $1$. Then insert $2$ in one of $n$ places, creating a permutation of $(1, 2, \dots, n)$. It remains to show that the first $k$ terms are never $1, 2, \dots, k$ in some order. The case of $k=1$ is clear, and for $k\ge 2$, we are done if $2$ is not in the first $k$ terms. Now assuming that $2$ is in the first $k$ terms, the other $k-1$ terms are not $1, 3, 4, \dots, k$, so the first $k$ terms are not $1, 2, 3, 4, \dots, k$. Since this process can be reversed, no two fresh permutations of $(1, 2, \dots, n-1)$ share a fresh permutation of $(1, 2, \dots, n)$. So for each fresh permutation of $(1, 2, \dots, n-1)$, there exist $n$ fresh permutations of $(1, 2, \dots, n)$ and $f_n\ge n\cdot f_{n-1}$.

If we want some bound of $f_n$, we can prove the following: Let $a_n = f_n / n!$ (except $a_1 = 1/2$ instead of 1). The problem is akin to proving that $a_n$ is an increasing sequence. Let: $$s_k = 1 + \frac{1}{\binom{n}{1}} + \dots + \frac{1}{\binom{n}{n-1}}$$$$t_k = \frac{2n-1}{2n} \frac{1}{s_n}$$We can prove that: $$t_{n} \leq a_n \leq t_{n+1}$$which should readily prove that $a_n$ is increasing. First, call a permutation spoiled if it's not fresh, and call its spoilage number to be the smallest $k$ such that the first $k$ elements consists of the numbers $1,\dots,k$. For example, the spoilage number of (2,1,3,4) is 2. So the number of spoiled permutations of $n$ elements with spoilage number $k$ is $f_k (n-k)!$ (because the first $k$ elements must have fresh permutation, otherwise the spoilage number would be smaller). so we have this identity (assuming $f_1 = 1, f_2 = 1$): $$f_1.(n-1)! + f_2.(n-2)! + \dots + f_k.(n-k)! + \dots + f_{n-1}.1! + f_n = n!$$(because every permutation is either fresh, or spoiled with spoilage number ranging from 1 to $n-1$). Using that identity, it's possible to calculate $a_n$ through recursion. $$a_n = \frac{2n-1}{2n} - \sum_{k=1}^{n-1} \frac{a_k}{\binom{n}{k}} $$ The rest is just induction and algebra. In my proof I used the following helper inequality: $\binom{n}{k} \geq \binom{n}{2}, k = 2,\dots,n-1$, so $1 < s_n \leq 1 + 4 \frac{n-2}{n(n-1)} < \frac{5}{3}$ So the left side: $a_n \geq t_{n}$ uses the fact that all $a_k \leq a_{n-1} \leq t_n$, so: $$a_n \geq \frac{2n-1}{2n} - a_{n-1}(s_n-1) \geq \frac{2n-1}{2n}-t_n(s_n-1) = t_n$$ And right side: $a_n \leq t_{n+1}$ uses the fact that $a_k \geq a_1 = 1/2$: $$a_n \leq \frac{2n-1}{2n} - \frac{1}{2} (s_n-1) < \frac{2n+1}{2n+2} \frac{1}{s_{n+1}}$$the last inequality can be verified by hand for small $n \leq 6$ and holds true as $n$ gets larger. The algebra here is longer but it comes down to just looking at the shape of $s_n$

EulersTurban wrote: Call a permutation anti-fresh if there exists and integer $k$ such that in a permutation of the numbers $1,2,3,...,m$, in the first $k$ numbers we encounter a permutation of the number $1,2,...,k$. Call the number of anti-fresh permutations $g_m$. We will calculate the number of anti-fresh permutations. We will devise an algorithm that will calculate this for us. The algorithm takes first $1$ and fixes it to the first place, so now we don't really want to have a $2$ next to the $1$, since then we would then count double. So the $2$ has really $m-2$ positions, since the first place is already taken, and it cannot have the second place. So the number $2$ has ${m-2 \choose 1}$ places to choose, and the other numbers can permutate $(m-2)!$, so by $MP$, we have that the total is ${m-2 \choose 1}(m-2)!$ The the algorithm fixes the number $2$ and $1$, in some order (), now we don't want a $3$ on the third spot, so the places number $3$ can choose is ${m-3 \choose 1}$, the others can permutate $(m-3)!$. also if we premutate $1,2$ the configuration is still anti-fresh so we multiply by $2!$.So by $MP$ the total is $2!{m-3 \choose 1}(m-3)!$. We can go on and on... So here is the formal definition of the algorithm The algorithm: It will take a number $k$ and then fix all the numbers less than or equal to $k$ in the first $k$ positions.Next it will send the number $(k+1)$ away from the $(k+1)^{th}$ place, and it will permutate the rest of the $(m-k-1)$ numbers. By this algorithm we get that for a number $k$ which is less than to $m$ ($m \geqslant k \geqslant 0$), we get that the total number of anti-fresh permutations is $(m-1-k)!{k \choose 1}k!$ So by $AP$ we get that: $$ g_m = \sum_{k=0}^{m-1} (m-k-1)!{k \choose 1} k! $$ Since an anti-fresh permutation can't be a fresh permutation we have that $f_m + g_m = m!$ So from here we have that $f_m = m! - g_m$, or in other terms we get that: $$ f_m = m! - \sum_{k=0}^{m-2} (m-1-k)!{k \choose 1}k! $$ So if we plug that in we must show that: $$g_n \leqslant ng_{n-1}$$Which is true, because when we compare the same elements with the same $k!$, and flip everything over to the other side, we can apply regressive induction and we are done. (because we don't have the same number of elements on each side we must use regressive induction) So we got that $g_n \leqslant ng_{n-1}$ which implies that $f_n \geqslant nf_{n-1}$.....

Remark

I think in your algorithm you're undercounting something. Basically we can verify that $f_3 = 3, f_4 = 13, f_5 = 71$ by hand (or with computer program as well), but your formula doesn't hold up. For example, when you're placing element 3, but 1 and 2 are already placed like 1 - BLANK - 2 -...., then are you counting the 3 in the blank there? or are you counting 1 - BLANK - 2 - 3 ... as well? For that last one, how do you prevent double counting with when the BLANK is filled by 4?

hendrata01 wrote: EulersTurban wrote: Call a permutation anti-fresh if there exists and integer $k$ such that in a permutation of the numbers $1,2,3,...,m$, in the first $k$ numbers we encounter a permutation of the number $1,2,...,k$. Call the number of anti-fresh permutations $g_m$. We will calculate the number of anti-fresh permutations. We will devise an algorithm that will calculate this for us. The algorithm takes first $1$ and fixes it to the first place, so now we don't really want to have a $2$ next to the $1$, since then we would then count double. So the $2$ has really $m-2$ positions, since the first place is already taken, and it cannot have the second place. So the number $2$ has ${m-2 \choose 1}$ places to choose, and the other numbers can permutate $(m-2)!$, so by $MP$, we have that the total is ${m-2 \choose 1}(m-2)!$ The the algorithm fixes the number $2$ and $1$, in some order (), now we don't want a $3$ on the third spot, so the places number $3$ can choose is ${m-3 \choose 1}$, the others can permutate $(m-3)!$. also if we premutate $1,2$ the configuration is still anti-fresh so we multiply by $2!$.So by $MP$ the total is $2!{m-3 \choose 1}(m-3)!$. We can go on and on... So here is the formal definition of the algorithm The algorithm: It will take a number $k$ and then fix all the numbers less than or equal to $k$ in the first $k$ positions.Next it will send the number $(k+1)$ away from the $(k+1)^{th}$ place, and it will permutate the rest of the $(m-k-1)$ numbers. By this algorithm we get that for a number $k$ which is less than to $m$ ($m \geqslant k \geqslant 0$), we get that the total number of anti-fresh permutations is $(m-1-k)!{k \choose 1}k!$ So by $AP$ we get that: $$ g_m = \sum_{k=0}^{m-1} (m-k-1)!{k \choose 1} k! $$ Since an anti-fresh permutation can't be a fresh permutation we have that $f_m + g_m = m!$ So from here we have that $f_m = m! - g_m$, or in other terms we get that: $$ f_m = m! - \sum_{k=0}^{m-2} (m-1-k)!{k \choose 1}k! $$ So if we plug that in we must show that: $$g_n \leqslant ng_{n-1}$$Which is true, because when we compare the same elements with the same $k!$, and flip everything over to the other side, we can apply regressive induction and we are done. (because we don't have the same number of elements on each side we must use regressive induction) So we got that $g_n \leqslant ng_{n-1}$ which implies that $f_n \geqslant nf_{n-1}$.....

Remark

I think in your algorithm you're undercounting something. Basically we can verify that $f_3 = 3, f_4 = 13, f_5 = 71$ by hand (or with computer program as well), but your formula doesn't hold up. For example, when you're placing element 3, but 1 and 2 are already placed like 1 - BLANK - 2 -...., then are you counting the 3 in the blank there? or are you counting 1 - BLANK - 2 - 3 ... as well? For that last one, how do you prevent double counting with when the BLANK is filled by 4? What the algorithm does is following; It fixes the first $k$ numbers into the first $k$ positions, and it prevent the $(k+1)$ number from taking the $(k+1)$ position. Now permutate the first $k$ numbers, you can do this $k!$, the $k+1$ number has $n-k-1$ positions to choose from (the first k are already taken, and we banned it from taking the $(k+1)$ position), and we can permutate the rest $(n-k-1)!$ so by MP we get: $$ (n-k-1)!k!{n-k-1 \choose 1}$$ So yeah I rushed with a solution, so thanks!!!

Storage Proof: Let $S$ be a fresh permutation of size $n-1$. Notice that if we insert $n$ at any of the positions $1,2,3, \cdots , n-1$ then the permutation still remains fresh. This will make $f_n \geq (n-1)f_{n-1}$ . Also notice that making $n-1 \mapsto n$ in $S$ and if we place $n-1$ at the end then also we end up with a fresh permutation. Notice that obviously all these permuatations are distinct. Thus we achieve the desired bound $f_n \geq nf_{n-1}$ $\qquad \blacksquare$

Is there anything wrong in my solution ? If not then it's very easy even for a P4.. Consider any fresh permutation $\sigma(i)$ of $1, 2, \ldots, n-1$ , now we will construct a fresh permutation of size $n$ , note that we can place $n$ anywhere in between the number's of a fresh permutation , either before the $1 st$ number , between $2$ numbers or after the last number giving $n$ choices , so $f_n \ge n f_{n-1}$ as desired. $\blacksquare$

MatBoy-123 wrote: Is there anything wrong in my solution ? If not then it's very easy even for a P4.. Consider any fresh permutation $\sigma(i)$ of $1, 2, \ldots, n-1$ , now we will construct a fresh permutation of size $n$ , note that we can place $n$ anywhere in between the number's of a fresh permutation , either before the $1 st$ number , between $2$ numbers or after the last number giving $n$ choices , so $f_n \ge n f_{n-1}$ as desired. $\blacksquare$ Yes, there is mistake. For each fresh permutation of $n-1$ you can't get fresh permutation of $n$ adding $n$ to the end.

Take a fresh permutation of length $n-1$. We can insert the number $n$ in any spot that isn't the last spot to make a new fresh permutation. This yields $(n-1) \cdot f_{n-1}$ new fresh permutations. Also, by replacing the $n-1$ by $n$ and moving the $n-1$ to the end yields a new fresh permutation. These $f_{n-1}$ new fresh permutations of length $n$ are different from the previous ones since the previous ones can't end in $n-1$. Thus, there is at least $n \cdot f_{n-1}$ fresh permutations of length $n$ as desired.