Find permutations

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Find permutations

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: INMO 1992 Problem 4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1592 posts

Rushil

#1 h Oct 4, 2005, 12:00 AM • 2 Y

Y by Adventure10, Mango247

Find the number of permutations $( p_1, p_2, p_3 , p_4 , p_5 , p_6)$ of $1, 2 ,3,4,5,6$ such that for any $k, 1 \leq k \leq 5$ , $(p_1, \ldots, p_k)$ does not form a permutation of $1 , 2, \ldots, k$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11 posts

XT

#2 h Jan 21, 2006, 4:14 PM • 3 Y

Y by Titttu, Adventure10, Mango247

Hello everyone!

Here I post my (ugly) idea to proceed which is simply to "Count 'em All!"

It's not a complete solution, I'm just explaining how I tried to solve it. I've probably done some mistake so any correction or alternate solution is welcome!

Well, let's start!
We see that it can't be $p_6=6$ or it would fall taking $k=5$ . How many of these permutations with $p_6=6$ are there? Easy! They are $6!\cdot\frac{1}{6}=5!=120$ .
Going on it's clear that it can't be in any order that $5$ and $6$ take the two last positions or it won't work with $k=4$ . This may happen only taking $p_5=6$ and $p_6=5$ (cause we have excluded $p_6=6$ here above!). So in how many ways may it happen? In $4!=24$ ways.
Again, $4$ , $5$ and $6$ can't (in any order) be the last three $p_i$ . How do we count the number of permutations where they are put in such way? The options are $3!\cdot3!$ but we must subtract the ones we have counted before (that are $2\cdot3!$ with $p_6=6$ and $1\cdot3!$ with $p_5=6,p_6=5$ ) so we have $3\cdot3!=18$ new "illegal" permutations.
...
On this way you check the number of illegal permutations with $k=2$ and $k=1$ and you're done. My result is $461$ possible permutations.

Has anybody solved it? Please post!

Bye people!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#3 h Dec 22, 2011, 4:05 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

I have 481 as my result calculating compliment cases

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#4 h Dec 22, 2011, 4:15 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

I have got it right now, it is 461 by PIE

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

332 posts

#5 h Dec 22, 2011, 7:41 AM • 2 Y

Y by Adventure10, Mango247

i THINK WE CAN USE A RECURSION IDEA TOO
If we write T(n) as the number of permutations of 1,2,...,n such that (p(1),...,p(n-1)) is not a permutation of 1 to n-1 , then we can write T(n) in terms of T(1) to T(n-1) from where the rest of the computation shd be fairly simple ...........

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16123 posts

JBL

#6 h Dec 22, 2011, 10:30 PM • 2 Y

Y by Adventure10, Mango247

These are called indecomposable permutations; one can solve for the number of them of a given length using generating functions, or use a recursion. They are given by sequence A003319 in the OEIS.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2280 posts

#7 h Jul 29, 2014, 2:04 PM • 2 Y

Y by Chandrachur, Adventure10

What is the recursion formed ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

385 posts

#8 h Jul 18, 2015, 3:02 AM • 2 Y

Y by Adventure10, Mango247

I am not sorry for reviving this topic i think this is required.
I have also solved this problem in somewhat the same "ugly" way mentioned above just now and was(is) looking for an elegant one. i have not much knowledge of generating functions so what is the recursion formed????

This post has been edited 2 times. Last edited by Chandrachur, Jul 18, 2015, 7:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

652 posts

#9 h Jul 18, 2015, 5:58 AM • 1 Y

Y by Adventure10

Maybe the recursion is this way: Take a permutation which is permissible for $n$ , append $n+1$ to its end, and then just swap the $n+1$ and any other number. I think it works, but maybe we are missing out many cases

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

385 posts

#10 h Jul 18, 2015, 6:15 AM • 1 Y

Y by Adventure10

AdithyaBhaskar wrote:

Maybe the recursion is this way: Take a permutation which is permissible for $n$ , append $n+1$ to its end, and then just swap the $n+1$ and any other number. I think it works, but maybe we are missing out many cases

Ya obviously you are missing out a hell lot of other cases. For the simplest example see that it you place $n+1$ in front then any permutation of { $1,2,...,n$ } after that is a vaild permuntation(which brings in a good $n!$ new ways)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

385 posts

#11 h Jul 18, 2015, 7:28 AM • 2 Y

