3115-An Introduction to Sets and Combinatorics using Sage .sagews

An Introduction to Sets and Combinatorics using Sage 

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial -  No Derivative Works 3.0 United States License.

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(srange(5,50,5))

B=set(srange(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=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)

<generator object powerset at 0x10ca426e0>

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)]=1
setsize.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(srange(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 srange(9) for a in srange(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 srange(9) for a in srange(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

B3=CartesianProduct(range(2),range(2),range(2))

B3.cardinality()

8

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)

<class 'sage.combinat.cartesian_product.CartesianProduct_iters'>

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]