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

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

QUESTION #1:

Write the proof of A tree with n vertices must have n-1 edges with more detail and in your own words.

ANSWER:

First, notice that in a tree there must be a vertex with only one neighbor (leaf). To show this suppose that t is a tree with n vertices. We know that t is connected and without cycles. Assume for the sake of contradiction that t has no leaves. Then, each vertex has at least two neighbors. Start at any vertex and continue to move vertices without every going back an edge, since our tree has a finite number of vertices, it will reach a vertex such that the next edge without repeating will either take you back to a vertex that was covered or a vertex which leads you to a vertex that was covered. This constitutes a cycle and contradicts our assumption that t has no cycles. Therefore, each tree contains a leaf. Whenever we remove a leaf, we get a tree with n-1 vertices. Hence, by induction the tree with n-1 vertices has n-2 edges and the tree with n vertices has n-1 edges after reconnecting the leaf to n-1 vertices tree.

QUESTION #2:

What is the OEIS A-number of 1, 1, 3, 16, 125, 1296, 16807, ...

ANSWER:

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

QUESTION #3:

Is the sequence 0, 0, 1, 15, 222, 3660, 68295, 1436568, ... in the OEIS? What is the A-number?

ANSWER:

A057500; Description: 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?

ANSWER:

r=13 is the smallest r I found such that ATreeSeq(30,r) is not in the OEIS?

QUESTION #5:

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

ANSWER:

Timings:

time(TreeSeq(75));
                             53.406

time(TreeSeq1(75));
                             0.531

The ratio is given by:

evalf(`%%`/%);
                          100.5762712


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). What are the first 20 terms of this sequence? Is it in the OEIS?

ANSWER:

We have R_e(x) = Sum(r_e(n)*x^n/n!, n=0..infinity)
We get a functional equation:
R_e(x) = e^{R_e(x)}

Running FunEqToSeq(e^z, z, 20) we get:
[1, ln(e), (3*ln(e)^2)/2, (8*ln(e)^3)/3, (125*ln(e)^4)/24, (54*ln(e)^5)/5, (16807*ln(e)^6)/720, (16384*ln(e)^7)/315, (531441*ln(e)^8)/4480, (156250*ln(e)^9)/567, (2357947691*ln(e)^10)/3628800, (2985984*ln(e)^11)/1925, (1792160394037*ln(e)^12)/479001600, (7909306972*ln(e)^13)/868725, (320361328125*ln(e)^14)/14350336, (35184372088832*ln(e)^15)/638512875, (2862423051509815793*ln(e)^16)/20922789888000, (5083731656658*ln(e)^17)/14889875, (5480386857784802185939*ln(e)^18)/6402373705728000, (32000000000000000*ln(e)^19)/14849255421]


QUESTION #7:

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

ANSWER:

L := TreeSeqL(27, t);
L0 := subs(t = 6, L);
L0 := [6, 12, 144, 2304, 50400, 1411776, 48129984, 1934019072, 
  89523657216, 4691161267200, 274519958270976, 17744804719054848, 
  1255675925359005696, 96547405732355579904, 
  8015006535674814259200, 714498982934881413758976, 
  68074004438478774239625216, 6903119789099162111539150848, 
  742346625727640108893787652096, 
  84382728191147010631985292902400, 
  10109323543695614740325002065739776, 
  1273134890997306212492176300947013632, 
  168143695228591324687193811144161624064, 
  23238279082671897481956889374338857304064, 
  3354201158680592950211575017526832136192000, 
  504721320438381234462944394796511883612389376, 
  79044165842816694716044003499779078685850599424]


The number of labelled trees with 27 vertices and 6 leaves is: 1411776

QUESTION #8:

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

ANSWER: