#ATTENDANCE QUIZ FOR LECTURE 22 of Dr. Z.'s Math454(02) Rutgers University # Please Edit this .txt page with Answers #Email ShaloshBEkhad@gmail.com #Subject: p22 #with an attachment called #p22FirstLast.txt #(e.g. p22DoronZeilberger.txt) #Right after finishing watching the lecture but no later than Nov. Dec. 1, 2020, 8:00pm THE NUMBER OF ATTENDANCE QUESTIONS WERE: 8 PLEASE LIST ALL THE QUESTIONS FOLLOWED, AFTER EACH, BY THE ANSWER 1) Write the above proof (if possible with more details) in your own words. Proof: since there are no cycles, at least one vertex has only one neighbor Such a vertex is a leaf If you remove it, you get a smaller tree with one less vertex and one less edge, by induction for the smaller tree number of vertices-number of edges is 1 Base case: tree with 1 vertex has 0 edges 1-0=1 We will prove by induction that: a tree with n vertices must have n-1 edges Base Case: A tree with 1 vertex has 0 edges. 1-1=0, so the base case is satisfied. Inductive Hypothesis. Assume the claim hold true for k vertices, aka a tree with k vertices has k-1 edges. It will suffice to show the claim still holds for k+1 vertices. Inductive Step: For the (k+1)th vertex being added to the tree, we know that it must be a leaf node. This is because there are no cycles in a tree, so the new node cannot have any children. If the (k+1)th node had children it would mean that there would be an edge to an already existing node (because only one new node was added), leading to a cycle. The leaf node must also have only one parent or else this would also be a cycle. Thus there is only one edge being added to the tree, from the (k+1)th node's parent to the (k+1)th node. Then the total number of edges for this new tree is (k-1)+1=k, which is equal to (k+1)-1. Now we have proved the claim. 2) What is the OEIS A-number of this sequence? TreeSeq(10); [1,1,3,16,125,1296,16807,262144,4782969,100000000] A000272 3) Is this sequence (number of labelled connected graphs with as many edges as vertices) in the OEIS? What is the A-number? ATreeSeq(30,1) 0,0,1,15,222,3660,68295,1436568... Yes, A057500 4) What is the smallest r such that ATreeSeq(30,r) is not in the OEIS? Optional: Submit it r=13 5) What is the ratio of the time it takes between time(TreeSeq(75)); AND time(TreeSeq1(75)); 45.890/0.546=84.04761905 TreeSeq takes much longer than TreeSeq1. 6) Let r_e(n) be the number of roots trees where every vertex has an even number of children Set up a functional equation for egf of r_e(n) R_e(x)=Sum(r_e(n)*x^n/n!,n=0..infinity) 7 / \ 5 9 What are the first 20 terms of this sequence? Is it in the oeis? r_e(n)=x*(R(x)^2/2! + R(x)^4/4!+...)= x*cosh(R(x)) L:=FunEqToSeq(add(z^(2*i)/(2*i)!,i=0..10),z,20): [seq(L[i]*i!,i=1..20)]; [1, 0, 3, 0, 65, 0, 3787, 0, 427905, 0, 79549811, 0, 22036379521, 0, 8513206310715, 0, 4374455745966593, 0, 2885264091484122979, 0] No, not in the OEIS. 7) How many labelled trees are there with 27 vertices and 6 leaves? coeff(TreeSeqL(27, t)[27], t, 6) 147591129548061384922325901312000000 8) Challenge: Conjecture an explicit formula for the average number of leaves of a labelled tree with n vertices Bigger Challenge: What is the limit if you divide by n an even bigger challenge: prove the conjecture