Math 146 Homework 1
INSTRUCTIONS:
You do not have to hand the exercises, but you will be tested on the quizzes and the exams using some of these exercises.
1. A permutation that has just one cycle is said to be cyclic. Prove that there are (n − 1)! cyclic permutations in Sn.
2. Suppose there are n boys and m girls in school. In how many ways can you arrange the children in a line while leaving the girls together?
3. How many five-digit telephone numbers have a digit that occurs more than once?
4. How many permutations are there in S6 which satisfy σ 2 = id, but σ is not the identity permutation?
5. Let a and b permutations in S9 whose representation in cycle notation is (1, 2, 3, 7)(49)(58)(6) (1, 3, 5)(2, 4, 6)(7, 8, 9) Write down the cycle notations for ab, ba, a2 , b2 , a−1 , b−1 . Find the sign of a, b and express them in terms of transpositions (try using the smallest number of transpositions you can).
6. A pack of 52 cards is divided into two equal parts and then “interlaced” so that if the original order was 1,2,3,4,5,6,..., the new order is 1,27,2,28, etc. How many times must this special shuffle be repeated before the cards are once again in the original order?
7. n men enter a disreputable establishment, and each one leaves a coat and an umbrella at the door. When a message is received say the establishment is about to be raided by the police, the men leave in a hurry, and each man grabs a wrong coat and a wrong umbrella. Give a formula for the probability this strange retrieval of coats and umbrellas occurs.
8. In how many ways can you place eight chess rooks on a chessboard in such a way that no two are in the same row or column (non-attacking rooks in chess terminology)? Now, How about if the rooks cannot be placed at the square at positions (1, 4) (2, 2),(4, 4), (5, 5), (6, 1),(7, 7) and (8, 7)?
9. Prove that every even permutation can be written as the product of 3-cycles. Further we say a 3-cycle is consecutive if it is of the form (k,k+1,k+2). Prove that the consecutive cycles (1, 2, 3),(2, 3, 4),...,and (n − 2, n − 1, n) generate the subgroup An. 1
10. Prove that S5 does not have a subgroup of order 15. On the other hand, construct subgroups of S5 with orders 1,2,3,4,5,6,8,10,12,20,24,60,120. Similarly, write down the possible orders of permutations that occur inside S8 and give an example of a divisor of 8! that is not present as the order of a permutation.
11. How many permutations of S8 have no even number fixed? How many permutations are there in S8 such that exactly 4 numbers remain in their original position?
12. How many permutations in S6 are there of order six? How many permutations in S6 have order four? Finally, how many even permutations of A6 have order 4?
13. What is the average number of fixed points of permutations in Sn?