Permutations

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

\begin{equation} P(n,k)=n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)=\frac{n!}{(n-k)!}.\label{k-permutations}\tag{1.2.1} \end{equation}

This is a simple computation in Sage, using the factorial() function. We illustrate two ways to compute \(P(10,6)\text{.}\)

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.

Notice that a simple computation with \(10\) and \(4\) tells us that the list contains \(6\) integers. (\(10-4=6\))

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.

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 \(10^{57}\) 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.

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 \(\set{1,\,2,\,3,\,\dots,\,n}\) by creating a Permutations object.

The strategy of creating a generator object and then employing it in some way is pervasive in the Sage combinatorics routines.