Worksheets related to Applied Discrete Structures
An Introduction to Sets and Combinatorics using Sage

# An Introduction to Sets and Combinatorics using Sage

 Author Ken Levasseur Date 2017-01-17T16:29:50 Project f351622c-d261-4717-abee-4c0bfa210e88 Location sage_worksheets/ADS2_Sets_Combinatorics.sagews Original file ADS2_Sets_Combinatorics.sagews

# An Introduction to Sets and Combinatorics using Sage

Here are a few tips on how to get started using Sage to work with sets and combinatorial calculations.

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

L1=[3,6,9,0,3]L2=[9,6,3,0,9]L1==L2
False
set(L1)==set(L2)
True

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

A=set(range(5,50,5))
B=set(range(6,50,6))

Intersection:

A & B
set([30])

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

A | B
set([35, 36, 5, 6, 40, 10, 12, 45, 15, 48, 18, 20, 24, 25, 42, 30])

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

A.union(B)
set([35, 36, 5, 6, 40, 10, 12, 45, 15, 48, 18, 20, 24, 25, 42, 30])

Caution:  sorting a union strips away the set wrapper.

sorted(A|B)
[5, 6, 10, 12, 15, 18, 20, 24, 25, 30, 35, 36, 40, 42, 45, 48]

A strange result:  putting the set wrapper back on unsorts the list.  ????

D2=sorted(union(A,B))set(D2)
set([35, 36, 5, 6, 40, 10, 12, 45, 15, 48, 18, 20, 24, 25, 42, 30])

Set difference, or complementation:

set(srange(0,50)).difference(A)
set([0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49])

U=set([0,1,2,3])
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:

list(subsets(U))
[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3]]

Here is a simple loop using the generator object.

for a in subsets(U):    print(str(a)+ " has " +str(len(a))+" elements.")
[] has 0 elements. [0] has 1 elements. [1] has 1 elements. [0, 1] has 2 elements. [2] has 1 elements. [0, 2] has 2 elements. [1, 2] has 2 elements. [0, 1, 2] has 3 elements. [3] has 1 elements. [0, 3] has 2 elements. [1, 3] has 2 elements. [0, 1, 3] has 3 elements. [2, 3] has 2 elements. [0, 2, 3] has 3 elements. [1, 2, 3] has 3 elements. [0, 1, 2, 3] has 4 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.

isetsize={}for a in subsets(srange(0,15)):    if len(a) in setsize:        setsize[len(a)]+=1    else:        setsize[len(a)]=1setsize.items()
[(0, 1), (1, 15), (2, 105), (3, 455), (4, 1365), (5, 3003), (6, 5005), (7, 6435), (8, 6435), (9, 5005), (10, 3003), (11, 1365), (12, 455), (13, 105), (14, 15), (15, 1)]

### 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.

set([x for x in set(range(100)) if x.is_prime()])
set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])

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

[a/b for b in range(9) for a in range(1,b) if gcd(a,b)==1]
[1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1/8, 3/8, 5/8, 7/8]

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

set([a/b for b in range(9) for a in range(1,b)])
set([4/7, 2/3, 1/3, 1/2, 1/5, 1/4, 3/5, 3/4, 1/8, 6/7, 2/5, 5/7, 5/8, 3/8, 5/6, 4/5, 1/6, 3/7, 1/7, 7/8, 2/7])

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

R=Integers(81)
set([ x for x in R if R(69)*x == R(15)])
set([73, 19, 46])

### Cartesian Products

cartesian_produc
File: /projects/sage/sage-7.3/local/lib/python2.7/site-packages/sage/misc/mrange.py
Signature : cartesian_product_iterator()
Docstring :
Iterate over the Cartesian product.

INPUT:

* "X" - list or tuple of lists

OUTPUT: iterator over the Cartesian product of the elements of X

EXAMPLES:

sage: list(cartesian_product_iterator([[1,2], ['a','b']]))
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]
sage: list(cartesian_product_iterator([]))
[()]
B3=cartesian_product(range(2),range(2))
Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-7.3/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 976, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in File "sage/misc/lazy_import.pyx", line 386, in sage.misc.lazy_import.LazyImport.__call__ (/projects/sage/sage-7.3/src/build/cythonized/sage/misc/lazy_import.c:3636) return self._get_object()(*args, **kwds) TypeError: __call__() takes exactly 2 arguments (3 given)
B3.cardinality()
B3.list()
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
type(B3)
def parity(s):    var('p')    p=0    for k in s:        p+=k    return p.mod(2)
parity([1,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.

for s in B3:   print(s+[parity(s)])
[0, 0, 0, 0] [0, 0, 1, 1] [0, 1, 0, 1] [0, 1, 1, 0] [1, 0, 0, 1] [1, 0, 1, 0] [1, 1, 0, 0] [1, 1, 1, 1]

## Basic Combinatorial Calculations

The factorial function is method attached to integers

5.factorial()
120

Binomial coefficients are computed by the function binomial.

binomial(52,5)
2598960
var('n')binomial(n,2)
1/2*(n - 1)*n

The binomial_coefficents function creates a dictionary of values.

binomial_coefficients(8)
{(5, 3): 56, (2, 6): 28, (7, 1): 8, (8, 0): 1, (4, 4): 70, (6, 2): 28, (1, 7): 8, (0, 8): 1, (3, 5): 56}
large=binomial_coefficients(100)

Here is "100 choose 40."

large[(60,40)]
13746234145802811501267369720
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]