Michael Yen, Assignment 23, 12/6/20 Ok to post HW Lecture 23: Due Dec.6, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment hw23FirstLast.txt Indicate whether it is OK to post 1) Pick a random tree, T, using RandTree(14); of M23.txt and find its Pruffer Code, BY HAND! Check that it agrees with Pruffer(T); T:=RandTree(14); T:={{1, 5}, {2, 6}, {2, 11}, {3, 10}, {4, 9}, {4, 13}, {5, 11}, {6, 7}, {6, 10}, {7, 13}, {8, 12}, {8, 14}, {11, 12}}; 14-8-12 | 1-5-11-2-6-7-13-4-9 | 3-10 a1=5 14-8-12 | 5-11-2-6-7-13-4-9 | 3-10 a2=10 14-8-12 | 5-11-2-6-7-13-4-9 | 10 a3=11 14-8-12 | 11-2-6-7-13-4-9 | 10 a4=4 14-8-12 | 11-2-6-7-13-4 | 10 a5=13 14-8-12 | 11-2-6-7-13 | 10 a6=6 14-8-12 | 11-2-6-7-13 a7=7 14-8-12 | 11-2-6-7 a8=6 14-8-12 | 11-2-6 a9=2 14-8-12 | 11-2 a10=11 14-8-12 | 11 a11=12 14-8-12 a12=8 14-8 Pruffer Code: [5,10,11,4,13,6,7,6,2,11,12,8] Pruffer(T); [5, 10, 11, 4, 13, 6, 7, 6, 2, 11, 12, 8] Agreed 2) Pick a random function from {1,2,..., 15} to itself, using RandF(15), call it f, and find, BY HAND, the doubly-rooted tree that you get with Joyal's mapping. Check that it is the same as Joyal(f). f:=RandF(15); f := [5, 10, 11, 2, 2, 4, 8, 11, 3, 9, 10, 13, 12, 13, 14] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 10 11 2 2 4 8 11 3 9 10 13 12 13 14 ###I use + to denote up arrow and | to denote down arrow### ### | + ### 1->5 | + 6->4->2->10->9->3->11<-8<-7 ^ | | | ----------- 12<->13<-14<-15 Cycles: (12,13) (10,9,3,11) 3 9 10 11 12 13 11 3 9 10 13 12 6->4->2<-5<-1 | + 7->8->11*->3->9->10->13->12** + | 15->14 Joyal(f); {{1, 5}, {2, 4}, {2, 5}, {2, 10}, {3, 9}, {3, 11}, {4, 6}, {7, 8}, {8, 11}, {9, 10}, {10, 13}, {12, 13}, {13, 14}, {14, 15}}, [11, 12] 3) Read and understand procedure Pruffer(T) and InvPruffer(C). Check empirically, for several choices of RandTree(100), that InvPruffer(Pruffer(T))=T T1 := RandTree(100) T1 := {{1, 16}, {1, 71}, {2, 35}, {2, 47}, {3, 8}, {3, 25}, {3, 83}, {4, 39}, {4, 46}, {4, 88}, {5, 44}, {5, 84}, {6, 9}, {6, 97}, {7, 77}, {8, 59}, {9, 46}, {9, 72}, {9, 100}, {10, 40}, {10, 43}, {10, 100}, {11, 70}, {11, 85}, {11, 95}, {12, 20}, {12, 47}, {12, 77}, {13, 39}, {13, 41}, {14, 92}, {15, 44}, {15, 72}, {16, 50}, {16, 75}, {17, 56}, {17, 78}, {18, 51}, {18, 52}, {19, 21}, {19, 42}, {19, 53}, {22, 40}, {22, 93}, {23, 40}, {24, 93}, {25, 49}, {26, 49}, {27, 32}, {27, 49}, {28, 67}, {28, 81}, {29, 74}, {30, 90}, {30, 96}, {31, 74}, {32, 98}, {33, 98}, {34, 61}, {34, 72}, {36, 69}, {36, 70}, {36, 73}, {37, 85}, {37, 86}, {38, 41}, {40, 55}, {40, 91}, {40, 99}, {43, 53}, {43, 77}, {44, 90}, {45, 64}, {47, 80}, {48, 52}, {51, 90}, {52, 58}, {53, 78}, {54, 55}, {57, 70}, {58, 92}, {59, 81}, {60, 87}, {61, 79}, {62, 85}, {63, 66}, {63, 67}, {63, 90}, {64, 68}, {65, 83}, {66, 73}, {67, 71}, {68, 70}, {74, 87}, {75, 82}, {75, 87}, {76, 98}, {89, 91}, {94, 98}} evalb(InvPruffer(Pruffer(T1))=T1); true T2 := RandTree(100); T2 := {{1, 67}, {1, 80}, {2, 12}, {2, 88}, {2, 96}, {3, 46}, {3, 56}, {3, 60}, {3, 69}, {4, 23}, {5, 41}, {6, 52}, {7, 58}, {8, 33}, {8, 67}, {8, 85}, {9, 41}, {9, 43}, {9, 71}, {9, 77}, {9, 91}, {10, 65}, {11, 81}, {12, 25}, {13, 36}, {14, 61}, {14, 93}, {15, 29}, {15, 84}, {15, 100}, {16, 53}, {16, 96}, {17, 94}, {18, 31}, {19, 81}, {20, 31}, {21, 54}, {21, 96}, {22, 38}, {22, 67}, {23, 36}, {23, 59}, {24, 32}, {24, 66}, {26, 30}, {26, 49}, {27, 90}, {28, 35}, {29, 54}, {30, 66}, {30, 92}, {31, 100}, {32, 39}, {33, 65}, {34, 63}, {35, 78}, {37, 49}, {37, 73}, {37, 79}, {37, 82}, {40, 59}, {40, 98}, {42, 53}, {43, 76}, {44, 90}, {44, 98}, {45, 57}, {45, 69}, {46, 75}, {47, 73}, {48, 88}, {49, 62}, {49, 98}, {50, 76}, {51, 55}, {51, 94}, {52, 60}, {52, 71}, {52, 73}, {53, 78}, {57, 72}, {58, 67}, {60, 63}, {61, 74}, {62, 74}, {64, 69}, {64, 70}, {68, 83}, {69, 81}, {73, 95}, {76, 83}, {78, 97}, {79, 94}, {80, 88}, {84, 95}, {86, 92}, {87, 92}, {89, 97}, {93, 99}} evalb(InvPruffer(Pruffer(T2))=T2); true 4) Write a competitor to RandTree, Call it RandTree1(n), that inputs a positive integer n and outputs a random tree with n vertices, but that uses procedure InvPruffer(C) rather than Joyal(f). First generated a random list of length n-2, whose entries are from {1, ..., n}, and then apply InvPruffer to it. By typing time(RandTree(2000)); several times, and your own time(RandTree1(2000)); the same number of times, find out who is faster. Can you explain why? RandTree1:=proc(n) local p,i,roll: p:=[]: roll:=rand(1..n): for i from 1 to n-2 do p:=[op(p),roll()] od: InvPruffer(p): end: RandTree (the original) is faster than my RandTree1 using InvPruffer because InvPruffer uses mex(S) to find the smallest integer not in S. This can be time confusing, since it has to continuously loop over S to find it. Joyal(f) does not have this issue. 5) Write a procedure: EstAveLeaves(n,K), that inputs a positive integer n and a large positive integer K, and outputs an ESTIMATE for the average number of leaves in a labelled tree on n vertices. [Hint: use RandTree(T), K times, finding the number of leaves (using nops(Leaves(T))] Run EstAveLeaves(100,1000) several times. How close is it to 99/exp(1)? (that we got exactly in Lecture 22) EstAveLeaves:=proc(n,K) local i, leaves, T; leaves:=0; for i from 1 to K do T:=RandTree(n); leaves:=leaves+nops(Leaves(T)); od: evalf(leaves/K): end: Trial 1: 37.37800000 Trial 2: 37.32000000 Trial 3: 37.24600000 Average of three trials is 37.31466667 99/exp(1)=36.42006468 Percent Error: (37.31466667-36.42006468)/36.42006468*100=2.456343771% It is pretty close to the exact 99/exp(1). 6) Read and understand this gem, for yet another proof of Cayley's formula. Implement in Maple the function R(e,b) given by equation (*) (Remember to use "option remember"), and verify empirically that it equals indeed b(b+e)e-1 R:=proc(e,b) option remember; local s,ans; if e=0 then ans:=1: else ans:=add(binomial(e,s)*b^s*R(e-s,s), s=1..e): fi: ans: end: f := (e, b) -> b*(e + b)^(e - 1); evalb(f(10,2)=R(10,2)) true evalb(f(100,10)=R(100,10)) true Yes, it does.