Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download

Project: admcycles

Path: Introduction to computer algebra and mathematical programming/06 Combinatorics.ipynb

Views: ⁵⁹

Visibility: Unlisted (only visible to those who know the link)

Image: ubuntu2004

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.

In [0]:

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

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

In [0]:

T = {2,4,2}
T

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

In [0]:

S.union(T)

In [0]:

S.intersection(T)

In [0]:

S-T

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

In [0]:

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

Exercise

Create the set $E$ of all even numbers $4, \ldots, 100$ .

In [0]:

Create the set $P$ of all primes between $2$ and $100$ .

In [0]:

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

In [0]:

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:

In [0]:

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

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

In [0]:

{(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:

In [0]:

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 \in \{0, \ldots, 100\}$ is the value $\sin(a)$ maximal? What is the value for this $a$ (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.

In [0]:

oeis([3,1,4,1,5])

In [0]:

oeis('A000796')

In [0]:

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:

In [0]:

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

In [0]:

P.cardinality()

In [0]:

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

In [0]:

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 $S$ , i.e. the set of subsets of $S$ .

In [0]:

S = {1,2,3,4}
PS = Subsets(S); PS

In [0]:

PS.cardinality()

In [0]:

for s in PS:
    print(s)

We can also restrict to subsets of a given size:

In [0]:

PS2 = Subsets(S,2); PS2

Exercise

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

Solution (uncomment to see)

Permutations

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

In [0]:

P = Permutations(4); P

In [0]:

list(P)

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

In [0]:

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

Exercise

Consider the following two vectors:

In [0]:

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

For which permutation $\sigma \in S_5$ is the sum $\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 $n$ is a way to write $n$ as a sum of positive integers, regardless of orientation. We can enumerate these as follows:

In [0]:

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):

In [0]:

list(Partitions(5, length=3))

In [0]:

list(Partitions(5, max_part=3))

In [0]:

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 $0$ 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), \ldots$ as solutions):

In [0]:

I = IntegerVectors(5, length=3); I

In [0]:

list(I)

In [0]:

list(IntegerVectors(6,min_part=2))

Exercise

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

Compute the number $J(n)$ of ways that the frog can jump from $0$ to $n$ for $n=1, \ldots, 9$ .
What is the number $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 $S$ as a disjoint union of subsets:

In [0]:

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

Exercise

Compute the numbers $B_n$ of set partitions of $\{1, \ldots, n\}$ for $n=0, \ldots, 9$ .
Find out what the numbers $B_n$ are called.
The numbers $B_n$ have a nice exponential generating series: $B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x -1}\,.$ Use this formula to compute $B_{19}$ .

Solution (uncomment to see)

Exercise

List all partitions $\{1, \ldots, 10\} = \coprod_i S_i$ into disjoint subsets $S_i$ such that all $S_i$ have the same sum (e.g. in the smaller example $\{1,2,3,4\} = \{1,4\} \cup \{2,3\}$ would be a solution, since $1+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:

In [0]:

L = [5,2,3,1,2]

In [0]:

sorted(L)

This doesn't change the list itself:

In [0]:

We can also change the original list by sorting it:

In [0]:

L.sort()
L

We can also sort in the opposite direction:

In [0]:

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:

In [0]:

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

In [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:

In [0]:

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 $n$ elements using $O(n \log(n))$ operations. But it's not, and so we won't.

Assignments

Exercise

Compute the number of conjugacy classes of $S_n$ for $n=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:

In [0]:

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

In [0]:

repr(12)

Solution (uncomment to see)

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

Lecture 6: Combinatorics

Python warmup: sets

Exercise

Python warmup: finding extreme values

Exercise

Combinatorics

Exercise

Products

Question

Subsets

Exercise

Permutations

Exercise

Partitions and integer vectors

Exercise

Set partitions

Exercise

Exercise

Appendix: sorting in Python

Assignments

Exercise

Exercise

Product

Resources

Company

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more, all in one place. Commercial Alternative to JupyterHub.

Lecture 6: Combinatorics

Python warmup: sets

Exercise

Python warmup: finding extreme values

Exercise

Combinatorics

Exercise

Products

Question

Subsets

Exercise

Permutations

Exercise

Partitions and integer vectors

Exercise

Set partitions

Exercise

Exercise

Appendix: sorting in Python

Assignments

Exercise

Exercise

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.