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

# Please Edit this .txt page with Answers

#Email  ShaloshBEkhad@gmail.com 
#Subject: p3
#with an attachment called
#p3FirstLast.txt
#(e.g. p3DoronZeilberger.txt)

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


Q1. THE FIRST ATTENDANCE QUESTION WAS:
What is a derangement?

A1. MY ANSWER TO THE FIRST ATTENDANCE QUESTION IS:
A derangement is a permutation of the elements of a set where none of the elements appear in their original positions i.e., there are no fixed points.



Q2. THE  SECOND ATTENDANCE QUESTION WAS:
Give two examples of WtoS and StoW.

A2. MY ANSWER TO THE  SECOND ATTENDANCE QUESTION IS:
WtoS([1,0,1,0,1]) = {1,3,5}.
StoW(WtoS([1,0,1,0,1]), 5) = [1,0,1,0,1].

StoW({2,3}, 4) = [0,1,1,0].
WtoS(StoW({2,3}, 4)) = {2,3}.



Q3. THE  THIRD ATTENDANCE QUESTION WAS:
Prove that the number of permutations of [1,...,n] is n!.

A3. MY ANSWER TO THE  THIRD ATTENDANCE QUESTION IS:
Let f(n) = the number of permutations of [1,...,n]. We know that f(0) = 1 because there is only one way to have an arrangement of no elements. Suppose we know f(n-1) and we're trying to find f(n). For each of the permutations numerated by f(n-1), there are n positions which we can insert a nth element to create a permutation of n elements. Hence, f follows the recurrence relation f(n) = n * f(n-1), f(0) = 1.
Now let g(n) = n!. We know that g(0) = 1 as defined by the factorial function. Also, a property of the factorial function is that g(n) = n! = n * (n-1)! = n * g(n-1). Therefore, g follows the same recurrence relation as f and so, the number of permutations of [1,...,n] has to be n!.