Y by srramanujan, Adventure10

I have got a way which i describe as QUASI-RECURSION as it is actually a recursion but i found solving it more difficult than to go with it in a way that makes it somewhat like the solution @XT has provided above.
.....
Let $S_n$ denote the set of required arrangements whose number of elements is required when u replace $6$ by $n$ in the question.Let $|S_n|=t_n$ (Looks ambitious

it isn't

)
We count $t_6$ by dividing that into 5 mutually disjoint cases namely when $p_i=6$ for $i=1,2,3,4,5$ (assuming u already figured out why $p_6$ can't be $6$

)
Case1_p_1=6
Case2_p_2=6
Case3_p_3=6
Case4_p_4=6
Finally_a_recursive_case_p_5=6
So finally the recursion is $t_6=(5!)+(4*4!)+(5!-(4!+3!))+(5!-(4!+3!+3*2!))+t_5$ . or $t_6=390+t_5$ .
Sad part is to relate $t_5$ and $t_4$ you will get a number other than $390$ in the recursion and good part is that $5$ is quite close to $1$ (thanks to question setter

).
But surely you can find a logical pattern and get(by logic)
$t_5=4!+3*3!+(4!-(3!+2!))+t_4$ or , $t_5=58+t_4$ and
$t_4=3!+2*2!+t_3$ or , $t_4=10+t_3$ and
$t_3=2!+t_2$ or , $t_3=2+t_2$ . and $t_2$ is trivially $1$ (check it!!!)

So $t_6=390+58+10+2+1=461$ .

This post has been edited 3 times. Last edited by Chandrachur, Jul 18, 2015, 7:39 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

385 posts

#12 h Jul 18, 2015, 7:47 AM • 1 Y

Y by Adventure10

Can anyone generalize my recursion above???. U see that the main thing is that
the number of caseworks to be done for $n^{th}$ recursion statement also itself follows a recursion of $C_n=1+C_{n-1}$ (

).
I may sound inebriated but really that is the main itch in the problem now.

This post has been edited 1 time. Last edited by Chandrachur, Jul 18, 2015, 7:47 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7 posts

Titttu

#13 h Jun 21, 2020, 11:59 AM

Y by

XT wrote:

Hello everyone!

Here I post my (ugly) idea to proceed which is simply to "Count 'em All!"

:lol:

It's not a complete solution, I'm just explaining how I tried to solve it. I've probably done some mistake so any correction or alternate solution is welcome!

Well, let's start!
We see that it can't be $p_6=6$ or it would fall taking $k=5$ . How many of these permutations with $p_6=6$ are there? Easy! They are $6!\cdot\frac{1}{6}=5!=120$ .
Going on it's clear that it can't be in any order that $5$ and $6$ take the two last positions or it won't work with $k=4$ . This may happen only taking $p_5=6$ and $p_6=5$ (cause we have excluded $p_6=6$ here above!). So in how many ways may it happen? In $4!=24$ ways.
Again, $4$ , $5$ and $6$ can't (in any order) be the last three $p_i$ . How do we count the number of permutations where they are put in such way? The options are $3!\cdot3!$ but we must subtract the ones we have counted before (that are $2\cdot3!$ with $p_6=6$ and $1\cdot3!$ with $p_5=6,p_6=5$ ) so we have $3\cdot3!=18$ new "illegal" permutations.
...
On this way you check the number of illegal permutations with $k=2$ and $k=1$ and you're done. My result is $461$ possible permutations.

Has anybody solved it? Please post! :lol:

:lol:

Bye people!

The ugly method is the method so far

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

33 posts

#14 h Apr 29, 2021, 12:08 AM

Y by

@Chandrachur
In case 3 $p_1$ cannot be equal to $1$ . It will violate the condition for $k=1$ constraint,

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

33 posts

#15 h Apr 29, 2021, 12:09 AM

Y by

Chandrachur wrote:

