| Hosted by CoCalc | Download
Kernel: SageMath 9.5

Lecture 6: Combinatorics

References:

Summary:
We start by recalling the Python datatype of sets and showing a nice trick for finding extreme values of functions on a finite set. Then we discuss useful functions in combinatorics, including cartesian products, how to enumerate subsets, partitions and various types of integer vectors. We also show how to use the online encyclopedia of integer sequences to identify interesting sequences of numbers.

Python warmup: sets

One of the basic data types in Python are sets, which are unordered collections of objects.

S = {7,3,5,2} S

If we list an element multiple times, it is still only recorded once in the set:

T = {2,4,2} T

We can form unions, intersections and relative complements of sets:

S.union(T)
S.intersection(T)
S-T

An important way to create sets is to obtain them by converting a list (or tuple) into a set:

W = set([sin(pi*t/2) for t in range(100)]) W

Exercise

  • Create the set EE of all even numbers 4,,1004, \ldots, 100.

  • Create the set PP of all primes between 22 and 100100.

  • Check the Goldbach conjecture ("Every even number nn greater than 22 is the sum of two primes") for n100n \leq 100.
    Hint: If only there was a method to check whether a set is a subset of another set.

Solution (uncomment to see)

One final word of warning: elements of a set must be hashable. Here a hash is an integer assigned to a Python object, only depending on its value, so that (hopefully) two objects are equal only if their hashes are equal. An example of an unhashable type are lists, which is why the following does not work:

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

This could be repaired by using a tuple, i.e. a list that cannot be changed:

{(1,2),(3,4)}

Python warmup: finding extreme values

In one exercise below (but also more generally) we encounter the following situation: we have list (or set) L and a function f from L to the real numbers, and want to find an element l such that f(l) is minimal (or maximal). The following is a nice trick to find such an element:

L = [(p,q) for p in range(20) for q in range(1,20)] f = lambda x,y : abs(pi - x / y) # the function (x,y) -> |pi - x/y| min((f(p,q), p, q) for p, q in L)

This uses that when ordering tuples (such as (f(p,q), p, q)) and finding the minimum, Python will first sort by the first entry, and only for equal first entries start sorting by the second entry etc.

Exercise

For which integer a{0,,100}a \in \{0, \ldots, 100\} is the value sin(a)\sin(a) maximal? What is the value for this aa (approximately)?

Solution (uncomment to see)

Combinatorics

Below we will see different ways of enumerating certain objects (such as partitions, integer vectors with given sums, permutations etc.). One very useful tool when studying combinatorics is the On-line Encyclopedia of Integer Sequences. This is a database of meaningful sequences of integers. The idea is: if you come across some sequence of numbers and wonder whether there is a pattern explaining them, you can look up this sequence in the OEIS database and check whether it appears somewhere.

oeis([3,1,4,1,5])
oeis('A000796')
vector(oeis('A000796').first_terms()) # using vector to avoid long output

Exercise

What is the next element of the sequence

0, 1, 5, 14, 30, 55, 91, 140, 204, 285, 385, 506 ?

Solution (uncomment to see)

Products

A basic operation in enumerative combinatorics is the cartesian product of sets:

C = {'red', 'blue', 'green'} N = {1,2,3,4} P = cartesian_product([C,N]); P
P.cardinality()
list(P)

Instead of an exercise, let's just show a fun application:

Question

Can you insert operations +, *, - in the equation below such that it becomes true?

13 _ 9 _ 4 _ 6 _ 21 = 208
ops = {'+', '*', '-'} for o1, o2, o3, o4 in cartesian_product(4*[ops]): st = '13'+o1+'9'+o2+'4'+o3+'6'+o4+'21' if eval(st) == 208: print(st+' = 208')

Subsets

A second operation is forming the power set of SS, i.e. the set of subsets of SS.

S = {1,2,3,4} PS = Subsets(S); PS
PS.cardinality()
for s in PS: print(s)

We can also restrict to subsets of a given size:

PS2 = Subsets(S,2); PS2

Exercise

Consider the alternating group A4A_4 and let SA4S \subseteq A_4 be a subset of two different elements of A4A_4, chosen uniformly at random. Compute the probability P(S generates A4). \mathbb{P}(S\text{ generates }A_4). Remark: Considering more generally the group AnA_n, this probability tends to 11 as nn \to \infty, as proven by Dixon. Replacing AnA_n by SnS_n, the probability tends to 3/43/4. Can you see why it can't be greater than 3/43/4?

Solution (uncomment to see)

