2017-02-22.ipynb

Kernel: SageMath (stable)

Math 152 - Intro to Mathematical Software

2017-02-23

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

** Lecture 18: Combinatorics (part 1) **

Sage has very well-developed infrastructure for combinatorics, of which we will only scratch the surface here. For PhD-level research in the subject, it is probably the best software available, open-source or otherwise.

Reference: the Sage combinatorics tutorial http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html

To begin with, recall that the number of ways to make an unordered choice of $k$ distinguishable objects from among $n$ given objects is the binomial coefficient $$\binom{n}{k} = \frac{n!}{k! (n-k)!}$$ where as usual $n! = 1 \times 2 \times \cdots \times n$ denotes the factorial function.

## Count unordered pairs chosen from a set of 6 objects.
binomial(6, 2)

multinomial(2,3,5)

You can use the binomial coefficients to count subsets without generating them. However, if you do actually want to generate the list of $k$-element subsets of a given set, you can do that easily!

l = ["ERC", "Marshall", "Revelle", "Muir", "Warren", "Sixth"]
S = Subsets(l, 2)
print S.cardinality()

S[0]

S[3:5]

S[1]

list(S)

The Subsets function is an example of a structured set construction. Another important example is the Cartesian product; let's see an example based on playing cards.

suits = ["Clubs", "Diamonds", "Hearts", "Spades"]
ranks = ["Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"]
deck = cartesian_product([suits, ranks])

type(deck)

deck[1]

Another example is the set of permutations of a list.

print list(Permutations([1,2,3]))

print list(Permutations([1,2,1,3]))

Exercise for right now: Use the Permutations function to "shuffle" the deck, i.e., pick a random permutation. (Hint: use the random_element method.)

Permutations(deck).random_element()

Subsets(deck, 13).random_element()

Another example is the set of partitions of a given nonnegative integer. Let's illustrate with an example:

print list(Partitions(5))

print list(Partitions(7))

There is a method for counting partitions without enumerating them.

%time n = Partitions(10^12).cardinality()

print N(log(n, 10)) ## This number has over 1 million digits! Let's not print it.

Partitions(10^6).random_element()

One can also enumerate partitions where the parts have fixed size, e.g., making change:

WeightedIntegerVectors(37, [1,5,10,25]).list()

... or solving the (original) Chicken McNuggets problem: https://en.wikipedia.org/wiki/Coin_problem

WeightedIntegerVectors(92, [6,9,20]).list()

Many combinatorics problems lead naturally to integer sequences. These can be looked up in the On-line Encyclopedia of Integer Sequences (OEIS): http://oeis.org; but better yet, this database is integrated into Sage!

oeis([1,2,3,5,8,13], max_results=4) # requires internet access

Maybe a less familiar example: let's count set partitions of {1, ..., n}.

list(SetPartitions([1..4]))

l = [SetPartitions([1..n]).cardinality() for n in [1..10]]
print l

oeis(l, max_results=4)

Aha, let's read about that first one some more.

t = oeis('A000110')

#What methods?
t.name()

t.comments()

Note in passing: many of these constructors are examples of Python iterators, which are effectively implicit tuples: the objects are only produced on demand.

The itertools module provides some useful functionality:

https://docs.python.org/2/library/itertools.html

(Reminder: Sage uses Python 2; some syntax is different in Python 3.)

%python
import itertools
list(itertools.permutations([1, 2, 3, 4]))