#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: 9

PLEASE LIST ALL THE QUESTIONS FOLLOWED, AFTER EACH, BY THE ANSWER




Question 1:

Write the proof for the following lemma

Lemma: A tree with n vertices must have n-1 edges 


Answer 1:

Proof: 

We will use the following theorem 

Theorem 4.3: Every non-trivial tree has at least two end vertices.

To prove: Every tree of order n has size n-1.

We proceed with induction on n.

There is only 1 tree of order 1 which has size 0. Hence the lemma holds for n=1. Assume that for some positive integer k, that the size of every tree of order k is k-1. Then, let T be a tree of order k+1. By theorem 4.3, T contains at least two end-vertices. Suppose v is one of the end vertices. Then T'= T - v is a tree of order k. By the induction hypothesis, the size of T' is m=k-1. Since T has exactly one more edge than T', the size of T is m+1 = (k-1) +1 = (k+1) -1 as desired. Hence proved.



Question 2:


What is the OEIS A-number of this sequence?

1,1,3,16,125,1296,16807,1262144,4782969

Answer 2:

A000272: Number of trees on n labeled nodes: n^(n-2) with a(0)=1.



Question 3:


Is this sequence (Number of labelled connected graphs with as many edges as vertices) in the OEIS? What is the A number?


Answer 3:

Yes the sequence is in the OEIS.

A057500 : Number of connected labeled graphs with n edges and n nodes.



Question 4:

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


Answer 4:

r=13



Question 5:


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


Answer 5:

time(TreeSeq(75))
46.625

time(TreeSeq1(75))
.546



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).


Answer 6:

R_e(x)= Sumj(r_e(n)*x^n/n!, n=0..infinity)

The functional equation is:

R(x)= x*(1+R(x)^2/2! + R(x)^4/4! + ...) = x* cosh(R(x))

FunEqToSeq(cosh(z), z, 10); 

First 20 terms of the sequence are :

FunEqToSeq(cosh(z), z, 20); 
[1, 0, 1/2, 0, 13/24, 0, 541/720, 0, 9509/8064, 0, 7231801/3628800, 0, 1695106117/479001600, 0, 567547087381/87178291200, 0, 36760132319047/2988969984000, 0, 151856004814953841/6402373705728000, 0]




Question 7:

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

Answer 7:

coeff(TreeSeqL(27,t)[27],t,6)

147591129548061384922325901312000000


Question 8:

Conjecture an explicit formula for average number of leaves of a labelled tree with n vertices. 



Answer 8:

The formula is 

(n^n) / (n+1)^(n-2) 


Question 9:

What is the limit if you divide by 10? Prove the conjecture.

Answer 9:

limit((n^n)/(((n+1)^(n-2))*n),n=infinity)
infinity