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

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


#1. Write the above proof in your own word

#given proof: since there are no cycles, at least on vertex has only one neighbor(Leaf)
#If you remove it, you get a smaller tree with on e less vertex
#and one less edge, by induction for the smaller tree, # of vertices - # of edges = 1
#So as a base case, the tree with one vertex has 0 edge.

#Assume P(n) is true, i.e. for n number of vertices in a tree, number of edges = n-1.
#Now, For P(n+1),
#the number of edges will be (n-1) + number of edges required to add (n+1)th node.
#Every vertex that is added to the tree contributes one edge to the tree.
#Thus, the number of edges required to add (n+1)th node = 1.
#Thus the total number of edges will be (n - 1) + 1 = n -1+1 = n = (n +1) - 1.
#Thus, P(n+1) is true.
#So, by Induction, the lemma is true. QED

####################################################################################

#2. what is the oeis(Anumber) of the seq Treeseq(10)?

#Answer:
#TreeSeq(10);
  [1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000]
#A000272

##################################################################################

#3. Is the seq ATreeseq(30,1) (the number of labelled connected graphs with as 
#many edges as vertices in the oeis? A-number?

#Answer:
#A057500

##################################################################################

#4. what is the smallest r suchat that ATReeSeq(30,r) is not in the oeis?
#optional: submit it

#Answer:
#By searching for the keyword "Number of connected labeled graphs with n nodes and edges."
#The only existing seq were till "n nodes and n+11 edges" which is ATreeSeq(30,12) - A182371
##################################################################################


#5. figure out the ratio of the time it takes between time(TreeSeq(75)) and time(TreeSeq1(75))

#Answer:
time(TreeSeq(75));
                            104.473
time(TreeSeq1(75));
                             1.123
`%%`/%;
                          104.4730000

##################################################################################


#6. Let r_e(n) be the number of root trees where every vertex has an even number of children
#set up a functional eq. for egf of r_e(n)

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

#R_e(x)=Sum(r_e(n)*x^n/n!,n=0..infinity)
#
#What are the first 20 terms of this seq?
#Is it in the oeis

#answer:
#L := FunEqToSeq(cosh(z), z, 20);
     [      1     13     541     9509     7231801     1695106117  
L := [1, 0, -, 0, --, 0, ---, 0, ----, 0, -------, 0, ----------, 
     [      2     24     720     8064     3628800     479001600   

     567547087381     36760132319047     151856004814953841   ]
  0, ------------, 0, --------------, 0, ------------------, 0]
     87178291200      2988969984000       6402373705728000    ]
[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

  ]
#its known as A036778

##################################################################################

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

# we used the labelled seq 
TreeSeqL1 := proc(N, t) local L, z, n; 
L := FunEqToSeq(t - 1 + exp(z), z, N); 
[seq(expand(L[n]*(n - 1)!), n = 1 .. N)]; 
end proc

TreeSeqL1(27, t):
subs(t = 1, %);
 [1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 

   2357947691, 61917364224, 1792160394037, 56693912375296, 

   1946195068359375, 72057594037927936, 2862423051509815793, 

   121439531096594251776, 5480386857784802185939, 

   262144000000000000000000, 13248496640331026125580781, 

   705429498686404044207947776, 39471584120695485887249589623, 

   2315513501476187716057433112576, 

   142108547152020037174224853515625, 

   9106685769537214956799814036094976, 

   608266787713357709119683992618861307]
%[12];
                          61917364224


#figure out the explicit formula ofr average number of leaves

L := TreeSeqL1(10, t);
L0 := subs(t = 1, L);
L0 := [1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000]
L1 := subs(t = 1, diff(L, t));
L1 := [1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489]
[seq(L1[i]/L0[i], i = 1 .. 10)];
  [      4  27  256  3125  46656  823543  16777216  387420489]
  [1, 1, -, --, ---, ----, -----, ------, --------, ---------]
  [      3  16  125  1296  16807  262144  4782969   100000000]
ifactor(%);
 [         2     3     8       5        6    6     7      24  
 [      (2)   (3)   (2)     (5)      (2)  (3)   (7)    (2)    
 [1, 1, ----, ----, ----, ---------, ---------, -----, -----, 
 [      (3)      4     3     4    4       5        18     14  
 [            (2)   (5)   (2)  (3)     (7)      (2)    (3)    

        18  ]
     (3)    ]
   ---------]
      8    8]
   (2)  (5) ]

#So, (n-1)^(n-1)/n^(n-2) is the explicit formula for the above sequence.