More Permutations Watch

This discussion is closed.
flyinghorse
Badges: 0
Rep:
?
#1
Report Thread starter 13 years ago
#1
Just wondering if anyone could help with this question:

As n increases from 2 upwards, the number of permutations in S_n that send 1->2 is equal to (n-1)! Prove that this pattern holds for all n.

[may find it useful to consider the composition of each permutation with the transposition (1 2)]

cheers
0
flyinghorse
Badges: 0
Rep:
?
#2
Report Thread starter 13 years ago
#2
Actually, does this look alright?

We know that there are n! permutations in S[n].
If we write a permutation as list where the i-th list element tells us the destination of ith element of {1,...,n}, e.g. the permutation of {1,2,3,4,5,6} sending
1->6
2->5
3->4
4->3
5->2
6->1
would be written
[6,5,4,3,2,1].
Now we want to list and count all of the permutations in S[n] that send 1->2. So, using this list notation, all of these permutations must be of the form
[2,(any arrangement of the numbers 1,3,4,5...n)].
So the number of permutations sending 1->2 is actually equal to the number of ways in which we can arrange the numbers {1,3,4,5...n}, i.e., the number of permutations of these numbers: (n-1)!
0
RichE
Badges: 15
Rep:
?
#3
Report 13 years ago
#3
(Original post by flyinghorse)
Actually, does this look alright?

We know that there are n! permutations in S[n].
If we write a permutation as list where the i-th list element tells us the destination of ith element of {1,...,n}, e.g. the permutation of {1,2,3,4,5,6} sending
1->6
2->5
3->4
4->3
5->2
6->1
would be written
[6,5,4,3,2,1].
Now we want to list and count all of the permutations in S[n] that send 1->2. So, using this list notation, all of these permutations must be of the form
[2,(any arrangement of the numbers 1,3,4,5...n)].
So the number of permutations sending 1->2 is actually equal to the number of ways in which we can arrange the numbers {1,3,4,5...n}, i.e., the number of permutations of these numbers: (n-1)!
Yes exactly; there are as many such perms as there are bijections from

{2,3,4,....,n} to {1,3,4,....,n}

which are just two sets each with n-1 elements.
0
naivesincerity
Badges: 0
Rep:
?
#4
Report 13 years ago
#4
(Original post by RichE)
Yes exactly; there are as many such perms as there are bijections from

{2,3,4,....,n} to {1,3,4,....,n}

which are just two sets each with n-1 elements.

Could you also prove it by induction?
0
flyinghorse
Badges: 0
Rep:
?
#5
Report Thread starter 13 years ago
#5
(Original post by RichE)
Yes exactly; there are as many such perms as there are bijections from

{2,3,4,....,n} to {1,3,4,....,n}

which are just two sets each with n-1 elements.
thanks for all of your help
0
X
new posts
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of Lincoln
    Brayford Campus Undergraduate
    Wed, 12 Dec '18
  • Bournemouth University
    Midwifery Open Day at Portsmouth Campus Undergraduate
    Wed, 12 Dec '18
  • Buckinghamshire New University
    All undergraduate Undergraduate
    Wed, 12 Dec '18

Do you like exams?

Yes (146)
18.27%
No (486)
60.83%
Not really bothered about them (167)
20.9%

Watched Threads

View All