#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, 800pm


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.
Definition of a tree: a connected graph with no cycles.
Lemma:A tree with n vertices must have n-1 edges
Given that a certain tree has n vertices, there must be at least n-1 edges in order to satisfy the connectedness requirement, and if there are more than n-1 edges then there is at least one cycle.
Moreover, since there are no cycles, there is at least one leaf, or one vertex connected to the other vertices through one singular edge. If that vertex and edge are removed, then the tree becomes a smaller tree with n-1 vertices and n-1-1 = n-2 edges.
The trivial tree is the tree with 1 vertex and 0 edges, and all trees have an arbitrary positive integer number k of vertices and k-1 edges, which can be constructed through the inductive hypothesis.

2. What is the OEIS A-number of this sequence?
Sequence: [1,1,3,16,125,1296,16807,262144,4782969,100000000]
A000272

3. Is this sequence (number of labeled connected graphs with as many edges as vertices) in the OEIS? If yes, what is the A-number?
Sequence: [0,0,1,15,222,3660,68295,1436568,33779340,880107840]
Yes, this sequence is in the OEIS. The A number is A057500.


-------------------------------------------------
#Can't access M22.txt (Maple code for Lecture 22)
-------------------------------------------------

4. (Optional) What is the smallest r such that ATreeSeq(30,r) is not in the OEIS? Optional: submit it

5. What is the ratio of the time it takes between time(TreeSeq(75)) and time(TreeSeq1(75))?

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 the egf of r_e(n)
R_e(x) = Sum(r_e(n)*x^n/n!,n=0..infinity)
What are the first 20 terms of this sequence? Is it in the OEIS?

7. How many labelled trees are there with 27 vertices and 6 leaves?

8. Challenge: Conjecture an explicit formula for the average number of leaves of a labelled tree with n vertices.
A bigger challenge: What is the limit if you divide by n
An even bigger challenge: prove the conjecture