Contact Us!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

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

| Download

Some SageMath code related to Chapters 1 and 2

Views: 1162
Tweet
Share
Share

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

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
{30}

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

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.

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

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]

Set difference, or complementation:

Set(srange(0,50)).difference(A)
{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 0x7f7b4f6fbe10>

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.


setsize={}
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()])
{2, 3, 5, 7, 73, 11, 13, 79, 17, 19, 23, 89, 71, 29, 31, 97, 67, 37, 41, 43, 47, 83, 53, 59, 61}

A list 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/8, 1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 3/8, 5/8, 7/8} 
Set([a/b for b in srange(9) for a in srange(1,b)])
{1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/8, 1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 3/8, 5/8, 7/8}

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.

R=Integers(81)

Set([ x for x in R if R(69)*x == R(15)])
{73, 19, 46}

Cartesian Products

bits=FiniteEnumeratedSet([0,1])

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

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)] 
def parity(s):
    sl=list(s)
    p=0
    for k in sl:
        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(tuple(list(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]