I have got a way which i describe as QUASI-RECURSION as it is actually a recursion but i found solving it more difficult than to go with it in a way that makes it somewhat like the solution @XT has provided above.
.....
Let $S_n$ denote the set of required arrangements whose number of elements is required when u replace $6$ by $n$ in the question.Let $|S_n|=t_n$ (Looks ambitious :huh:

:huh:

it isn't

:rotfl:

)
We count $t_6$ by dividing that into 5 mutually disjoint cases namely when $p_i=6$ for $i=1,2,3,4,5$ (assuming u already figured out why $p_6$ can't be $6$

)
Case1_p_1=6
Case2_p_2=6
Case3_p_3=6
Case4_p_4=6
Finally_a_recursive_case_p_5=6
So finally the recursion is $t_6=(5!)+(4*4!)+(5!-(4!+3!))+(5!-(4!+3!+3*2!))+t_5$ . or $t_6=390+t_5$ .
Sad part is to relate $t_5$ and $t_4$ you will get a number other than $390$ in the recursion and good part is that $5$ is quite close to $1$ (thanks to question setter :omighty:

:omighty:

).
But surely you can find a logical pattern and get(by logic)
$t_5=4!+3*3!+(4!-(3!+2!))+t_4$ or , $t_5=58+t_4$ and
$t_4=3!+2*2!+t_3$ or , $t_4=10+t_3$ and
$t_3=2!+t_2$ or , $t_3=2+t_2$ . and $t_2$ is trivially $1$ (check it!!!)
:trampoline:

:trampoline:

So $t_6=390+58+10+2+1=461$ .

In case 3 $p_1$ cannot be equal to $1$ . It will violate the condition for $k=1$ constraint,

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1839 posts

PEKKA

#16 h Apr 29, 2021, 12:09 AM • 1 Y

Y by Mango247

nice 6 year bump

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1133 posts

#18 h Dec 16, 2023, 3:55 AM

Y by

Let's denote the set of permutations of $\{1, \dots, n\}$ as $P_n$ , where $|P_n|=n!$ is the number of permutations. For a permutation $P=(\alpha_1 \dots \alpha_n)$ , let's define the degree of the permutation, denoted as $\text{der} P$ (Degree of a permutation can be a different concept in the literature. Here we use our definition), for $1 \leq k \leq n$ , $(\alpha_1\dots \alpha_k)$ represents a permutation of the set $\{1, \dots, k\}$ , and the degree is the smallest $k$ for which this holds.

Let $Q_n$ denote the set of permutations of $\{1,\dots, n\}$ such that, for every $1\leq k \leq n-1$ , $(\alpha_1\dots \alpha_k)$ is not a permutation of $\{1,\dots, k\}$ . For example, $Q_1 = \{(1)\}$ and $Q_2 = \{(21)\}$ . The problem asks for $|Q_6|$ .

For $1\leq i \leq n$ , let $D_i = \{P \in P_n \mid \text {der} P = i\}$ . Note that $D_i$ and $D_j$ are disjoint for $i \neq j$ , and $P_n = D_1 \cup \dots \cup D_n$ . First, observe that $D_n= \{P \in P_n \mid \text {der} P = n\} = Q_n$ .

If we append a permutation of $\{i+1, \dots, n\}$ to $Q_i$ , we obtain a permutation in $D_i$ . Therefore, we have the equation:

$n! = |P_n| = |Q_n| + |Q_{n-1}|\cdot 1! + |Q_{n-2}|\cdot 2! + \dots + |Q_{1}|\cdot (n-1)! = \displaystyle \sum_{i=1}^{n} |Q_i|\cdot (n-i)!$
Let's calculate for smaller values:

$|P_3| = 3! = |Q_3| + |Q_2|\cdot 1! + |Q_1|\cdot 2! \Longrightarrow |Q_3| = 3! - 1 - 2 = 3$ .
$|P_4| = 4! = |Q_4| + |Q_3|\cdot 1! + |Q_2|\cdot 2! + |Q_1| \cdot 3! \Longrightarrow |Q_4| = 4! - 3 - 2 - 6 = 13$ .
$|P_5| = 5! = |Q_5| + |Q_4|\cdot 1! + |Q_3|\cdot 2! + |Q_2| \cdot 3! + |Q_1| \cdot 4! \Longrightarrow |Q_5| = 5! - 13 - 6 - 6 - 24 = 71$ .
$|P_6| = 6! = |Q_6| + |Q_5|\cdot 1! + |Q_4|\cdot 2! + |Q_3| \cdot 3! + |Q_2| \cdot 4! + |Q_1| \cdot 5! \Longrightarrow |Q_6| = 6! - 71 - 26 - 18 - 24 - 120 = 461$ .

This post has been edited 6 times. Last edited by xeroxia, Dec 16, 2023, 4:08 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a