Permutation groups¶

A permutation group is a finite group G whose elements are permutations of a given finite set X (i.e., bijections X⟶X) and whose group operation is the composition of permutations. The number of elements of X is called the degree of G.

In Sage, a permutation is represented as either a string that defines a permutation using disjoint cycle notation, or a list of tuples, which represent disjoint cycles. That is:

(a,...,b)(c,...,d)(e,...,f) <--> [(a,...b),(c,...,d),(e,...,f)]

print Permutations([1,2,3]).list(), "\n"
print Permutations(4).list(), "\n"
print Permutations("Hey").list()

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]] 

[['H', 'e', 'y'], ['H', 'y', 'e'], ['e', 'H', 'y'], ['e', 'y', 'H'], ['y', 'H', 'e'], ['y', 'e', 'H']]

Generators have a command G.next(obj) that takes the input object and outputs the next object that would occur in the list. If the object is not part of the generator or it is at the end of the list it will return either None or False. Similarily there are G.first( ) and G.last( ) commands that get the first and last elements.

p = Permutation([1, 3, 2])
next(p)

[2, 1, 3]

Sometimes we are only interested in permutations of the n elements that have a certain length k. To do so just pass you desired length k as a second argument: Permutations(n,k).

L = Permutations(5,3)
print L.list()

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 2], [1, 3, 4], [1, 3, 5], [1, 4, 2], [1, 4, 3], [1, 4, 5], [1, 5, 2], [1, 5, 3], [1, 5, 4], [2, 1, 3], [2, 1, 4], [2, 1, 5], [2, 3, 1], [2, 3, 4], [2, 3, 5], [2, 4, 1], [2, 4, 3], [2, 4, 5], [2, 5, 1], [2, 5, 3], [2, 5, 4], [3, 1, 2], [3, 1, 4], [3, 1, 5], [3, 2, 1], [3, 2, 4], [3, 2, 5], [3, 4, 1], [3, 4, 2], [3, 4, 5], [3, 5, 1], [3, 5, 2], [3, 5, 4], [4, 1, 2], [4, 1, 3], [4, 1, 5], [4, 2, 1], [4, 2, 3], [4, 2, 5], [4, 3, 1], [4, 3, 2], [4, 3, 5], [4, 5, 1], [4, 5, 2], [4, 5, 3], [5, 1, 2], [5, 1, 3], [5, 1, 4], [5, 2, 1], [5, 2, 3], [5, 2, 4], [5, 3, 1], [5, 3, 2], [5, 3, 4], [5, 4, 1], [5, 4, 2], [5, 4, 3]]

To create an individual element of a Permutation_Class object you can simply do the following.

p = Permutation([1,3,2,4])
p

[1, 3, 2, 4]

when examing permutations of [n] it is possible to get the number of fixed points or the number of peaks in a permutation. A fixed point in combinatorics is that for some integer 0<i<n+1, the ith spot in the permutation is i, in 1342 the number 1 is in the first spot and so it is a fixed point. A peak in a permutation is when three consecutive numbers ijk have the property that ik.

print p.number_of_fixed_points()
print p.number_of_peaks()

2
1

you can even get a list of permutations that avoid certain patterns.

L = Permutations(5, avoiding = [3,4,1,2])
print L
print L.cardinality()
L.cardinality() < factorial(5)

Standard permutations of 5 avoiding [[3, 4, 1, 2]]
103

True

We can check if a permutation avoids some element by:

p = Permutation([1,2,3,5,4])
print p.avoids([3,1,2,4])
print p.avoids([1,2,3,4])

True
False

Return the class of all cyclic permutations of the input set in cycle notation

CyclicPermutations(range(4)).list()

[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]

Combinations of cyclic permutations of each cell of a given partition

CyclicPermutationsOfPartition([[1,2,3,4],[5,6]]).list()

[[[1, 2, 3, 4], [5, 6]],
 [[1, 2, 4, 3], [5, 6]],
 [[1, 3, 2, 4], [5, 6]],
 [[1, 3, 4, 2], [5, 6]],
 [[1, 4, 2, 3], [5, 6]],
 [[1, 4, 3, 2], [5, 6]]]

Assignment¶

1a) Find the number of ways in which 5 people A,B,C,D,E can be seated at a round table, such that A and B must always sit together.

len(CyclicPermutations(range(4)).list())*len(CyclicPermutationsOfPartition([[1,2,3],[4,5]]).list())

12

1b) Find the number of ways in which 5 people A,B,C,D,E can be seated at a round table, such that C and D must not sit together.

len(CyclicPermutations(range(5)).list()) - len(CyclicPermutations(range(4)).list())*len(CyclicPermutationsOfPartition([[1,2,3],[4,5]]).list())

12

1c) In how many ways can 3 men and 3 ladies be seated at around table such that no two men are seated together?

# ways that the men and women sit alternately
len(CyclicPermutations(range(2)).list())*len(CyclicPermutationsOfPartition([[1,2,3],[4,5]]).list())

2

# ways 3 men can be seated in the remaining seats
factorial(3)

6

len(CyclicPermutations(range(2)).list())*len(CyclicPermutationsOfPartition([[1,2,3],[4,5]]).list())*factorial(3)

12

1d)Write a function that outputs all possible strings and number of all permutations formed by a 3 character string exactly once without using any sage built-in functions.

def permu(string):
    count =0
    for i in range(len(string)):
        for j in range(len(string)):
            for k in range(len(string)):
                if(i!=j and i!=k and j!=k):
                    print(""+ string[i] + string[j]+ string[k])
                    count +=1
    print(count)

permu(['h','e','y'])

hey
hye
ehy
eyh
yhe
yeh
6

2) Let S,T,U∈$ℝ^{2*2}$ such that, Si,j,Ti,j,Ui,j∈0,1,⋯,9 How many of the products S⋅T⋅U are invertible?

R = [0..9]
C = cartesian_product((R,R,R,R))
len( [ c for c in C if matrix( ZZ, 2, 2, list(c) ).det() ] )

9430