This document is one of More SageMath Tutorials. You may edit it on github. \(\def\NN{\mathbb{N}}\) \(\def\ZZ{\mathbb{Z}}\) \(\def\QQ{\mathbb{Q}}\) \(\def\RR{\mathbb{R}}\) \(\def\CC{\mathbb{C}}\)

Combinatorics in Sage

Documentation/Resources

  • You can use tab completion to explore modules in Sage. For instance, place your cursor at the end of the following lines and hit tab.

    sage: sage.combinat.

    sage: sage.combinat.sf.

    sage: sage.combinat.words.

  • There is a chapter on Combinatorics in the Reference Manual.

  • There is a wiki page describing the sage-combinat project.

  • There is a sage-combinat Google group.

Iterators/Generators

An iterator is an object that allows one to iterate through all the elements of a collection. Iterators have a next() method that return the next element in the collection.

The Python command iter returns an iterator from an object (the object itself must support iteration).

sage: it = iter([1,2,3])
sage: it
<listiterator object at 0x35a3950>

sage: it.next()
1

sage: it.next()
2

sage: it.next()
3

sage: it.next()
Traceback (most recent call last):
...
StopIteration

A generator is a function that is used to define an iterator. Instead of return statements, it has yield statements (it cannot have both!). When the function encounters a yield statement, the function pauses and returns that value to the user. It continues from where it left off when it is asked for the next value.

sage: def fibonacci_iterator(a=0, b=1):
....:     while True:
....:         yield b
....:         a, b = b, a+b

sage: f = fibonacci_iterator()

sage: f.next()
1

sage: f.next()
1

sage: f.next()
2

sage: f.next()
3

sage: f.next()
5

sage: f.next()
8

Project Euler Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

sage: result = 0

sage: for f in fibonacci_iterator():
....:     if f > 4000000:
....:         break
....:     if is_even(f):
....:         result += f

sage: result
4613732

Combinatorial Classes

There are many objects in Sage that model sets of combinatorial objects.

sage: P = Permutations(3)
sage: P
Standard permutations of 3

sage: P.cardinality()
6

sage: P.list()
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

sage: Permutations(1000)
Standard permutations of 1000

sage: time P = Permutations(7, avoiding=[2,1,4,3])
sage: P
Time: CPU 0.00 s, Wall: 0.00 s
Standard permutations of 7 avoiding [[2, 1, 4, 3]]

sage: time P.cardinality()
2761
Time: CPU 4.10 s, Wall: 4.20 s

sage: P = Partitions(4)
sage: P
Partitions of the integer 4

sage: for p in Partitions(4):
....:     print p
[4]
[3, 1]
[2, 2]
[2, 1, 1]
[1, 1, 1, 1]

sage: for c in Compositions(4):
....:     print c
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]
[4]

sage: DyckWords(4)
Dyck words with 4 opening parentheses and 4 closing parentheses

sage: DyckWords(4).cardinality()
14

sage: for dw in DyckWords(4):
....:     print dw
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
(()()())
(()(()))
((()))()
((())())
((()()))
(((())))

sage: W = Words("ab")
sage: W
Words over Ordered Alphabet ['a', 'b']

sage: W.cardinality()
+Infinity

sage: it = iter(W)
sage: for a in range(16):
....:     print it.next()
word:
word: a
word: b
word: aa
word: ab
word: ba
word: bb
word: aaa
word: aab
word: aba
word: abb
word: baa
word: bab
word: bba
word: bbb
word: aaaa

sage: P = posets()
sage: P
Posets

sage: P.cardinality()
+Infinity

sage: it = iter(P)
sage: for a in range(10):
....:     print it.next()
Finite poset containing 0 elements
Finite poset containing 1 elements
Finite poset containing 2 elements
Finite poset containing 2 elements
Finite poset containing 3 elements
Finite poset containing 3 elements
Finite poset containing 3 elements
Finite poset containing 3 elements
Finite poset containing 3 elements
Finite poset containing 4 elements

Operations producing new combinatorial classes