Permutations

Given n1n \geq 1 we can list all permutations of the set {1,,n}\{1, \ldots, n\}:

P = Permutations(4); P
list(P)

We can also look at permutations of any other set/list:

Q = Permutations([3,4,5]) list(Q)

Exercise

Consider the following two vectors:

A = (2,5,7,12,34) B = (1,3,6,7,11)

For which permutation σS5\sigma \in S_5 is the sum i=15AiBσ(i) \sum_{i=1}^5 A_i B_{\sigma(i)} minimal?
Optional: Can you make a guess, even before computing the answer?

Solution (uncomment to see)

Partitions and integer vectors

We have already seen that a partition of nn is a way to write nn as a sum of positive integers, regardless of orientation. We can enumerate these as follows:

P = Partitions(5) list(P)

There are also several optional arguments that can restrict the shape of the partition (see the documentation of Partitions for more details):

list(Partitions(5, length=3))
list(Partitions(5, max_part=3))
list(Partitions(5, max_part=3, min_part=2))

We can also look at the related problem where the order of the summands matters. In other words, of enumerating vectors of integers summing to a given number. Here, since 00 counts as an integer, we have to either restrict the length of the vector, or give some minimal part in order to obtain a finite set (otherwise we have (n),(n,0),(n,0,0),(n), (n,0), (n,0,0), \ldots as solutions):

I = IntegerVectors(5, length=3); I
list(I)
list(IntegerVectors(6,min_part=2))

Exercise

A frog sits on the origin of the real axis and wants to hop to the number nn. It always jumps in positive direction, and its jumps can either have length 11 or length 22.

  • Compute the number J(n)J(n) of ways that the frog can jump from 00 to nn for n=1,,9n=1, \ldots, 9.

  • What is the number J(n)J(n) in general? Can you see a proof?

Solution (uncomment to see)

Set partitions

Finally, we can enumerate all ways of writing a given set SS as a disjoint union of subsets:

C = SetPartitions([1,2,3]) list(C)

Exercise

  • Compute the numbers BnB_n of set partitions of {1,,n}\{1, \ldots, n\} for n=0,,9n=0, \ldots, 9.

  • Find out what the numbers BnB_n are called.

  • The numbers BnB_n have a nice exponential generating series: B(x)=n=0Bnn!xn=eex1. B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x -1}\,. Use this formula to compute B19B_{19}.

Solution (uncomment to see)

Exercise

List all partitions {1,,10}=iSi \{1, \ldots, 10\} = \coprod_i S_i into disjoint subsets SiS_i such that all SiS_i have the same sum (e.g. in the smaller example {1,2,3,4}={1,4}{2,3}\{1,2,3,4\} = \{1,4\} \cup \{2,3\} would be a solution, since 1+4=2+31+4=2+3).

Solution (uncomment to see)

Appendix: sorting in Python

For some computations it can be useful to sort elements in a list. This comes in two variants: firstly, we can create a new list, which is the sorted version of the old one:

L = [5,2,3,1,2]
sorted(L)

This doesn't change the list itself:

L

We can also change the original list by sorting it:

L.sort() L

We can also sort in the opposite direction:

sorted(L, reverse=True)

And finally, we can specify a key function ourselves. This is a function which sends the elements of our list to numbers, and the list is then sorted in increasing order of these numbers:

L = [(1,0), (0,2), (4,-1)] sorted(L, key = lambda v : v[0])
sorted(L, key = lambda v : v[0]+v[1])

Here we used the a lambda-function, which is a short way to define a function. For example, the following two constructions define the same functions:

f1 = lambda a,b : a+b def f2(a,b): return a+b

If this was a very serious lecture on computer algebra, I could discuss some sorting algorithms and how they allow to sort a list with nn elements using O(nlog(n))O(n \log(n)) operations. But it's not, and so we won't.

Assignments

Exercise

  • Compute the number of conjugacy classes of SnS_n for n=1,,6n=1, \ldots, 6.

  • Do you know (or can you find out) what this sequence of integers is?

Solution (uncomment to see)

Exercise

Recall the following question we saw above:

Can you insert operations +, *, - in the equation below such that it becomes true?

13 _ 9 _ 4 _ 6 _ 21 = 208

Write a function taking a list L (like [13,9,4,6,21]) and an integer s (like 208) which prints out all possibilities of combining the elements of L using +,*,- and obtaining the number s.
Hint: Some useful functions:

''.join(['Hello', ' wor', 'ld'])
repr(12)

Solution (uncomment to see)