by Andrew Johnson
edited by Sara Billey
This worksheet is an introduction to the mathematical field of Combinatorics and an exploration of the combinat library in Sage. Combinatorics has many areas of study and so this tutorial will try to simply get a good foundation. To see the Combinatorics library for Sage go to http://www.sagemath.org/doc/reference/combinat/index.html .
For more general background on Sage see http://wstein.org/books/sagebook/sagebook.pdf and http://docs.python.org/tutorial/ and http://www.diveintopython.net/ and http://interact.sagemath.org/
Sets
We will start with the Sets data structure and its various functions in Sage even though it is not part of the combinat library. In many combinatorial proofs we are often intersted in constructing various sets, counting their elements, and/or creating bijections between 2 or more sets. For this a good understanding of the set implementation in sage will be useful. To create a set one just simply needs to pass a list/tuple or even other sets to the set() command. Reference page for Sage sets http://www.sagemath.org/doc/reference/sage/sets/set.html .
{{{id=77| List1 = [1,2,3,10,'a','b','c',pi,3,2,1] /// }}} {{{id=79| List1 /// [1, 2, 3, 10, 'a', 'b', 'c', pi, 3, 2, 1] }}} {{{id=1| Set1 = Set(List1) Set1 /// {'a', 1, 2, 3, pi, 10, 'c', 'b'} }}}Note that the sets can contain elements that differ in data types. Sage has implementation for all the basic set operations.
{{{id=3| A = Set(range(10)); print A B = Set(range(5,15)); print B #Intersection print "Intersection:", A & B #or A.intersection(B) #Union print "Union:", A | B #or A.union(B) #Difference print "Difference A \ B:", A.difference(B) print "Difference B \ A:", B.difference(A) /// {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} {5, 6, 7, 8, 9, 10, 11, 12, 13, 14} Intersection: {8, 9, 5, 6, 7} Union: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} Difference A \ B: {0, 1, 2, 3, 4} Difference B \ A: {10, 11, 12, 13, 14} }}}You can get a generator for all the subsets for any set as well as the cartesian product for two given sets.
{{{id=8| C = Set([1,2,3]) D = Set([4,5,6]) sub = subsets(C) print "subsets C:", list(sub) Prod = CartesianProduct(C,D) print "Cartesian Product C and D:", list(Prod) /// subsets C: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] Cartesian Product C and D: [[1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]] }}}To get help on a command, type its name and then "?". To see the internal code for a command type the name of the command and "??".
{{{id=82| subset? /// No object 'subset' currently defined. }}} {{{id=81| subset?? ///No object subset
File: /home/sage/sage-5.0/local/lib/python2.7/site-packages/sage/sets/set.py
Type: <class 'sage.sets.set.Set_object_enumerated_with_category'>
Definition: C(x, *args, **kwds=0)
Docstring:
A finite enumerated set.Counting Functions
Put simply, Combinatorics is the study of counting objects, as such there are many tools that we can use to count them. It is sometimes the case that certain number patterns appear frequently for different situations or they are used often enough that they become major fields of study. Luckily Sage has implementation for many of these Combinatorial functions, but lets first start with some basic counting principles.
The factorial of a non-negative integer n, denoted by n!, is the product of all the positive integers less than or equal to n. For example 5!=5*4*3*2*1=120. To calculate the factorial of n in Sage just use the factorial(n) command. By definition we say 0! = 1. An instance of this is given the set of letters {a,b,c,d,e} how many different "words" (for example adbce) can I create? The first letter has 5 choices, the second 4, the third 3, and so on and we see that it is 5!. This is an example of permutations which will be discussed later.
It is often that case that you do not want to multiple all of the integers less than or equal to n, but only the last k integers (n,n-1,n-2,...,n-k+1). You may have noticed that this can be calculated by n!/(n-k)! which is simple enough but sage has no direct way to compute this like factorial(). The simple approach would be to calculate factorial(n) and factorial(n-k) then perform division, but if our k was small such as 2 this can be inefficient. So we will need to use a different function, name the falling_factorial(n,k). To continue with our word example from above for k=3 this is the same as asking how many words can we get from {a,b,c,d,e} that have length 3 to which the answer is 5*4*3 = 60 ways.
{{{id=14| print falling_factorial(10,3) print factorial(10)/factorial(10-3) print falling_factorial(10,0) print falling_factorial(10,10) /// 720 720 1 3628800 }}}Binomial coefficients are another set of commonly used numbers and are very similar to our last function. For positive inters n,k where k is less than or equal to n the binomial coefficient of n and k is n!/[k!(n-k)!], this looks very similar to our previous function but with an extra k! in the divisor. An easy way to see why the k! is needed is to again look at our word problem, note that 'abd' and 'bad' have the same letters but in different order. But if we were more interested in what elements were chosen and ignoring the order in which they were chosen then 'abd' and 'bad are the same, but our falling_factorial() function will count both of these words which is too many and so we must divide by the number of ways we can order a word of size k, which we already found to be k!
There are two functions in Sage that handle binomial coffecients, binomial(n,k) and binomial_coefficients(n). The first function returns a single solution for specific values of n and k whereas the second function returns a dictionary of all the binimial coefficients j and k such that j+k = n.
{{{id=16| print binomial(8,2) print binomial_coefficients(10) /// 28 {(7, 3): 120, (4, 6): 210, (9, 1): 10, (6, 4): 210, (2, 8): 45, (5, 5): 252, (0, 10): 1, (1, 9): 10, (3, 7): 120, (10, 0): 1, (8, 2): 45} }}}Next we have the famous Fibonacci numbers which are defined as the following recurrence relation: For a function F let F(0)=0, F(1)=1 and F(n)=F(n-1)+F(n-2). In Sage this can be found using fibonacci(n) or if you want to go through the first n fibonacci numbers use fibonacci_sequence(n) which returns a generator and you can use the .next() method to get each element. The Fibonacci numbers and binomial coefficients have many interesting relationships with each other which can be found here for those interested.
{{{id=18| print fibonacci(5) print fibonacci(50) G = fibonacci_sequence(10) for i in range(10): print G.next() /// 5 12586269025 0 1 1 2 3 5 8 13 21 34 }}}Other combinatorial functions of interest are the Catalan numbers, Stirling (first/second kind) numbers, Euler numbers, and Bell numbers. We will see later that the Stirling numbers and Bell numbers have their roots in set partitions.
Permutations
A permutation on a set of objects is an arrangement of those objects in some order. In the combinat library for Sage there is conviently a Permutation class that can perform many operations as needed, see it here. An example of a permutation is 4123 from the set {1,2,3,4}. To get a list of all the permutations of a set you can call Permutations(n) where n is an integer, list, set, or string. The elements of the list are of type Permutation_Class.
The individual elements of these lists have data type Permutation_Class that also have many useful functions we will explore later.
What the function actually returns is a generator G which will produce the desired permutations as necessary. Many combinatorial commands in Sage return generators and knowing how to iterate through these lists is important. One way to get these elements is with the G.list() command which returns a list of all the elements in the generator but this can be terribly inefficient for large lists. Another way to retrieve elements is to use list syntax g[i] (zero-based indexing) and in combination with G.cardinality() it is a good way to iterate over the elements without converting G to a list.
While the above method is valid it can be inefficient if the cardinality method is hard to calculate. 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. We will perform the above code again but using these methods.
For a set with n elements, the total number of permutations can be found by first choosing an element to take the first spot which can be done in n ways, for the second element n-1 ways, and so on and therefore the total number of permutations is n*(n-1)*(n-2)...*1 = factorial(n). Any set that is an ordering on n elements is called the symmetric group, Sn, of that set. The cardinality of any Sn is factorial(n) for any set of n elements. For this tutorial define [n] to be the set of the first n integers {1,2,...,n}.
{{{id=24| L = Permutations(8) #Permutations of [8] L.cardinality() == factorial(8) /// True }}}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). If you recall from the Counting Functions section of this tutorial we used a falling_factorial function, it should be readily seen that the number of k-permutations on n elements is precisely the same as the value we get from our function for the same values of n and k.
To create an individual element of a Permutation_Class object you can simply do the following.
{{{id=26| p = Permutation([1,3,2,4]) p /// [1, 3, 2, 4] }}}Permutation_Class objects have many useful methods to learn details about the permutation you created. For example 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 i<j>k.
{{{id=28| print p.number_of_fixed_points() print p.number_of_peaks() /// 2 1 }}}For those more knowledgeble in the field you can even get a list of permutations that avoid certain patterns or check if a permutation does avoid a pattern. It is obvious that if we remove all the permutations that have a pattern then we will have fewer elements then that of the symmetric group of n.
Set Partitions
A partition of a set X divides or breaks up X into smaller sets in such a way that no two sets have a common element and the union of all of these sets gives us back the original X. For example consider the set {1,2,3}, this set can be broken into the following two parts {1,3} and {2}. This of course is not the only way to break up this set into two parts. To get all the partitions of a set in Sage use the SetPartitions(n) where n is an integer, string, list, or a set.
If you are interested only in partitions of k many parts then you can simply do the following.
If you wish to be really specific on how you partition your set you can pass as a second arguement a list instead of an integer. For example if you want to partition [5] into 3 sets such that one set has 3 elements and the other two have 1 element pass the list [3,1,1]. It is important that the list be in descending order otherwise you will get an error.
There are two combinatorial functions that are concerned with set partitions, Stirling numbers of the second kind and Bell numbers. The Stirling numbers count the number of partitions of [n] into k parts while Bell numbers counts all the possible partitions of [n]. In Sage these numbers can be retrieved with stirling_number2 and bell_number. To show these equalities we will count the elements ourselves.
{{{id=73| count = 0 A = SetPartitions(6,3) #Partitions of [10] into 3 parts g = A.first() while(g): count+=1 g = A.next(g) print stirling_number2(6,3) == count count = 0 B = SetPartitions(6) #Partitions of [10] g = B.first() while(g): count+=1 g = B.next(g) print bell_number(6) == count /// True ^C Traceback (most recent call last): print stirling_number2(6,3) == count File "", line 1, inInteger Partitions
Partitioning an integer n is to find a list of positive integers so that their sum is n. For example [3,1] is a partition of 4 since 3+1=4 and so is [2,2]. The lists [3,1] and [1,3] are the same partitions and so the lists are are required to be in decreasing order so as to prevent multiples of the same partition. The Partitions class in Sage can easily handle our partitioning needs and it is more extensive then the SetPartitions class.
If you want partitions of a specific length (the number of parts) you must do the following
{{{id=46| print Partitions(7,length = 3).list() print Partitions(7,length = 3).cardinality() print type(Partitions(7,length = 3)) /// [[5, 1, 1], [4, 2, 1], [3, 3, 1], [3, 2, 2]] 4If the ordering of the parts is important you can instead use OrderedPartitions(). The arguements however are different and you can only specify how many parts are in your partition, default being None.
{{{id=50| print OrderedPartitions(5).list(), "\n" print OrderedPartitions(5,2).list() /// [[5], [4, 1], [3, 2], [3, 1, 1], [2, 3], [2, 2, 1], [2, 1, 2], [2, 1, 1, 1], [1, 4], [1, 3, 1], [1, 2, 2], [1, 2, 1, 1], [1, 1, 3], [1, 1, 2, 1], [1, 1, 1, 2], [1, 1, 1, 1, 1]] [[4, 1], [3, 2], [2, 3], [1, 4]] }}}There are otherways to specify how you wish to construct your partitions but I will not go over them. If you wish to work with a specific partition you can use the Partition(n) method where n is a list in decreasing order to create a Partition_Class object which also has many useful functions. A couple of them are the ferrers_diagram() and conjugate() methods. The Ferrers diagram for a partition is a diagram so that each part ai has ai boxes (or in Sage *’s) in the ith row. The conjugate of a partition p is the partition whose Ferrer's diagram is the reflection across the diagnol of p's Ferrer's diagram.
{{{id=52| p = Partition([4,3,2]) print p print p.ferrers_diagram(), "\n" print p.conjugate() print p.conjugate().ferrers_diagram() /// [4, 3, 2] **** *** ** [3, 3, 2, 1] *** *** ** * }}}It is important to note that ferrers_diagram.() returns a string containing new line chars.
{{{id=54| Partition([4,3,2]).ferrers_diagram() /// '****\n***\n**' }}}Integer Compositions
Integer compositions are very similar to integer partitions. A composition of n is a sequence of positive integers such that their sum is n and the ordering of the integers matter, so it is very much like the OrderedPartitions mentioned preiously. If there is one or more zero elements in the sequence then it is called a weak composition of n. Similarily as for partitions you can designate any constraints you wish in your compositions.
{{{id=56| c = Composition([1,3,2,1,5]) print c print type(c), "\n" L = Compositions(5) print L.list() print L.cardinality() print type(L), "\n" M = Compositions(5,length=2) print M.list() print M.cardinality() print type(M) /// [1, 3, 2, 1, 5]The number of compositions of n into k non-empty parts is binomial(n-1,k-1) and the total number of compositions is 2n-1 , which can be proven easily by taking the summation of binomial(n-1,k-1) from k=1 to k=n and using binomial coefficient identities.
{{{id=59| print Compositions(10, length = 5).cardinality() == binomial(10-1,5-1) print Compositions(10).cardinality() == 2^(10-1) /// True True }}} {{{id=61| /// }}} {{{id=87| /// }}}If you wish to be really specific on how you partition your set you can pass as a second arguement a list instead of an integer. For example if you want to partition [5] into 3 sets such that one set has 3 elements and the other two have 1 element pass the list [3,1,1]. It is important that the list be in descending order otherwise you will get an error.
{{{id=51| print SetPartitions(5,[3,1,1]).list() print SetPartitions(5,[3,1,1]).cardinality() /// [{{2}, {3, 4, 5}, {1}}, {{2, 4, 5}, {3}, {1}}, {{2, 3, 5}, {4}, {1}}, {{5}, {2, 3, 4}, {1}}, {{1, 4, 5}, {2}, {3}}, {{4}, {1, 3, 5}, {2}}, {{1, 3, 4}, {5}, {2}}, {{4}, {3}, {1, 2, 5}}, {{5}, {3}, {1, 2, 4}}, {{4}, {5}, {1, 2, 3}}] 10 }}} {{{id=53| /// }}}Stanley Symmetric Functions
For each permutation there exists a Stanley symmetric function.
{{{id=62| G = WeylGroup(['A',3]) /// }}} {{{id=63| w = G.from_reduced_word([3,2,3,1]) /// }}} {{{id=64| w /// [0 1 0 0] [0 0 0 1] [0 0 1 0] [1 0 0 0] }}} {{{id=65| f=w.stanley_symmetric_function() /// }}}Symmetric Functions
A symmetric function is a power series in countably many variables which is invariant under transposition of any two variables. The symmetric functions form a ring under usual addition and multiplication of power series. There are several important bases for this ring. Here is a brief start computing symmetric function expansions.
Quasisymmetric Functions
A quasisymmetric function is a power series in countably many variables which is invariant under shifts of the variables. The quasisymmetric functions form a ring under usual addition and multiplication of power series. There are several important bases for this ring. Here is a brief start computing quasisymmetric function expansions.
{{{id=68| QSym=QuasiSymmetricFunctions(QQ) /// }}} {{{id=83| QSym.inject_shorthands() /// Injecting M as shorthand for Quasisymmetric functions over the Rational Field in the Monomial basis Injecting F as shorthand for Quasisymmetric functions over the Rational Field in the Fundamental basis }}} {{{id=71| F(f) /// F[1, 3] + F[2, 2] + F[3, 1] }}} {{{id=72| #QSym? /// }}} {{{id=84| /// }}}