#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 ----------------------------------- Attendance Question 1: Write the above proof (if possible with more details) in your own words. We prove that a tree with n vertices must have n-1 edges by induction. As a base case, note that a tree with 1 vertex has 0 edges which matches the above statement. Now, we assume that a tree with k vertices has k-1 edges. We need to show that a tree with k+1 vertices has k edges. Suppose we have a tree with k vertices with k-1 edges and we wish to connect a k+1th vertex. There has to be at least one edge between the new vertex and the tree in order for the new graph to be connected. Additionally, there can't be more than one edge between the new vertex and the tree because then that would create a cycle. Therefore, the new graph can only be a tree if the new vertex is connected with 1 edge to the old tree (i.e. the new vertex becomes a leaf). Since we've shown that a tree with k+1 vertices must have k edges, we have proven the statement as desired. ----------------------------------- Attendance Question 2: What is the OEIS A-number of this sequence? A272. ----------------------------------- Attendance Question 3: Is this sequence (number of labelled connected graphs with as many edges as vertices) in the OEIS? What is the A-number? It is in the OEIS as A57500. ----------------------------------- Attendance Question 4: What is the smallest r such that ATreeSeq(30,r) is not in the OEIS? ATreeSeq(30,2) = A61540 ATreeSeq(30,3) = A61541 ATreeSeq(30,4) = A61542 ATreeSeq(30,5) = A61543 ATreeSeq(30,6) = A96117 ATreeSeq(30,7) = A61544 ATreeSeq(30,8) = A96150 ATreeSeq(30,9) = A96224 ATreeSeq(30,10)= A182294 ATreeSeq(30,11)= A182295 ATreeSeq(30,12)= A182371 The smallest r such that ATreeSeq(30,r) is not in the OEIS is r=13. ----------------------------------- Attendance Question 5: What is the ratio of the time it takes between time(TreeSeq(75)); and time(TreeSeq1(75)); time(TreeSeq(75)) = 46.375 time(TreeSeq1(75)) = .531 TreeSeq took ~87.335 times as long as TreeSeq1 did. ----------------------------------- Attendance Question 6: Let r_e(n) be the number of rooted 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? Removing the root Case 0: Empty tree, egf is x^0/0! = 1 Case 1: There are two components, egf is R_e(x)^2/2! Case 2: There are four components, egf is R_e(x)^4/4! ... The root itself is a rooted tree with 1 vertex so the egf is x So, R_e(x) = x * (1 + R_e(x)^2/2! + R_e(x)^4/4! + ...) R_e(x) = x*cosh(R_e(x)) L := FunEqToSeq(cosh(z),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] This sequence itself is not in the OEIS, but the sequence without the 0s is in the OEIS as A36778: number of labeled rooted trees on 2n+1 nodes each node having an even number of children as desired. ----------------------------------- Attendance Question 7: How many labelled trees are there with 27 vertices and 6 leaves? coeff(TreeSeqL(27,t)[27],t,6) 5466338131409680923049107456000000 ----------------------------------- Attendance Question 8: Challenge: Conjecture an explicit formula for the average number of leaves of a labelled tree with n vertices. Let a(n) = the average number of leaves of a labelled tree with n vertices. A conjecture would be a(n) = (n-1)^(n-1)/(n^(n-2)). Alternatively, (n-1) * ((n-1)/n)^(n-2). Bigger Challenge: What is the limit if you divide by n? If you divide by n, we would have ((n-1)/n)^(n-1)). Finding the limit as n goes to infinity of that is equivalent to finding the limit as n goes to infinity of (n/(n+1))^n. Since we know e = lim (1 + 1/n)^n = lim ((n+1)/n)^n, it follows that the limit of (n/(n+1))^n is 1/e. Biggest Challenge: Prove the conjecture. The average number of leaves of a labelled tree with n vertices can be found by dividing the total number of leaves of all labelled trees with n vertices over the total number of labelled trees with n vertices. The total number of labelled trees with n vertices is n^(n-2) as we already know by Cayley's Formula. I've gotten stuck on trying to show the total number of leaves across all labelled trees with n vertices is (n-1)^(n-1). My idea was to use strong induction perhaps to get to that conclusion but I'm unsure about the details of how that would work.