Lecture notes on functions

how functions work together to optimise performance , lecture notes on functions and relations, lecture notes on functions and their graphs lecture notes on functions of management
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Lists, Decisions and Graphs With an Introduction to Probability Unit Fn: Functions Edward A. Bender S. Gill Williamson c Edward A. Bender & S. Gill Williamson 2010. All rights reserved.Preface The material in this unit of study was, over several years, presented by the authors to lower division undergraduates in the Department of Mathematics and the Department of Computer Science and Engineering at the University of California, San Diego (UCSD). All material has been classroom tested by the authors and other faculty members at UCSD. Thefirstcourseof atwo quartersequencewas chosen fromsixunits ofstudy: Boolean Functions (Unit BF), Logic (Unit Lo), Number Theory and Cryptography (Unit NT), Sets and Functions (Unit SF), and Equivalence and Order (Unit EO) The second course of the sequence was chosen from four units of study: Counting and Listing (Unit CL), Functions (Unit Fn), Decision Trees and Recursion (Unit DT), and Basic Concepts in Graph Theory (Unit GT). The order of presentation of units within the first six, as well as those within the second four, can be varied for students with a good high school background in mathematics. Discrete mathematics has become an essential tool in computer science, economics, biology, mathematics, chemistry, and engineering. Each area introduces its own special terms for shared concepts in discrete mathematics. The only way to keep from reinventing the wheel from area to area is to know the precise mathematical ideas behind the concepts being applied by these various fields. Our course material is dedicated to this task. At the end of each unit is a section of multiple choice questions: Multiple Choice Questions for Review. These questions should be read before reading the corresponding unit, and they should be referred to frequently as the units are read. We encouraged our students to be able to work these multiple choice questions and variations on them with ease and understanding. At the end of each section of the units are exercises that are suitable for written homework, exams, or class discussion. iiiivTable of Contents Unit Fn: Functions Section 1: Some Basic Terminology..............................................................Fn-1 direct product, intersection, union, symmetric difference, domain, range, codomain, one-line notation, surjection, onto, injection, one-to-one, bijection, permutation, relation, functional relation, two-line notation Section 2: Permutations................................................................................Fn-7 composition, cycle, cycle form of permutation, involution, permutation matrices, derange- ments Section 3: Other Combinatorial Aspects of Functions................................Fn-13 image, inverse image, coimage, image size and Stirling numbers, strictly increasing, strictly decreasing, weakly increasing, weakly decreasing, monotone, multisets, lists without repeti- tion, restricted growth functions and partitions Section 4: Functions and Probability..........................................................Fn-21 random variable, probability function, event, probability distribution function, expectation, covariance, variance, standard deviation, correlation, independent events, independent ran- dom variables, product spaces, generating random permutations, joint distribution function, marginaldistributions,binomialdistribution,Poissondistribution,normaldistribution,stan- dard normal distribution, cumulative distribution, central limit theorem, normal approxima- tion to binomial, Poisson approximation to binomial, Tchebycheff’s inequality Multiple Choice Questions for Review........................................................Fn-41 Notation Index................................................................................... Fn-Index 1 Subject Index..................................................................................... Fn-Index 3 Starred sections () indicate more difficult and/or specialized material. vviUnit Fn Functions Section 1: Some Basic Terminology Functions play a fundamental role in nearly all of mathematics. Combinatorics is no ex- ception. In this section we review the basic terminology and notation for functions. Per- mutations are special functions that arise in a variety of ways in combinatorics. Besides studying them for their own interest, we’ll see them as a central tool in other topic areas. ExceptfortherealnumbersR,rationalnumbersQandintegersZ,oursetsarenormally finite. The set of the first n positive integers, 1,2,...,n will be denoted by n. Recall that A is the number of elements in the set A. When it is convenient to do so, we linearly order the elements of a set A. In that case we denote the ordering by a ,a ,...,a or by (a ,a ,...,a ). Unless clearly stated otherwise, the ordering on a 1 2 A 1 2 A set of numbers is the numerical ordering. For example, the ordering on n is 1,2,3,...,n. A review of the terminology concerning sets will be helpful. When we speak about sets, we usually have a “universalset”U in mind, to which the varioussetsofour discourse belong. Let U be a set and let A and B be subsets of U. • The sets A∩B and A∪B are the intersection and union of A and B. • The set A\B or A−B is the set difference of A and B; that is, the set x:x∈A,x6∈B. c • The set U \A or A is the complement of A (relative to U). The complement of A is ′ also written A and ∼A. • The set A⊕B =(A\B)∪(B\A) is symmetric difference of A and B; that is, those x that are in exactly one of A and B. We have A⊕B =(A∪B)\(A∩B). • P(A) is the set of all subsets of A. (The notation for P(A) varies from author to author.) • P (A) the set of all subsets of A of size (or cardinality) k. (The notation for P (A) k k varies from author to author.) • The Cartesian product A×B is the set of all ordered pairs built from A and B: A×B =(a,b)a∈A and b∈B. We also call A×B the direct product of A and B. 2 If A = B = R, the real numbers, then R×R, written R , is frequently interpreted as coordinates of points in the plane. Two points are the same if and only if they have the ′ ′ ′ same coordinates, which says the same thing as our definition, (a,b) = (a,b ) if a =a and ′ b = b . Recall that the direct product can be extended to any number of sets. How can 3 R×R×R=R be interpreted? Definition 1 (Function) If A and B are sets, a function from A toB is a rule that tells us how to find a unique b∈B for each a∈A. We write f:A→B to indicate that f is a function from A to B. Fn-1Functions 1 We call the setA the domain off and the setB the range or, equivalently, codomain of f. To specify a function completely you must give its domain, range and rule. A The set of all functions fromA toB is writtenB , for a reason we will soon explain. Thus A f:A→B and f ∈B say the same thing. In calculus you dealt with functions whose ranges were R and whose domains were 2 contained in R; for example, f(x) = 1/(x − 1) is a function from R−−1,1 to R. You also studied functions of functions The derivative is a function whose domain is all differentiable functions and whose range is all functions. If we wanted to use functional notation we could write D(f) to indicate the function that the derivative associates with f. Definition 2(One-line notation) WhenA is ordered,a functioncanbe writtenin one- line notation as (f(a ),f(a ),...,f(a )). Thus we can think of a function as an element 1 2 A A of B×B×...×B, where there areA copies of B. Instead of writing B to indicate the A A set of all functions, we write B . Writing B is incomplete because the domain A is not specified. Instead, only its size A is given. Example 1 (Using the notation) To get a feeling for the notation used to specify a function, it may be helpful to imagine that you have an envelope or box that contains a function. In other words, this envelope contains all the information needed to completely describe the function. Think about what you’re going to see when you open the envelope. You might see P =a,b,c, g:P → 4, g(a)= 3, g(b) =1 and g(c)= 4. This tells you that name of the function is g, the domain of g is P, which is a,b,c, and the range of g is 4 =1,2,3,4. It also tells you the values in 4 that g assigns to each of the values in its domain. Someone else may have put a,b,c g:4 , ordering: a,b,c, g = (3,1,4). in the envelope instead. This describes the same function. It doesn’t give a name for the domain, but we don’t need a name like P for the seta,b,c — we only need to know what is in the set. On the other hand, it gives an order on the domain so that the function can begiven in one-line form. Can you describeotherpossible envelopesfor the same function? What if the envelope contained only g = (3,1,4)? You’ve been cheated You must know the domain of g in order to known what g is. What if the envelope contained the domain of g is a,b,c, ordering: a,b,c, g =(3,1,4)? We haven’t specified the range of g, but is it necessary since we know the values of the function? Our definition included the requirement that the range be specified, so this is not a complete definition. On the other hand, in some discussions the range may not be important; for example, ifg =(3,1,4) all thatmay matteris that therangeis large enough to contain 1, 3 and 4. In such cases, we’ll be sloppy and accept this as if it were a complete specification. 1 Some people define “range” to be the values that the function actually takes on. Most people call that the image, a concept we will discuss a bit later. Fn-2Section 1: Some Basic Terminology A A Example 2 (Counting functions) By the Rule of Product, B = B . We can represent a subset S of A by a unique function f:A → 0,1 where f(x) = 0 if a 6∈ S A and f(x) = 1 if x ∈ S. This proves that there are 2 such subsets. For example, if a,b,d 3 A =a,b,d, then the number of subsets of A is 2 = 2 =8. We can represent a multiset S formed from A by a unique function f:A → N = 0,1,2,... where f(x) is the number of times x appears in S. If no element is allowed to appear more than k times, then we can restrict the codomain of f to be 0,1,...,k and A so thereare (k+1) such multisets. For example, the number ofmultisets ofA =a,b,d A 3 where each element can appear at most 4 times is (4+1) = 5 = 125. The particular multiset a,a,a,d,d is represented by the function f(a) =3, f(b) =0 and f(d)=2. We can represent a k-list of elements drawn from a set B, with repetition allowed, by a unique function f:k → B. In this representation, the list corresponds to the function written in one-line notation. (Recall that the ordering on k is the numerical ordering.) k This proves that there are exactly B such lists. For example, the number of 4-lists that 4 4 can be formed from B = a,b,d is B = 3 = 81. The 4-list (b,d,d,a) corresponds to the function f =(b,d,d,a) in 1-line notation, where the domain is 4. Definition 3 (Types of functions) Let f:A→B be a function. (Specific examples of these concepts are given after the definition.) • If for every b ∈ B there is an a ∈ A such that f(a) =b, then f is called a surjection (or an onto function). Another way to describe a surjection is to say that it takes on each value in its range at least once. • If f(x) =f(y) implies x =y, then f is called an injection or a one-to-one function). Another way to describe an injection is to say that it takes on each value in its range k at most once. The injections in S correspond to k-lists without repetitions. • If f is both an injection and a surjection, it is a called a bijection. A • The bijections of A are called the permutations of A. −1 • If f:A → B is a bijection, we may talk about the inverse of f, written f , which −1 −1 reverses what f does. Thus f :B → A and f (b) is that unique a ∈ A such that −1 −1 2 f(a)=b. Note that f(f (b))=b and f (f(a))=a. Example 3 (Types of functions) Let A =1,2,3 and B =a,b be the domain and range of the function f = (a,b,a). The function is a surjection because every element of the range is “hit” by the function. It is not an injection because a is hit twice. Now consider the function g with domain B and range A given by g(a) = 3 and g(b)= 1. It is not a surjection because it misses 2; however, it is an injection because each element of A is hit at most once. Neitherf norg isa bijectionbecausesome elementoftherangeiseitherhitmorethan once or is missed. The function h with domain B and range C =1,3 given by h(a) = 3 and h(b) = 1 is a bijection. At first, it may look like g and h are the same function. They 2 −1 3 Do not confuse f with 1/f. For example, if f:R → R is given by f(x) = x +1, 3 −1 1/3 then 1/f(x)= 1/(x +1) and f (y) =(y−1) . Fn-3Functions arenotbecausetheyhave different ranges. You cantellifa functionisan injectionwithout knowing its range, but you must know its range to decide if it is a surjection. −1 The inverse of the bijectionh has domainC and rangeB it is given by h (1)=b and −1 h (3)=a. The function f with domain and range a,b,c,d given in 2-line form by   a b c d f = b c a d is a permutation. You can see this immediately because the domain equals the range and the bottom line of the 2-line form is a rearrangement of the top line. The 2-line form is convenient for writing the inverse—just switch the top and bottom lines. In this example,   b c a d −1 f = . a b c d Example 4 (Functions as relations) There is another important set-theoretic way of defining functions. Let A and B be sets. A relation from A to B is a subset of A×B. For example: If A =3 and B = 4, then R =(1,4),(1,2),(3,3),(2,3) is a relation from A to B. If the relationR satisfiesthe condition that, for allx∈A there is a unique y∈B such that (x,y) ∈ R, then the relation R is called a functional relation. In the notation from logic, this can be written ∀x∈A ∃y∈B ∋ (x,y)∈R. This mathematical shorthand is well worth knowing: • “∀” means “for all”, • “∃” means “there exists”, • “∃” means “there exists a unique”, and • “∋” means “such that.” In algebra or calculus, when you draw a graph of a real-valued function f :R →R (such 3 as f(x) =x ), you are attempting a pictorial representation of the set (x,f(x)):x∈R, which is the subset of R×R that is the “functional relation from R to R.” In general, if R⊂A×B is a functional relation, then the function f corresponding to R has domain A and codomain B and is given by the ordered pairs (x,f(x))x∈A =R. If you think of the “envelope game,” Example 1, you will realize that a functional relation is yet another thing you might find in the envelope that describes a function. When a subset is defined it is formally required in mathematics that the “universal set” fromwhich it has beenextractedto form a subset also bedescribed. Thus, in the envelope, in addition to R, you must also find enough information to describe completely A×B. As you can see, a function can be described by a variety of different “data structures.” −1 Given any relation R⊆A×B, the inverse relation R from B to A is defined to be (y,x) : (x,y)∈R. RecalltheexampleinthepreviousparagraphwhereA =3,B =4,and Fn-4Section 1: Some Basic Terminology −1 R = (1,4),(1,2),(3,3),(2,3), The inverse relation is R = (4,1),(2,1),(3,3),(3,2). Notice that all we’ve had to do is reverse the order of the elements in the ordered pairs −1 (1,4),...,(2,3) of R to obtain the ordered pairs (4,1),...,(3,2) of R . −1 Note that neither R nor R is a functional relation in the example in the previous paragraph. You should make sure you understandwhy this statementis true (Hint: R fails −1 the “∃” test and R fails the “∀” part of the definition of a functional relation). Note −1 also that if both R and R are functional relations then A = B. In this case, R (and −1 R ) are bijections in the sense of Definition 3. Example5(Two-linenotation) Sinceone-linenotationisasimple,briefwaytospecify functions, we’ll use it frequently. If the domain is not a set of numbers, the notation is poor because we must first pause and order the domain. There are other ways to write functions which overcome this problem. For example, we could write f(a) =4, f(b) =3, f(c)= 4 and f(d)=1. This could be shortened up somewhat to a→ 4, b→ 3, c→ 4 and d→ 1.   a b c d By turning each of these sideways, we can shorten it even more: . For 4 3 4 1 obvious reasons, this is called two-line notation. Sincex always appearsdirectly over f(x), thereisnoneedtoorderthedomain;infact,weneednotevenspecifythedomainseparately sinceit isgiven bythetopline. Ifthefunctionisabijection,itsinverse functionisobtained by interchanging the top and bottom lines. The arrows we introduced in the last paragraph can be used to help visualize different properties of functions. Imagine that you’ve listed the elements of the domain A in one column and the elements of the range B in another column to the right of the domain. Draw an arrow from a to b if f(a)=b. Thus the heads of arrows are labeled with elements of B and the tails with elements of A. Here are some arrow diagrams. A A B A B B 1 a 1 a 1 a 2 b 2 b 2 b 3 3 c 3 c d In all three functions, the domain A =1,2,3; however, the range B is different for each function. Since each diagram represents a function f, no two arrows have the same tail. If f is an injection, no two arrows have the same head. Thus the second and third diagrams are injections, but the first is not. If f is a surjection, every element of B is on the head of some arrow. Thus the first and third diagrams are surjections, but the second is not. Since the third diagram is both an injection and a surjection, it is a bijection. You should be able to describe the situation with the arrowheads when f is a bijection. How can you tell if a diagram represents a permutation? Fn-5Functions Exercises for Section 1 1.1. This exercise lets you check your understanding of the definitions. In each case below, some information about a function is given to you. Answer the following questions and give reasons for your answers: • Have you been given enough information to specify the function? • Can you tell whether or not the function is an injection? a surjection? a bijection? • If possible, give the function in two-line form. ,,+,? (a) f ∈ 3 , f =(3,1,2,3). 3 (b) f ∈,,+,? , f = (?,,+). 3 (c) f ∈ 4 , 2→ 3, 1→ 4, 3→2. 1.2. Let A and B be finite sets and f:A → B. Prove the following claims. Some are practically restatements of the definitions, some require a few steps. (a) If f is an injection, thenA≤B. (b) If f is a surjection, thenA≥B. (c) If f is a bijection, thenA =B. (d) If A =B, then f is an injection if and only if it is a surjection. (e) If A = B, then f is a bijection if and only if it is an injection or it is a surjection. 1.3. Let S be the set of students attending a large university, let I be the set of student ID numbers for those students, let D be the set of dates for the past 100 years (month/day/year),letG be the set of 16 possible grade point averages between 2.0 and 3.5, rounded to the nearest tenth. For each of the following, decide whether or not it is a function. If it is, decidewhether it is an injection, bijectionor surjection. Give reasons for your answers. (a) The domain is S, the codomain is I and the function maps each student to his or her ID number. (b) The domain is S, the codomain is D and the function maps each student to his or her birthday. (c) The domain is D, the codomain is I and the function maps each date to the ID number of a student born on that date. If there is more than one such student, the lexicographically least ID number is chosen. (d) The domain is S, the codomain is G and the function maps each student to his or her GPA rounded to the nearest tenth. Fn-6Section 2: Permutations (e) The domain is G, the codomains is I and the function maps each GPA to the ID numberofa studentwith thatGPA. Ifthereis morethanonesuchstudent, the lexicographically least ID number is chosen. 1.4. Let A =1,2,3 and B =a,b,d. Consider the following subsets of sets. (3,a), (2,b), (1,a), (1,a), (2,b), (3,c), (1,a), (2,b), (1,d), (1,a), (2,b) (3,d), (1,b). Which of them are relations on A× B? Which of the are functional relations? Which of their inverses are functional relations? Section 2: Permutations Before beginning our discussion, we need the notion of composition of functions. Suppose thatf and g are two functionssuch that the valuesf takes on are contained in the domain of g. We can write this as f:A → B and g:C → D where f(a) ∈ C for all a ∈ A. We define the composition of g and f, written gf:A→ D by (gf)(x) = g(f(x)) for all x∈ A. The notation g◦f is also used to denote composition. Suppose that f and g are given in two-line notation by     p q r s P Q R S T U V f = g = . P R T U 1 3 5 2 4 6 7   p q r s Thengf = . To derive (gf)(p),we noted thatf(p)=P andg(P)=1. The 1 5 4 6 other values of gf were derived similarly. The set of permutations on a set A is denoted in various ways in the literature. Two notationsarePER(A) andS(A). Supposethatf andg are permutationsofa setA. Recall −1 thata permutationisa bijectionfromasettoitselfandsoit makessensetotalkaboutf −1 and fg. We claim that fg and f are also permutations of A. This is easy to see if you write the permutations in two-line form and note that the second line is a rearrangement of the first if and only if the function is a permutation. You may want to look ahead at the next example which illustrates these ideas. The permutation f given by f(a) =a for all a∈A is called the identity permutation. −1 −1 Notice that f ◦f and f ◦f both equal the identity permutation. You should be able to show that, if f is any permutation of A and e is the identity permutation of A, then f ◦e =e◦f =f. 2 Again suppose that f is a permutation. Instead of f◦f or ff we write f . Note that 2 2 2 f (x)isnot(f(x)) . (Infact,ifmultiplicationisnotdefinedinA, (f(x)) hasnomeaning.) 3 We could compose three copies of f. The result is written f . In general, we can compose k k copies of f to obtain f . A cautious reader may be concerned that f ◦(f ◦f) may not k+m k m be the same as (f ◦f)◦f. They are equal. In fact, f = f ◦f for all nonnegative 0 0 integers k and m, where f is defined by f (x) = x for all x in the domain. This is based Fn-7Functions on the“associativelaw” which statesthatf◦(g◦h)=(f◦g)◦hwheneverthecompositions make sense. We’ll prove these results. To prove that the two functions are equal, it suffices to prove that they take on the same values for all x in the domain. Let’s use this idea for f ◦(g◦h) and (f ◦g)◦h. We have (f◦(g◦h))(x)=f((g◦h)(x)) by the definition of ◦, =f(g(h(x))) by the definition of ◦. Similarly ((f◦g)◦h)(x)= (f◦g)(h(x)) by the definition of ◦, =f(g(h(x))) by the definition of ◦. More generally, one can use this approachto prove by induction thatf ◦f ◦···◦f is well 1 2 n k+m k m defined. This result then implies that f =f ◦f . Note that we have proved that the associative law for any three functions f, g and h for which the domain of f contains the values taken on by g and the domain of g contains the values taken on by h. Example 6 (Composing permutations) We’ll use the notation. Let f and g be the permutations     1 2 3 4 5 1 2 3 4 5 f = g = . 2 1 4 5 3 2 3 4 5 1 We can compute fg by calculating all the values. This can be done fairly easily from the two-line form: For example, (fg)(1) can be found by noting that the image of 1 under g is 2 and the image of 2 under f is 1. Thus (fg)(1)= 1. You should be able to verify that     1 2 3 4 5 1 2 3 4 5 fg = gf = = 6 fg 1 4 5 3 2 3 2 5 1 4 and that       1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 3 5 6 f = f = g =f = . 1 2 5 3 4 2 1 3 4 5 1 2 3 4 5 Note that it is easy to get the inverse, simply interchange the two lines. Thus     2 1 4 5 3 1 2 3 4 5 −1 −1 f = which is the same as f = , 1 2 3 4 5 2 1 5 3 4 since the order of the columns in two-line form does not matter. Let f be a permutation of the set A and let n =A. If x ∈ A, we can look at the sequence k x,f(x),f(f(x)),...,f (x),..., D which is often written as k x→f(x)→f(f(x))→...→f (x)→···. Fn-8Section 2: Permutations Since the range of f has n elements, this sequence will contain a repeated element in the s first n+1 entries. Suppose that f (x) is the first sequence entry that is ever repeated and s+p s s+p −1 s that f (x) is the first time that it is repeated. Thus f (x) = f (x). Apply (f ) to p both sides of this equality to obtain x = f (x) and so, in fact, s = 0. It follows that the sequence cycles through a pattern of length p forever since p+1 p p+2 2 p 2 f (x) =f(f (x))=f(x), f (x)=f (f (x))=f (x), and so on. p−1 We call (x,f(x),...,f (x)) the cycle containing x and call p the length of the cycle. If a 3 cycle has lengthp, we call it a p-cycle. Cyclic shifts of a cycle are consideredthe same; for example, if (1,2,6,3)isthe cyclecontaining1 (aswell as2, 3 and 6), then(2,6,3,1),(6,3,1,2) and (3,1,2,6) are other ways of writing the cycle (1,2,6,3). A cycle looks like a function in one-line notation. How can we tell them apart? Either we will be told or it will be clear from the context. Example 7 (Using cycle notation) Consider the permutation   1 2 3 4 5 6 7 8 9 f = . 2 4 8 1 5 9 3 7 6 Since 1 → 2 → 4 → 1, the cycle containing 1 is (1,2,4). We could equally well write it (2,4,1)or (4,1,2);however, (1,4,2)isadifferentcyclesinceit correspondsto1→ 4→ 2→1 The usual convention is to list the cycle starting with its smallest element. The cycles of f are (1,2,4), (3,8,7), (5) and (6,9). We write f in cycle form as f =(1,2,4) (3,8,7) (5)(6,9). It is common practice to omit the cycles of length one and write f = (1,2,4)(3,8,7)(6,9). −1 Theinverse off is obtainedbyreadingthecyclesbackwardsbecausef (x)isthelefthand neighbor of x in a cycle. Thus −1 f =(4,2,1)(7,8,3)(9,6)=(1,4,2)(3,7,8)(6,9). Cycleformisusefulincertainaspectsofthebranchofmathematicscalled“finitegroup theory.” Here’s an application. 3 If (a ,a ,...,a ) is a cycle of f, then 1 2 p f(a )=a , f(a ) =a , ..., f(a ) =a , f(a ) =a . 1 2 2 3 p−1 p p 1 Fn-9Functions Example8(Powersofpermutations) Withapermutationincycleform,it’sveryeasy to calculate a power of the permutation. For example, suppose we want the tenth power of the permutation whose cycle form (including cycles of length 1) is (1,5,3)(7)(2,6). To find the image of 1, we take ten steps: 1 → 5 → 3 → 1···. Where does it stop after ten steps? Since threestepsbring us backto wherewe started(because1 is in a cycle oflength three), nine steps take us around the cycle three times and the tenth takes us to 5. Thus 1 → 5 in the tenth power. Similarly, 5 → 3 and 3 → 1. Clearly 7 → 7 regardless of the power. Ten steps take us around the cycle (2,6) exactly five times, so 2 → 2 and 6 → 6. Thus the tenth power is (1,5,3)(7)(2)(6). Suppose we have a permutation in cycle form whose cycle lengths all divide k. The reasoninginthepreviousexampleshowsthatthekthpowerofthatpermutationwillbethe identitypermutation;thatis, allthecycleswillbe1-longandsoeveryelementismappedto itself (i.e., f(x)=x for allx). In particular, if we are considering permutationsof ann-set, every cycle has length at most n and so we can take k =n, regardless of the permutation. We have shown Theorem 1 (A fixed power of n-permutations is the identity) Given a setS, there k are k 0 depending onS such that f is the identity permutation for every permutation f of S. Furthermore, k =S is one such k. Example 9 (Involutions) An involution is a permutation which is equal to its inverse. −1 2 −1 Since f(x) = f (x), we have f (x) = f(f (x)) = x. Thus involutions are those permu- tations which have all their cycles of lengths one and two. How many involutions are there on n? Let’s count the involutions with exactly k 2-cycles and use the Rule of Sum to add up the results. We can build such an involution as follows: • Select 2k elements for the 2-cycles AND • partition these 2k elements into k blocks that are all of size 2 AND • put the remaining n−2k elements into 1-cycles. Since there is just one 2-cycle on two given elements, we can interpret each block as  n 2-cycle. This specifies f. The number of ways to carry out the first step is . For the 2k  2k k second step, we might try the multinomial coefficient = (2k)/2 . This is almost 2,...,2 right In using the multinomial coefficient, we’re assuming an ordering on the pairs even though they don’t have one. For example, with k =3 and the set 6, there are just 15 possible partitions as follows. 1,2,3,4,5,6 1,2,3,5,4,6 1,2,3,6,4,5 1,3,2,4,5,6 1,3,2,5,4,6 1,3,2,6,4,5 1,4,2,3,5,6 1,4,2,5,3,6 1,4,2,6,3,5 1,5,2,3,4,6 1,5,2,4,3,6 1,5,2,6,3,4 1,6,2,3,4,5 1,6,2,4,3,5 1,6,2,5,3,4  6 This is smaller than = 6/222 = 90 because all 3 ways to order the three blocks 2,2,2 in each partition are counted differently to obtain the number 90. This is because we’ve Fn-10Section 2: Permutations chosen a first, second and third block instead of simply dividing 6 into three blocks of size two. How can we solve the dilemma? Actually, the discussion of what went wrong contains the key to the solution: The multinomial coefficient counts ordered collections of k blocks and we want unordered collections. Since the blocks in a partition are all distinct, there are k ways to order the blocks and so the multinomial coefficient counts each unordered collection k times. Thus we must simply divide the multinomial coefficient by k. If this dividing by k bothers you, try looking at it this way. Let f(k) be the number of ways to carry out the second step, partition the 2k elements into k blocks that are all of size 2. Since the k blocks can be permuted in k ways, the Rule of Product tells us that there are  2k f(k)k ways to select k ordered blocks of 2 elements each. Thus f(k)k= . 2,...,2 Since there is just one way to carry out Step 3, the Rule of Product tells us that the number of involutions with exactly k 2-cycles is     n 1 2k n 1 (2k) = . k 2k k 2,...,2 (2k)(n−2k) k (2) Simplifying and using the Rule of Sum to combine the various possible values of k, we obtain a formula for involutions. We have just proved: The number of involutions of n is ⌊n/2⌋ X n k (n−2k)2 k k=0 where⌊n/2⌋denotesthelargestintegerless thanor equalton/2. Let’susethisto compute the number of involutions when n = 6. Since ⌊6/2⌋= 3, the sum has four terms: 6 6 6 6 + + + 0 1 2 3 (6−0)2 0 (6−2)2 1 (6−4)2 2 (6−6)2 3 6×5 6×5×4×3 6×5×4 = 1+ + + 2 4×2 8 = 1+15+45+15 = 76. Thelastterminthesum, namelyk =3correspondstothoseinvolutionswiththree2-cycles (and hence no 1-cycles). Thus it counts the 15 partitions listed earlier in this example. If you’re familiar with the basic operations associated with matrices, the following example gives a correspondence between matrix multiplication and composition of permu- tations. Example 10 (Permutation matrices) Supposef andg are permutationsof n. We can th define an n×n matrix F to consist of zeroes except that the (i,j) entry, F , equals one i,j whenever f(j)=i. Define G similarly. Then n X (FG) = F G =F , i,j i,k k,j i,g(j) k=1 Fn-11Functions since G = 0 except when g(j)=k. By the definition of F, this entry of F is zero unless k,j f(g(j))=i. Thus (FG) is zero unless (fg)(j)=i, in which case it is one. We’ve proven i,j that FG corresponds to fg. In other words: Composition of permutations corresponds to multiplication of matrices. −1 −1 It is also easy to prove that f corresponds to F . Using this correspondence, we can −1 −1 −1 k −1 −1 k prove things such as (fg) = g f and (f ) = (f ) by noting that they are true for matrices F and G. As an example, let f and g be the permutations     1 2 3 4 5 1 2 3 4 5 f = g = . 2 1 4 5 3 2 3 4 5 1 We computed fg in Example 6. We obtained   1 2 3 4 5 fg = . 1 4 5 3 2 Using our correspondence, we obtain     0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0     F =0 0 0 0 1 G =0 1 0 0 0     0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 You should multiply these two matrices together and verify that you get the matrix FG corresponding to   1 2 3 4 5 fg = . 1 4 5 3 2 Example 11 (Derangements) A derangement is a permutation f with no fixed points; i.e., f(x) 6= x for all x. We first show that the probability is 1/n that a permutation f, selected uniformly at random from all permutations of n, has f(k) = k. If f(k) = k, then the elements ofn−k can be permuted in any fashion. This can be done in (n−1) ways. Thus, (n−1) is the cardinality of the set of all permutations of n that satisfy f(k) = k. Since there are n permutations, the probability that f(k) = k is (n− 1)/n = 1/n. Hence the probability that f(k) = 6 k is 1− 1/n. If we toss a coin with probability p of n heads for n tosses, the probability that no heads occurs in n tosses is (1−p) . This is because each toss is “independent”of the prior tosses. If we, incorrectly, treat then events f(1)6=1,...,f(n)= 6 n as independentin this same sense, the probability thatf(k)= 6 k for n n k =1,...,n, would be (1−1/n) . One ofthestandardresultsin calculusis that(1−1/n) n approaches1/easn→∞. (Youcanproveitbywriting(1−1/n) =exp(ln(1−1/n)/(1/n)), setting 1/n = x and using l’Hˆopital’s Rule.) Thus, we might expect approximately n/e derangements of n for large n. Although our argument is wrong, the result is right We get partial credit for this example. Fn-12Section 3: Other Combinatorial Aspects of Functions Exercises for Section 2 2.1. This exercise lets you check your understanding of cycle form. A permutation is given in one-line, two-line or cycle form. Convert it to the other two forms. Give its inverse in all three forms. (a) (1,5,7,8) (2,3) (4) (6).   1 2 3 4 5 6 7 8 (b) . 8 3 7 2 6 4 5 1 (c) (5,4,3,2,1), which is in one-line form. (d) (5,4,3,2,1), which is in cycle form. 2.2. A carnival barker has four cups upside down in a row in front of him. He places a pea under the cup in the first position. He quickly interchanges the cups in the first and third positions, then the cups in the first and fourth positions and then the cups in the second and third positions. This entire set of interchanges is done a total of five times. Where is the pea? Hint: Write one entire set of interchanges as a permutation in cycle form. 2.3. Let f be a permutation of n. The cycle of f that contains 1 is called the cycle generated by 1. (a) Prove that the number of permutations in which the cycle generated by 1 has length n is (n−1). (b) For howmany permutationsdoesthe cyclegeneratedby1 have lengthk? (Re- member that a permutation must be defined on all elements of its domain n.) (c) If your answer to (b) is correct, when it is summed over 1 ≤ k ≤ n it should equaln, thetotalnumber ofpermutationsofn. Why? Showthatyour answer to (b) has the correct sum. 2.4. This exercise deals with powers of permutations. All our permutations will be written in cycle form. 300 (a) Compute (1,2,3) .  300 (b) Compute (1,3)(2,5,4) . 60 (c) Showthatforeverypermutationf of5,wehavef istheidentitypermutation. 61 What is f ? Fn-13Functions Section 3: Other Combinatorial Aspects of Functions Thissectioncontainstwo independentparts. The firstdealswiththeconceptoftheinverse of a general function. The second deals with functions related to computer storage of unordered lists. The Inverse of an Arbitrary Function Again, let f:A→B be a function. The image of f is the set of values f actually takes on: Image(f)=f(a)a∈A. The definition of a surjection can be rewritten Image(f) =B because a surjection was defined to be a function f : A → B such that, for every b ∈ B there is an a∈A with f(a)=b. −1 For eachb∈B, the inverse image ofb, writtenf (b) is the set of those elementsin A whose image is b; i.e., −1 f (b) =aa∈A andf(a)=b. −1 This extends our earlier definition of f from bijections to all functions; however, such −1 an f can’t be thought of as a function from B to A unless f is a bijection because it will 4 not give a unique a∈A for each b∈B. −1 Suppose f is given by the functional relation R ⊂ A×B. Then f (b) is all those a −1 −1 such that (a,b)∈R. Equivalently, f (b) is all those a such that (b,a)∈R . Definition 4 (Coimage) Let f:A → B be a function. The collection of nonempty inverse images of elements of B is called the coimage of f. In mathematical notation −1 −1 −1 Coimage(f)=f (b)b∈B,f (b)6=∅=f (b)b∈ Image(f). 5 We claim that the coimage of f is the partition of A whose blocks are the maximal 5 subsets of A on which f is constant. For example, if f ∈a,b,c is given in one line form as (a,c,a,a,c), then  −1 −1 Coimage(f)=f (a),f (c)= 1,3,4,2,5 , f is a on1,3,4 and is c on 2,5. −1 −1 We now prove the claim. If x∈A, let y =f(x). Then x∈f (y) and the set f (y) is an element of Coimage(f). Hence the union of the nonempty inverse images contains A. Clearly it does not contain anything which is not in A. If y = 6 y , then we cannot 1 2 −1 −1 have x ∈ f (y ) and x ∈ f (y ) because this would imply f(x)=y and f(x)=y , a 1 2 1 2 contradiction of the definition of a function. Thus Coimage(f) is a partition of A. Since the value of f(x) determines the block to which x belongs, x and x belong to the same 1 2 block if and only if f(x ) =f(x ). Hence a block is a maximal set on which f is constant. 1 2 4 There is a slight abuse of notation here: If f:A→ B is a bijection, our new notation −1 −1 is f (b) =a and our old notation is f (b)=a. 5 RecallthatapartitionofasetS isanunorderedcollectionofdisjointnonemptysubsets of S whose union is S. These subsets are called the blocks of the partition. Fn-14

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.