| Hosted by CoCalc | Download
#This file contains some code bits to help point you along to solving some MATH3012 problems with computer assistance #Hit the 'Open in CoCalc' and 'Copy to My Project' buttons above to make a copy of this that you can interact with. #Cocalc is getting slow without a $s subscription :( but you can install Sage on your computer to work faster # Sage has more complete tutorials online: # http://doc.sagemath.org/html/en/tutorial/introduction.html
#--------------------------- #GRAPH THEORY #--------------------------- #Sage is very powerful! Lots of math is already implemented in Sage. You might want to look into graph theory parts! G=Graph(6);G.add_edges([(0,1),(1,2),(3,1),(0,4),(3,4),(1,5)]) G.show() G.is_eulerian() G.is_hamiltonian() G.is_planar(kuratowski=True) G.automorphism_group().cardinality() #Symmetries!
False False (True, None) 4
#Sage can construct graphs from many types of inputs! #Remember our Hogwarts Class Coloring problem? #Over the ordered basis div,pot,trans,care,charms,defense,arith,herbology the adjacency matrix is adj_mat = Matrix( [[0,0,1,1,1,1,1,1],[0,0,1,1,1,0,1,1],[1,1,0,1,1,1,1,1],[1,1,1,0,1,1,1,1],[1,1,1,1,0,1,1,1],[1,0,1,1,1,0,0,1],[1,1,1,1,1,0,0,1],[1,1,1,1,1,1,1,0]] ) hogwarts_sched = Graph(Matrix(adj_mat)) #Sage computes the chromatic number: hogwarts_sched.chromatic_number() #And can visualize! hogwarts_sched.show()
6
#Sage can even find the obstruction to planarity graphs.CompleteGraph(6).show() ans , H =graphs.CompleteGraph(6).is_planar(kuratowski=True) ans H.show()
False
#--------------------------- #GENERATING FUNCTIONS #--------------------------- #In Sage the default algebraic variable is x. #You can write expressions in x: a=1/(1-3*x) #Hit Run to or Shift+Enter execute the command. The horizontal lines define cells that execute separately.
#Sage is built in Python and uses Python syntax and commands #You can find the Taylor series for an expression in x up to arbitrary order a.series(x,5)
1 + 3*x + 9*x^2 + 27*x^3 + 81*x^4 + Order(x^5)
#You can also find a particular coefficient as long as you've expanded the Taylor series past that order #The coefficient of x^4 is given by a.series(x,5).coefficient(x,4)
81
#You'll get a useless big O estimate if you don't expand far enough #(Sidenote: Here the big O is as x->0 instead of n->infinity, so the bigger powers are actually the smaller Os...>:O ) a.series(x,4).coefficient(x,4)
Order(1)
#Sage waits to do any algebraic simplifying or expanding till you tell it to, so if you haven't expanded your function into polynomial terms, you might get the wrong answer. # b=(1+x+x^2)^7 b.coefficient(x^5) b.expand().coefficient(x^5) (1+2*x+x^2).factor()
0 266 (x + 1)^2
#How many games of football? #In american football each team can score a 2 point safety, a 3 point field goal, or a 6 point touchdown. After a touchdown they can try kick for 1 extra point or score a 2 point conversion. #Let's make x be a variable to track the score for Team 1: the Philadelphia Eagles and make a variable y to track the score for Team 2: the New England Patriots. var('y')
y
#Then the generating function to describe points from one scoring event in the game would be: # eagles safety XOR fieldgoal XOR touchdown THEN (no bonus XOR extrapoint XOR 2-pt conversion) XOR (similar for patriots) score_event = x^2 + x^3 + x^6*(1+x+x^2) + y^2 + y^3 + y^6*(1+y+y^2) #Then all the possible football games are made up of any number of scoring events and we use the geometric series trick: football_games = 1/(1-score_event) #We could see the "number of GAMES" meaning the number of sequences of scoring events broken down by the end scores. #Here are the numbers of games with scores less than 6: football_games.taylor((x,0),(y,0),6)
3*x^6 + 3*x^4*y^2 + 2*x^3*y^3 + 3*x^2*y^4 + 3*y^6 + 2*x^5 + 2*x^3*y^2 + 2*x^2*y^3 + 2*y^5 + x^4 + 2*x^2*y^2 + y^4 + x^3 + y^3 + x^2 + y^2 + 1
#I didnt watch the Superbowl LII, but I know the score was eagles 41 to patriots 33. #We can compute the number of ways that might have happened as the coefficient of x^41*y^33 if we get the computer to find the multivariate Taylor expansion up to order 41+33=74 .... football_games.taylor((x,0),(y,0),75).coefficient(x^41*y^33)
756128164919912192
#--------------------------------------- #LINEAR RECURRENCE RELATIONS #--------------------------------------- #Finding roots of polynomials: my_poly=x^5+1 polyroots = my_poly.roots() #Each root is listed with its multiplicity. polyroots #To see a decimal approximation to numbers use the .n() numerical approximation function [foo[0].n() for foo in polyroots]
[(1/4*(-1)^(1/5)*(sqrt(5) + I*sqrt(2*sqrt(5) + 10) - 1), 1), (-1/4*(-1)^(1/5)*(sqrt(5) - I*sqrt(-2*sqrt(5) + 10) + 1), 1), (-1/4*(-1)^(1/5)*(sqrt(5) + I*sqrt(-2*sqrt(5) + 10) + 1), 1), (1/4*(-1)^(1/5)*(sqrt(5) - I*sqrt(2*sqrt(5) + 10) - 1), 1), ((-1)^(1/5), 1)] [-0.309016994374947 + 0.951056516295154*I, -1.00000000000000, -0.309016994374947 - 0.951056516295154*I, 0.809016994374947 - 0.587785252292473*I, 0.809016994374947 + 0.587785252292473*I]
#Finding the solution to a linear recursion with tricky but distinct roots #a(n+3)=a(n+2)+2*a(n+1)-3a(n) and a(0)=0 and a(1)=3 and a(2)=10 char_poly=x^3-x^2-2*x+3 eigenvals=[foo[0] for foo in char_poly.roots()] #General solution is a(x) = c0*(eigenvals[0])^x + c1*(eigenvals[1])^x + c2*(eigenvals[2])^x #Solve for constants from initial conditions A=Matrix([[1,1,1,0],[eigenvals[0], eigenvals[1], eigenvals[2],3],[eigenvals[0]^2, eigenvals[1]^2, eigenvals[2]^2,10]]) Asolved=A.rref() c0=Asolved[0][3] c1=Asolved[1][3] c2=Asolved[2][3] a(x)=c0*(eigenvals[0])^x + c1*(eigenvals[1])^x + c2*(eigenvals[2])^x #Use the .n() command to give decimal approximations to complicated exact expressions a(3).n() #Notice there's some small numerical errors from your computer rounding off things to rational approximations, but #for now at least they are neglectably small! round(a(3).real_part()) 10+2*3-3*0
16.0000000000000 - 1.77635683940025e-15*I
#--------------------------- #PERMUTATION GROUPS #--------------------------- #Use sage to compute the cycle index of a permutation group or all the elements. #Note that sage has different conventions than our text (#1 it doesn't bother listing 1-cycles). Call .cycle_index? to see some documentation #There is also a bug where cycle_index won't work if 0 is being permuted X=Graph(8);X.delete_vertex(0);X.add_edges([(1,2),(1,3),(2,3),(3,4),(4,5),(4,6),(4,7)]) X.show() for foo in X.automorphism_group(): print foo X.automorphism_group().cycle_index()
() (5,6) (6,7) (1,2) (5,6,7) (5,7,6) (1,2)(6,7) (1,2)(5,6) (1,2)(5,6,7) (1,2)(5,7,6) (5,7) (1,2)(5,7) 1/12*p[1, 1, 1, 1, 1, 1, 1] + 1/3*p[2, 1, 1, 1, 1, 1] + 1/4*p[2, 2, 1, 1, 1] + 1/6*p[3, 1, 1, 1, 1] + 1/6*p[3, 2, 1, 1]
#Some famous groups you can call manually sym_hex=DihedralGroup(6) print 'The Group of Hexagon Symmetries has Polya cycle index:' sym_hex.cycle_index() print('\n') var('x1,x2,x3,x4,x6,r,g,b') p(x1,x2,x3,x4,x6)=(x1^6+3*x1^2*x2^2+4*x2^3+2*x3^2+2*x6)/12 # If we substitute ( x_i= r^i + b^i ) we can make a generating function that breaks down the hexagon "necklaces" according # to the number of red and number of blue vertices! print('\nThe number of hexagonal necklaces with red and blue beads has generating function:') p( r+b, r^2+b^2, r^3+b^3, r^4+b^4, r^6+b^6).expand()
The Group of Hexagon Symmetries has Polya cycle index: 1/12*p[1, 1, 1, 1, 1, 1] + 1/4*p[2, 2, 1, 1] + 1/3*p[2, 2, 2] + 1/6*p[3, 3] + 1/6*p[6] (x1, x2, x3, x4, x6, r, g, b) The number of hexagonal necklaces with red and blue beads has generating function: b^6 + b^5*r + 3*b^4*r^2 + 3*b^3*r^3 + 3*b^2*r^4 + b*r^5 + r^6
#Here's a pentagon to get you started! Pentagon = Graph(6); Pentagon.delete_vertex(0); Pentagon.add_edges([(1,2),(2,3),(3,4),(4,5),(5,1)]) Pentagon.show() for foo in Pentagon.automorphism_group(): print foo print('Notice the graph-theoretic symmetries of the 5-cycle graph are the same as the pentagon! Same group!') for foo in DihedralGroup(5): print foo
() (1,2,3,4,5) (2,5)(3,4) (1,2)(3,5) (1,3,5,2,4) (1,5)(2,4) (1,3)(4,5) (1,4)(2,3) (1,4,2,5,3) (1,5,4,3,2) Notice the graph-theoretic symmetries of the 5-cycle graph are the same as the pentagon! Same group! () (1,5)(2,4) (1,2,3,4,5) (1,4)(2,3) (1,3,5,2,4) (2,5)(3,4) (1,3)(4,5) (1,5,4,3,2) (1,4,2,5,3) (1,2)(3,5)