Section 1.2 Permutations
¶A k-permutation of an n-set is a selection of k objects from a set of n distinct objects and then arranged into an ordered list. So these are sometimes called arrangements. From the multiplication principle, we deduce the following formula for the number of k-permutations
This is a simple computation in Sage, using the factorial()
function. We illustrate two ways to compute P(10,6).
xxxxxxxxxx
factorial(10)/factorial(10-6)
The srange()
function is a variant of the standard Python range()
function, except it produces a list of Sage integers. These integers can be as large as necessary, in contrast to Python's integer types that have a limited range of values. In this example, we start with 10 and count down to 5 to mimic the first expression in (1.2.1). Note the creation of the the list stops before using the second argument. The prod()
function multiplies all the items in the list given as its argument.
xxxxxxxxxx
prod(srange(10, 4, -1))
Notice that a simple computation with 10 and 4 tells us that the list contains 6 integers. (10−4=6)
xxxxxxxxxx
srange(10, 4, -1)
So it is a simple matter to compute the number of permutations, but Sage can also enumerate all the possibilities. We create all pairs of pets, in different orders.
xxxxxxxxxx
pets = ['dog', 'cat', 'bird', 'pig']
pairs = Arrangements(pets, 2)
pairs
That is a bit unsatisfying. We know what we built and would hope that asking Sage to output pairs
would show us all of them. But this is typical of the combinatorics routines. What if we created 100 different types of pets and asked to print ordered lists of 30 of them? There are approximately 1057 such permutations! What Sage has built is an object that generates the permutations we requested. You can do various operations with it, as we illustrate.
xxxxxxxxxx
pairs.cardinality()
xxxxxxxxxx
pairs.list()
xxxxxxxxxx
for p in pairs:
print( p[0] + ' and ' + p[1] )
This final example illustrates the use of pairs
as a Python iterable that we can use in a for
loop. We have a simple demonstration of doing something with each pair rather than just listing them verbatim. In this case, we form a single string from each pair and display it.
If you do not want to form permutations of exotic objects, you can just default to permutations of the n symbols {1,2,3,…,n} by creating a Permutations
object.
xxxxxxxxxx
perms = Permutations(4, 2)
perms.list()
The strategy of creating a generator object and then employing it in some way is pervasive in the Sage combinatorics routines.