Author: Ken Levasseur
Description: Worksheets related to Applied Discrete Structures

# An Introduction to Sets and Combinatorics using SageMath

Here are a few tips on how to get started using Sage to work with sets and combinatorial calculations. For more details on the introductory theory, see Chapters 1 and 2 of Applied Discrete Structures.

## Sets

A set is an expression of the form   set(list).    By wrapping a list with set, the order of elements appearing in the list and their duplication are ignored.    For example, L1 and L2 are two different list, but notice how as sets they are considered equal:

In [ ]:
L1=[3,6,9,0,3]
L2=[9,6,3,0,9]
L1==L2

In [ ]:
Set(L1)==Set(L2)


The standard set operations are all methods and/or functions that can act on Sage sets.

In [ ]:


In [3]:
A=Set(srange(5,50,5))

In [4]:
B=Set(srange(6,50,6))


Intersection:

In [5]:
A & B

{30}

Notice that the union isn't sorted in any obvious way

In [6]:
A | B

{5, 6, 10, 12, 15, 18, 20, 24, 25, 30, 35, 36, 40, 42, 45, 48}

The union operation is also a method, as are the other set operations.

In [7]:
A.union(B)

{5, 6, 10, 12, 15, 18, 20, 24, 25, 30, 35, 36, 40, 42, 45, 48}

Set difference, or complementation:

In [ ]:
Set(srange(0,50)).difference(A)

In [ ]:
U=Set([0,1,2,3])

In [ ]:
subsets(U)


You can easily convert the result to list, but in practice the result is often a very large list.  Not the case here:

In [ ]:
list(subsets(U))


Here is a simple loop using the generator object.

In [ ]:
for a in subsets(U):
print(str(a)+ " has " +str(len(a))+" elements.")


Here is an example where the generator goes through the 32768 different subsets of the integers from 0 to 14 and tallies the cardinalities.

In [ ]:
setsize={}
for a in subsets(srange(0,15)):
if len(a) in setsize:
setsize[len(a)]+=1
else:
setsize[len(a)]=1
setsize.items()


### Set-builder notation in Sage

Syntax for building a set by logical selection from a "universe" is remarkably similar to mathematical notation.   Here the universe is the set {0, 1, 2, ..., 99} and we select the primes from that set.

In [ ]:
Set([x for x in Set(srange(100)) if x.is_prime()])


A list of rational numbers reduced to lowest terms with denominator less than 9 can be generated as follows.

In [ ]:
[a/b for b in srange(9) for a in srange(1,b) if gcd(a,b)==1]


The condition on the greatest common divisor can be dropped if the set wrapper is used since duplicates are ignored.

In [ ]:
Set([a/b for b in srange(9) for a in srange(1,b)])


We define R to the the integers modulo 81, (see Section 11.3 of Applied Discrete Structures).  We then build the list of solutions to the equation  69 x = 15.

In [ ]:
R=Integers(81)

In [ ]:
Set([ x for x in R if R(69)*x == R(15)])


### Cartesian Products

In [ ]:
bits=FiniteEnumeratedSet([0,1])

In [ ]:
B3=cartesian_product([bits,bits,bits])

In [ ]:
B3.list()

In [ ]:
def parity(s):
sl=list(s)
p=0
for k in sl:
p+=k
return p.mod(2)

In [ ]:
parity((1,1,1))


Here, we append a parity bit to each element of B3 to produce eight sequence of four bits, all with even parity.

In [ ]:
for s in B3:
print(tuple(list(s)+[parity(s)]))


## Basic Combinatorial Calculations

The factorial function is method attached to integers

In [ ]:
5.factorial()


Binomial coefficients are computed by the function binomial.

In [ ]:
binomial(52,5)

In [ ]:
var('n')
binomial(n,2)


The binomial_coefficents function creates a dictionary of values.

In [ ]:
binomial_coefficients(8)

In [10]:
large=binomial_coefficients(100)


Here is "100 choose 40."

In [11]:
large[(60,40)]

13746234145802811501267369720
In [12]:
large.values()

[141629804643600, 93206558875049876949581681100, 161700, 132341572939212267400, 38116532895986727945334202400, 13746234145802811501267369720, 1917353200780443050763600, 5670048986634686922786117600, 84413487283064039501507937600, 49378235797073715747364762200, 1345860629046814650, 141629804643600, 66324638306863423796047200, 1095067153187962886461165020, 4998813702034726525205100, 4950, 9013924030034630492634340800, 580717429720889409486981450, 161700, 98913082887808032681188722800, 30664510802988208300, 79776075565900368755100, 75287520, 6650134872937201800, 1345860629046814650, 1977204582144932989443770175, 6650134872937201800, 4950, 28258808871162574166368460400, 1050421051106700, 29372339821610944823963760, 73470998190814997343905056800, 24865270306254660391200, 253338471349988640, 73470998190814997343905056800, 30664510802988208300, 143012501349174257560226775, 3420029547493938143902737600, 1902231808400, 20116440213369968050635175200, 1977204582144932989443770175, 16007560800, 7332066885177656269200, 294692427022540894366527900, 66324638306863423796047200, 3420029547493938143902737600, 7110542499799200, 79776075565900368755100, 186087894300, 4998813702034726525205100, 16007560800, 294692427022540894366527900, 29372339821610944823963760, 242519269720337121015504, 580717429720889409486981450, 100891344545564193334812497256, 38116532895986727945334202400, 84413487283064039501507937600, 253338471349988640, 1050421051106700, 242519269720337121015504, 535983370403809682970, 1, 75287520, 28258808871162574166368460400, 186087894300, 535983370403809682970, 20116440213369968050635175200, 699574816500972464467800, 5670048986634686922786117600, 1917353200780443050763600, 44186942677323600, 24865270306254660391200, 44186942677323600, 3921225, 12410847811948286545336800, 699574816500972464467800, 1, 9013924030034630492634340800, 143012501349174257560226775, 1192052400, 3921225, 1902231808400, 1192052400, 2041841411062132125600, 2041841411062132125600, 1095067153187962886461165020, 49378235797073715747364762200, 17310309456440, 98913082887808032681188722800, 100, 13746234145802811501267369720, 100, 17310309456440, 12410847811948286545336800, 132341572939212267400, 61448471214136179596720592960, 61448471214136179596720592960, 7332066885177656269200, 7110542499799200, 93206558875049876949581681100]
In [ ]: