#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 Q. #1 for LECTURE 22
#write the above proof in your own words

#ANSWER to Q. #1:	

# There must be one vertex who only has one edge (and thus, one neighbor), called a leaf because the graph is acyclic.  If there was a cycle, this leaf would have a
# second edge which connects to another vertex, thus closing a loop.  This is true for a tree with n vertices.  If we remove this leaf, we lose both one edge and
# one vertex, so (by induction on n-->n-1), we now have a tree with n-1 vertices and n-2 edges.  By our assumption, this is a tree as well, as removing a vertex
# could never possibly result in the CREATION of a cycle.  So, this tree follows the property of having (n-1) vertices and (n-1)-1 edges.

# This continues all the way down to the base case (n=1), which is the singular vertex (no edges), so it is true that it has 1 vertex and 1-1=0 edges.




#ATTENDANCE Q. #2 for LECTURE 22
#OEIS A number of the sequence?

#ANSWER to Q. #2:

# A000272




#ATTENDANCE Q. #3 for LECTURE 22
#Is this sequence in the OEIS? A number?

#ANSWER to Q. #3:

#Yes, A057500





#ATTENDANCE Q. #4 for LECTURE 22
#Smallest r such that ATreeSeq(30,r) is not in the OEIS?

#ANSWER to Q. #4:

#It appears to be r=13




#ATTENDANCE Q. #5 for LECTURE 22
#Ratio of time it atkes between doing treeseq(75) vs treeseq1(75)?

#ANSWER to Q. #5:

#evalf(time(TreeSeq(75))/time(TreeSeq1(75))) = 72.11538462 (72x as long to do it the inefficient way!!)




#ATTENDANCE Q. #6 for LECTURE 22
#Let r_e(n) be the number of rooted trees where very 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); what are the first 20 terms of this sequence? Is it in the OEIS?

#ANSWER to Q. #6:

#Remove the root (gives us x on its own)
#Case 0 --> 1
#Case 1 --> 0 (not even)
#Case 2 --> r_e(x)^2/2!
#Case 3 --> 0
#Case 4 --> r_e(x)^4/4!
...
#We want to multiply it all by x, so let's 

#R_e(X) = Sum(r_e(x)^(2n+1)/(2n+1)!, n=0..infinity)...

#R_e(X) = x*cosh(r_e(x)), then do FunEqToSeq(cosh(z),z,20) and multiply by i! i=1..20

#Sequence: [1, 0, 3, 0, 65, 0, 3787, 0, 427905, 0, 79549811, 0, 22036379521, 0, 
8513206310715, 0, 4374455745966593, 0, 2885264091484122979, 0]

# This is not in the OEIS, but it is if we skip the 0's (elements in the sequence are the (2n+1)th elements) with A036778

# Example tree

#	 4
       /   \
      2     6
     / \   / \
    1   3 5   7




#ATTENDANCE Q. #7 for LECTURE 22
#How many labelled trees are there with 27 vertices and 6 leaves?

#ANSWER to Q. #7:

#coeff(taylor(TreeSeqL(27,t)[27],t=0,28),t,6) = 5466338131409680923049107456000000 labeled trees





#ATTENDANCE Q. #8 for LECTURE 22
#conjecture an explicit formula for the average number of leaves of a labeled tree with n vertices. Limit if you divide by n?

#ANSWER to Q. #8:

#From observing the factored list, we have a formula a(n) = (n-1)^(n-1)/(n)^(n-2)

#The limit if we divide by n as n --> infinity is limit((n-1)^(n-1)/(n*(n)^(n-2)),n=infinity) = e^(-1) or 1/e

#A proof might include different ways to 'choose' how we may distribute our tree in terms of leaves, though I'm unsure of the true
#approach.  1 and 2 are pretty straight forward, and 3 has trees like / (1), \ (1) or /\ (2) = (1+1+2)/3 = 4/3, so some
#idea of base cases may come from these..