Sage supports several ways of creating new combinatorial classes from objects.

sage: C = Combinations([1,2,3], 2)
sage: C
Combinations of [1, 2, 3] of length 2

sage: C.list()
[[1, 2], [1, 3], [2, 3]]

sage: S = Subsets([1,2,3], 2)
sage: S
Subsets of {1, 2, 3} of size 2

sage: S.list()
[{1, 2}, {1, 3}, {2, 3}]

sage: S = SetPartitions(['a','b','c'])
sage: S
Set partitions of ['a', 'b', 'c']

sage: S.list()
[{{'a', 'c', 'b'}}, {{'c', 'b'}, {'a'}}, {{'c'}, {'a', 'b'}}, {{'a', 'c'}, {'b'}}, {{'c'}, {'b'}, {'a'}}]

sage: S.cardinality()
5

Example: Vexillary involutions

A vexillary involution is a permutation that:

  1. avoids the pattern 2143;
  2. is an involution (that is, \(p = p^{-1}\)).

We can create the set of vexillary involutions of the set {1,2,3,4} in Sage by filtering the set of permutations of {1,2,3,4}.

sage: def is_involution(p):
....:     return p == p.inverse()

sage: P = Permutations(4, avoiding=[2,1,4,3]).filter(is_involution)
sage: P
Filtered sublass of Standard permutations of 4 avoiding [[2, 1, 4, 3]]

sage: P.cardinality()
9

sage: P.list()
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 3, 2], [3, 4, 1, 2], [2, 1, 3, 4], [4, 2, 3, 1], [3, 2, 1, 4], [4, 3, 2, 1]]

sage: def number_of_vexillary_involutions(n):
....:     P = Permutations(n, avoiding=[2,1,4,3]).filter(is_involution)
....:     return P.cardinality()

sage: SL = sloane_find([number_of_vexillary_involutions(n) for n in range(1,7)])
Searching Sloane's online database...

sage: SL[0]
[1006, 'Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.', [1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829]]

Defining your own Combinatorial Classes

Warning

Combinatorial classes are now deprecated, and will disappear as soon as all derived classes in Sage’s library will have been fixed.

If you want to work with a set of objects that is not defined in Sage, then you can use the object-oriented features of Python/Sage to define a new class to model your set.

By inheriting from the CombinatorialClass class, your object will behave like the objects we saw above ( Permutations(3) , Compositions(6) , etc.).

At the very minimum, you should implement the following methods:

  • __init__ : takes as arguments what is needed to define the set;
  • __iter__ : the algorithm to iter ate through the elements of the set;
  • __repr__ : (optional) a string repr esentation of the set.
sage: class VexillaryInvolutions(CombinatorialClass):
....:     def __init__(self, n):
....:         """
....:         The combinatorial class of vexillary involutions
....:         """
....:         self._n = n
....:
....:     def __iter__(self):
....:         P = Permutations(self._n, avoiding=[2,1,4,3]).filter(lambda p : p == p.inverse())
....:         for p in P:
....:             yield p
....:
....:     def __repr__(self):
....:         return "Vexillary involutions of %s" % self._n

sage: V.list()
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 3, 2], [3, 4, 1, 2], [2, 1, 3, 4], [4, 2, 3, 1], [3, 2, 1, 4], [4, 3, 2, 1]]

sage: V.cardinality()
9

sage: [2,1,3,4] in V
Traceback (most recent call last):
...
NotImplementedError

sage: class VexillaryInvolutions(CombinatorialClass):
....:     def __init__(self, n):
....:         """
....:         The combinatorial class of vexillary involutions
....:         """
....:         self._n = n
....:
....:     def __iter__(self):
....:         P = Permutations(self._n, avoiding=[2,1,4,3]).filter(lambda p : p == p.inverse())
....:         for p in P:
....:             yield p
....:
....:     def __repr__(self):
....:         return "Vexillary involutions of %s" % self._n
....:
....:     def __contains__(self, p):
....:         p = Permutation(p)
....:         return len(p) == self._n and p.avoids([2,1,4,3]) and p == p.inverse()

