#ATTENDANCE QUIZ FOR LECTURE 23 of Dr. Z.'s Math454(02) Rutgers University

# Please Edit this .txt page with Answers

#Email  ShaloshBEkhad@gmail.com 
#Subject: p23
#with an attachment called
#p23FirstLast.txt
#(e.g. p23DoronZeilberger.txt)

#Right after finishing watching the lecture but no later than Dec. 4, 2020, 8:00pm


THE NUMBER OF ATTENDANCE QUESTIONS WERE: 3

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

QUESTION #1:

Use Lagrange Inversion formula to find an explicit expression for the coeff. of x^n in the power series of u(x) that satisfies the functional equations:
(i) u(x) = x*(1+u(x))^2
(ii) u(x) = x*(1+u(x))^3
(ii) For any positive integer k, u(x) = x*(1+u(x))^k

ANSWER:

(i)

We have PHI(z) = (1+z)^2.
The coefficient of x^n is given by:
(1/n) * (Coeff z^{n-1} in (1+z)^{2n}).

By the binomial theorem, (1+z)^{2n} = Sum(binomial(2n,k)*z^k, k=0..2n).
When k=n-1, the coefficient of z^{n-1} is binomial(2n, n-1).

Hence, the coefficient of x^n is:
(1/n)*binomial(2n, n-1) =
(2n)!/n!*(n+1)!

(ii)

We have PHI(z) = (1+z)^3.

Following part (i), we have by the binomial theorem, 
(1+z)^{3n} = Sum(binomial(3n,k)*z^k, k=0..3n).

When k=n-1, the coefficient of z^{n-1} is binomial(3n, n-1).

Hence, the coefficient of x^n is:
(1/n)*binomial(3n, n-1) = 
(3n)!/n!*(2n+1)!

(iii)

We can already see the pattern from parts (i) and (ii).
(1+z)^{kn} = Sum(binomial(kn,i)*z^i, i=0..3n).

When i=n-1, the coefficient of z^{n-1} is binomial(kn, n-1).

Hence, the coefficient of x^n is:
(1/n)*binomial(kn, n-1) = 
(kn)!/n!((k-1)n+1)!


QUESTION #2:

Let F = [13, 7, 15, 10, 13, 16, 6, 2, 11, 12, 4, 6, 5, 11, 16, 13].

(i) Draw the Directed graph
(ii) Find the Doubly-rooted tree that is outputted by the Joyal Bijection
(iii) Check that is as Joyal(F).

ANSWER:

(i)

		1->13<->5		
		    ^
		    |	          	
	8->2->7->6->16<-15<-3
	         ^	
	         |
  9->11->4->10->12
      ^		  	
      |
     14

(ii)

Cycles: (5,13,5)
This Permutation: Pi(5)=13, Pi(13)=5
5  13
13 5

The Doubly rooted tree:

		   1
		   |
		   v	
		   13*<->5**		
		    ^
		    |	          	
	8->2->7->6->16<-15<-3
	         ^	
	         |
  9->11->4->10->12
      ^		  	
      |
     14	


(iii) Running Joyal(F), we get:

Joyal(F);
 {{1, 13}, {2, 7}, {2, 8}, {3, 15}, {4, 10}, {4, 11}, {5, 13}, 
   {6, 7}, {6, 12}, {6, 16}, {9, 11}, {10, 12}, {11, 14}, 
   {13, 16}, {15, 16}}, [13, 5]

This is the same as above. 13 is the first root and 5 is the second root.


QUESTION #3:

		    13
		    |
		    v	
		    2	
		    |	
		    v				Code so far: [2, 4, 11]
	9->8->7->6->3->10->11->4
	         |
                 v
                 12

Find this. Find the Pruffer Code of the labelled tree.

ANSWER:



		    13
		    |
		    v	
		    2	
		    |	
		    v				Code so far: [2, 4, 11, 8]
	9->8->7->6->3->10->11
	         |
                 v
                 12


		    13
		    |
		    v	
		    2	
		    |	
		    v				Code so far: [2, 4, 11, 8, 7]
	   8->7->6->3->10->11
	         |
                 v
                 12


		    13
		    |
		    v	
		    2	
		    |	
		    v				Code so far: [2, 4, 11, 8, 7, 6]
	      7->6->3->10->11
	         |
                 v
                 12


		    13
		    |
		    v	
		    2	
		    |	
		    v				Code so far: [2, 4, 11, 8, 7, 6, 10]
	         6->3->10->11
	         |
                 v
                 12


		    13
		    |
		    v	
		    2	
		    |	
		    v			Code so far: [2, 4, 11, 8, 7, 6, 10, 3]
	         6->3->10
	         |
                 v
                 12


		    13
		    |
		    v	
		    2	
		    |	
		    v			Code so far: [2, 4, 11, 8, 7, 6, 10, 3, 6]
	         6->3
	         |
                 v
                 12


		    13
		    |
		    v	
		    2	
		    |	
		    v			Code so far: [2, 4, 11, 8, 7, 6, 10, 3, 6, 3]
	         6->3


		    13
		    |
		    v	
		    2	
		    |	
		    v			Code so far: [2, 4, 11, 8, 7, 6, 10, 3, 6, 3, 2]
	            3

		    13
		    |
		    v	
		    2	
		    	
		    		Code so far: [2, 4, 11, 8, 7, 6, 10, 3, 6, 3, 2, 13]

	
The final code is: [2, 4, 11, 8, 7, 6, 10, 3, 6, 3, 2, 13]