sage: V = VexillaryInvolutions(4)
sage: V
Vexillary involutions of 4

sage: [2,1,3,4] in V
True

sage: [2,1,4,3] in V
False

Exercise: Sums of subsets

(Inspired by Project Euler Problem 201)

For any set \(A\) of numbers, let \(\sigma(A)\) be the sum of the elements of \(A\).

Consider the set \(B = \{ 1, 2, 3, 4 \}\). There are 6 subsets of \(B\) of size \(2\):

\[\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}\]

And the sums of the numbers in these subsets are

\[\begin{split}\sigma(\{1, 2\}) = 3 \\ \sigma(\{1, 3\}) = 4 \\ \sigma(\{1, 4\}) = 5 \\ \sigma(\{2, 3\}) = 5 \\ \sigma(\{2, 4\}) = 6 \\ \sigma(\{3, 4\}) = 7 \\\end{split}\]

Some of these sums occur more than once, others are unique. The set of unique sums is \(\{3, 4, 6, 7\}\), and the sum of this set is \(\sigma(\{3, 4, 6, 7\}) = 20\).

Exercises

  1. How many subsets of \(\{1,2,3,4,5,6,7,8\}\) are there containing exactly 3 elements? (Hint: Use the Subsets command.)

    sage: # edit here

  2. Use the union method to construct the subsets of \(\{1,2,3,4,5,6,7,8\}\) that contain 3 or 5 elements. What is its cardinality?

    sage: # edit here

  3. List all the subsets of \(\{1,3,6,8,10,11\}\) of size three.

    sage: # edit here

  4. Determine the sum of all integers that are the sum of exactly one of the 3-element subsets of \(\{1,3,6,8,10,11\}\).

    sage: # edit here

  5. How many 12-element subsets of \(\{1^2, 2^2, \dots, 24^2\}\) are there?

    sage: # edit here

  6. Determine the sum of all integers that are the sum of exactly one of the 12-element subsets of \(\{1^2, 2^2, \dots, 24^2\}\).

    sage: # edit here
Remark. The Project Euler Problem 201 is to determine the sum of all the integers that are the sum of exactly one of the 50-element subsets of \(\{1^2, 2^2, \dots, 100^2\}\), and to do this in under two minutes of computation time!

Exercise: Derangements

A fixed point of a permutation \(p\) is an element \(i\) such that \(p(i) = i\). A derangement is a permutation that has no fixed points.

  1. Define a function called is_derangement that returns True if \(p\) is a derangement and returns False otherwise.

    sage: # edit here

  2. Use the filter method of Permutations to create a combinatorial class of all the derangements of [1,2,3,4], and list them.

    sage: # edit here

  3. Create a list of the number of derangements of an \(n\)-element set, for \(n = 1, 2, \dots, 7\).

    sage: # edit here

  4. Visit the The On-Line Encyclopedia of Integer Sequences webpage to find a fomula for the number of derangements of an \(n\)-element set, and implement the function.

    sage: # edit here

Exercise: Vexillary involutions

Warning

Combinatorial classes are now deprecated, and will disappear as soon as all derived classes in Sage’s library will have been fixed.

Using the VexillaryInvolutions class above as a guide, create a class called Derangements that inherits from CombinatorialClass and implement the following methods.

  1. __init__(self, n): this method will take as argument a positive integer n , and it will store the value in a data attribute for later access.
  2. __repr__(self): a string representation of the object. The command Derangements(5) should print ‘Derangements of a 5-element set’.
  3. __iter__(self): implement a generator that iterates through all the derangements. ( Hint: In the exercise above you used the filter method to construct derangements; it is okay to use that here.)
  4. __contains__(self, p): implement a method that tests whether p belongs to this combinatorial class (tests whether p is a derangement).
  5. cardinality(self): implement the method cardinality that returns the number of derangements. ( Hint: You should have already implemented the function in the previous exercise.) ( Remark: by default, this method iterates through the iterator to get the cardinality, which can be slow if the class contains a lot of elements.)