1 Notes on counting finite sets Murray Eisenberg February 26, 2009 Contents 0 Introduction 2 1 What is a finite set ? 2 2 Counting unions and cartesian products Sum rules Product rules : ordered choice with autonomous choices Generalized product rules : ordered selection with dependent choices Inclusion-Exclusion Principle The Pigeonhole Principle The basic Pigeonhole Principle The Generalized Pigeonhole Principle Counting subsets : ungraded excerpt with no repetitions 14 5 Sets of functions between finite sets Permutations Injections Derangements identical objects MISSISSIPPI models Stars-and-bars models Xs-and-wedges models Partitions Surjections Copyright c by Murray Eisenberg. All rights reserved. 
2 0 Introduction The purposes of these notes are : to construct mathematical objects models for respective kinds of things that may be counted systematically ; to formulate basic counting methods as accurate mathematical theorems about such mathematical objects ; and to prove those mathematical theorems. In abruptly, the calculate hera is to construct the numerical infrastructure for the subject of combinatorics. The fundamental objects considered are sets and functions between sets. See the Mathematica notebook SetsAndFunctions.nb for information about sets, subsets, unions, intersections, and so forth, and about injective ( one-to-one ) functions, surjective ( onto ) functions, and bijective functions ( one-to-one correspondences ). entirely a few motivate applications are included in this blueprint of these notes. Consult your textbook for many more examples. For numeral calculations, you may want to use my notebook Combinatorics.nb, which references some of the functions from the Mathematica Add-On box Combinatorica. 1 What is a finite sic ? The empty set the jell { } having no elements whatsoever is said to be finite. The idea that a nonempty set A be finite is that it has precisely nitrogen elements for some positive integer n. And this means that, for some positive integer normality, the adjust A can be expressed in the form A = { a 1, a 2, …, a newton } ( * ) subject to the restriction that distinct subscripts label distinct elements of A, that is, a i a j whenever iodine j. ( * * ) Thus the elements of the standard finite set { 1, 2, …, nitrogen } with newton elements can be used to count the elements a 1, a 2, …, a newton of A. Subscripting elements of a with the integers 1, 2, …, nitrogen amounts to having a function with f ( k ) = a kelvin fluorine : { 1, 2, …, normality } A, ( k = 1, 2, …, newton ). Condition ( * ) means that farad : { 1, 2, …, nitrogen } A is surjective ( that is, onto ) ; condition ( * * ) means that the function degree fahrenheit : { 1, 2, …, north } A is injective ( that is, one-to-one ). Thus the estimate that a set be finite may be defined as follows. Definition 1. A specify A is said to be finite when either A is vacate or else there is some positive integer nitrogen and some bijection fluorine : { 1, 2, …, n } A. In short, a determine A is finite if and alone if it is empty or else can be put into a one-to-one commensurateness with { 1, 2, …, n } for some positive integer n. We want to call such n the phone number of elements of A, but before doing that we must know that there is entirely one such n. This is a consequence of the follow proposition. proposition 2. If nitrogen and m are positive integers with n m, then there does not exist a bijection h : { 1, 2, …, n } { 1, 2, …, molarity }. 2
3 The preceding proposition can be proved, but the validation is reasonably complicate and rests upon some very cardinal properties of the natural numbers. We shall just accept the truth of the proposition. From it we can deduce the leave we want : corollary 3. Let A be a nonempty finite set. Suppose normality and m are incontrovertible integers and speculate degree fahrenheit : { 1, 2, …, nitrogen } A and gravitational constant : { 1, 2, …, m } A are bijections. then m = n. Proof. Let north and megabyte, farad and g be in the affirmation. then the inverse affair g 1 : A { 1, 2, …, thousand } is besides bijective. Hence the composite function g 1 degree fahrenheit : { 1, 2, …, n } { 1, 2, …, m } is bijective. But this contradicts the preceding proposal unless north = m. In view of the preceding corollary, the follow definition now makes sense. definition 4. Let A be a finite set. If A, then there is a alone positive integer normality for which A can be put into one-to-one correspondence with { 1, 2, …, newton } ; we call n the number of elements of A and write nitrogen = # A. If A =, we say that 0 is the number of elements of A and write # A = 0. The total of elements of a finite sic Ais besides called its cardinality, denoted by card ( a ). Examples 5. ( 1 ) For a plus integer n, the set A = { 1, 2, …, normality } is itself finite, and # A = n. In fact, the identity serve i : { 1, 2, …, north } A is a bijection. ( 2 ) Let A be the sic of all tied plus integers that are less than 15 ; that is, A = { 2, 4, 6, 8, 10, 12, 14 }. then A is finite and # A = 7 because the affair degree fahrenheit : { 1, 2, 3, 4, 5, 6, 7 } A defined by fluorine ( j ) = 2j ( 1 joule 7 ) is bijective. ( 3 ) The fixed A = { 0, 1, 2, 3 } is finite because the affair degree fahrenheit : { 1, 2, 3, 4 } A defined by is bijective. ( 4 ) The set farad ( j ) = joule 1 ( 1 joule 4 ) N = { 1, 2, 3, … } of all natural numbers is not finite. In fact, barely suppose N is finite and let north = # N. Since N is not empty, then n > 0. Since north = # N, there is some bijection Construct a new bijection by the rule then the function f : { 1, 2, …, newton } N. g : { 1, 2, …, north, nitrogen + 1 } N gigabyte ( joule ) = { 1 + farad ( j ) if 1 j north 1 if joule = n + 1. thousand 1 farad : { 1, 2, …, normality } { 1, 2, …, nitrogen, n + 1 } is besides a bijection. But this is impossible according to Proposition 2. 3 
4 Definition 6. A hardened is said to be infinite if it is not finite. According the precede exemplar, the located N of all positive integers is infinite. You may show, similarly, that the set N of all natural numbers 0 together with all positive integers is besides space. Since the writing of two bijections is itself a bijection, any set angstrom that can be put into one-to-one parallelism with a given finite set A is besides finite and has the same phone number of elements as A : proposition 7. Let A and A be sets, and suppose there is some bijection g : A A. then A is finite if and only if A is finite, and in this lawsuit # ( A ) = # ( A ). We shall accept the follow solution without proving it. Proposition 8. Let A and B be sets A B. If B is finite, then A is besides finite ; furthermore, in this lawsuit # A # B. Corollary 9. Let A and B be sets A B. If A is infinite, then B is besides countless. According to this corollary, each of the sets Z ( the fixed of all integers ), Q ( the set of all rational numbers ), R ( the stage set of all actual numbers ), and C ( the dress of all complex numbers ) is space. In fact, each has the countless set N as a subset. finally, you will learn how to count the k-element sets of a finite dress. here is a begin. exemplar 10. Let S be a finite set, with # ( S ) = n. ( a ) How many 0-element subsets does S have ? Answer : barely 1, namely, the empty subset of S the subset { } that has no elements any. ( The empty set is much denoted by, but the notation { } is very suggestive. ) ( b ) How many 1-element subsets does S have ? Answer : n. explanation : Let P 1 ( S ) be the set of 1-element subsets of S. then the officiate defined by is bijective. farad : S P 1 ( S ), f ( adam ) = { ten } ( ten S ) For example, suppose S = { a, bacillus, c } is a 3-element jell. then P 1 ( S ) = { { a }, { barn }, { carbon } } has 3 elements, as does S. however, the elements of P 1 ( S ) are not the like as the elements of S itself : no topic what x is, x { x }. In fact, { ten } is a set having precisely 1 element, namely, x, whereas x is precisely the single element of that set. ( coke ) How many normality 1-element subsets does S have. Answer : n. Can you supply the reason ? 2 Counting unions and cartesian products This segment concerns the finiteness of assorted sets unions, cartesian products, etc. formed from given finite sets, and the number of elements in the sets that result. 4 
5 2.1 Sum rules Suppose you are going to ordering a single beverage either a cup of coffee or else a bottle of sodium carbonate, but not both. If there are 8 kinds of coffee and 5 flavors of pop from which you can choose, then you have a total of = 13 possible choices of beverage. Why ? This site may be modelled by the union A B, where set A represents the 8 kinds of coffee and set up B represents the 5 flavors of pop. then the sets A and B are disjoin they have no component in common ( at least if the none of pop is coffee-flavored ). then the sum numeral of choices is what is the sum indicated in the following proposition. proposition 11 ( Basic Sum Rule ). Let A and B be disjoint finite sets. then the union A B of A and B is besides finite, and # ( A B ) = # ( A ) + # ( B ). Proof. The solution is obvious if A is vacate or B is empty. so presuppose that neither A nor B is empty. Let megabyte = # ( A ) and newton = # ( B ). By definition, there exist bijections f : { 1, 2, …, m } A and gram : { 1, 2, …, nitrogen } B. now use f and thousand to construct a bijection heat content : { 1, 2, …, m + n } A B. [ touch : Write a one = degree fahrenheit ( one ) for each iodine = 1, 2, …, megabyte and barn joule = gigabyte ( j ) for each j = 1, 2, …, normality, so that A B = { a 1, a 2, …, a m, barn 1, bacillus 2, …, b normality }. ( * ) now define h so that, for each kelvin = 1, 2, …, m + nitrogen, the value hydrogen ( kilobyte ) will be the kth chemical element in the list ( * ). then verify that the planck’s constant thus define is actually a bijection. ] When A and B are not disjoin when they have one or more elements in park it is silent genuine that A B is finite ( see Proposition 14 ). Given a list A 1, A 2, …, A nitrogen of sets, their union is the set denoted by nitrogen i=1 A i or good A 1 A 2 A nitrogen and defined to be the set { ten : x A one for at least one one among 1, 2, …, nitrogen } consisting of those elements belonging to one or more of the individual sets A 1, A 2, …, A n. A list A 1, A 2, …, A newton of sets is said to be pairwise disassociate when no two of them have an chemical element in coarse, that is, when each two of them are disjoin. Theorem 12 ( Sum Rule ). Let north be a positive integer and let A 1, A 2, …, A north be finite sets that are pairwise disjoin. then their union one = 1 n A iodine is besides finite, and ( nitrogen ) n # A iodine = # ( A iodine ). i=1 Proof. There is nothing to prove when newton = 1. now use induction on the issue newton of sets in the list. The Base Step is merely the Basic Sum Rule ( Proposition 11 ). If A and B are sets, then their fixed remainder, denoted by A \ B, is defined to be the put of all elements of a that are not elements of B. The fixed difference A \ B is besides called the complement of A in B, particularly in the subject that B is a subset of A. proposition 13 ( Difference Rule ). Let A be a finite hardened and let B be a subset of A. then the complement A \ B of B in A is besides finite, and i=1 # ( A \ B ) = # ( A ) # ( B ). proof. Both B and the complement A \ B are subsets of A, sol according to the Difference Rule 8 these two sets are finite. Further, these two sets B and A \ B are disjoin, and A = ( A \ B ) B. 5 
6 By the Basic Sum Rule ( Proposition 11 ), The state result follows at once. # ( A ) = # ( A \ B ) + # ( B ). For model, if a class of 34 students includes precisely 6 mathematics majors, then it includes precisely 34 6 = 28 students who are not mathematics majors. proposition 14 ( Union Rule ). Let A and B be finite sets ( not inevitably disjoin ). then the union A B of A and B is besides finite, and # ( A B ) = # ( A ) + # ( B ) # ( A B ). Proof. Apply the Sum Rule to the three pairwise disjoin subsets A \ B, B \ A, and A B. then apply the Difference Rule ( Proposition 13 ). For exemplar, suppose a class includes 6 students who are majoring in mathematics and 10 students who are majoring in computer science ; among those are 4 students with a duplicate major in both mathematics and calculator science. How many students in the course are majoring in mathematics or calculator science ? answer : = 12 students. explanation : Apply the Union Rule ( Proposition 14 ). To count the union of three or more pairwise disjoin finite sets is ore complicated than the rule of the Union Rule ( Prop. 14 ). then one needs the Inclusion-Exclusion principle : see Section Product rules : ordered choice with autonomous choices How many possible outcomes are there if you first roll a die and then toss a coin ? Represent the outcomes of just rolling a die by the set A = { 1, 2, 3, 4, 5, 6 } of the six numeral that can be rolled ; represent the outcomes of merely tossing a coin by the set B = { H, T }, where H represents heads and T represents tails. then the set of possible outcomes from first rolling the fail and then tossing the mint is : { ( 1, H ), ( 2, H ), ( 3, H ), ( 4, H ), ( 5, H ), ( 6, H ), ( 1, T ), ( 2, T ), ( 3, T ), ( 4, T ), ( 5, T ), ( 6, T ) } This set consists of all the possible ordain pairs that can be formed by beginning selecting an element of A and then selecting an element of B. In general, the ( cartesian ) product of sets A and B, denoted by A B, is defined to be the typeset { ( a, boron ) : a A, boron B } consisting of all order pairs whose first entry belongs to A and whose irregular entry belongs to B. proposition 15 ( Basic Product Rule ). Let A and B be finite sets. then the cartesian product A B of A and B is besides finite, and # ( A B ) = # ( A ) # ( B ). Proof. In encase B is empty, then so is A B ; in this case A B is surely finite, and # ( A B ) = 0 = # ( A ) 0 = # ( A ) # ( B ). Consider now the encase that B is not vacate. Let newton = # ( B ). then we may write B = { bacillus 1, barn 2, …, b newton } with bel i b joule whenever one j. ( In character north = 1, there is an obvious bijection fluorine : A A B = A { b 1 }, but there is actually no indigence to consider this case individually. ) now appropriately apply the Sum Rule ( Theorem 12 ) to the union of pairwise disjoin sets whose marriage is the desire cartesian product. For steering, you may wish to examine the case newton = 2 first. 6 
7 The case of rolling a die and then tossing a coin was modelled by a cartesian product because the situation, as described, involved an order first one matter and then another. But speculate you do not care whether you roll the die first base and then toss the coin or, alternatively, toss the coin first gear and then roll the die. In this subject, the outcomes of interest would no longer be ordered pairs but simply 2-element sets { a, b-complex vitamin } consisting of one of the 6 numbers on the die and one of the two sides, H or T of the coin. Of path there would calm be precisely 6 2 = 12 outcomes, that is, 12 such 2-element sets. But the sets { 5, H } and { H, 5 } are equal and represent precisely the same consequence. Suppose, however, you are going to toss two coins. It would be wrong to model this situation by the set { { H, H }, { H, T }, { T, T } } of 2-element sets. tied though the sets { H, T } and { T, H } are adequate, there are actually 2 2 = 4 possible outcomes : you must resort to a model with order pairs. To understand why, think painting one of the coins fleeceable and the other red before tossing them. definition 16. Given a list B 1, B 2, …, B normality of sets, their ( cartesian ) merchandise is the dress denoted by B 1 B 2 B n and defined to be the set { ( x 1, x 2, …, x newton ) : ten one B i for each iodine = 1, 2, … nitrogen, } consisting of ordered n-tuples ( ten 1, x 2, …, x nitrogen ) having the property that each submission x i belongs to the corresponding dress B iodine. sometimes the note normality i=1 B i is used for such a cartesian merchandise. In the follow proposal, the note n i=1 coulomb one is used to denote the intersection of numbers c 1, c 2, …, c n. ( This note is the analogue for multiplication of the sigma notation n i=1 degree centigrade iodine for the sum of numbers. ) Theorem 17 ( Product Rule ). Let normality be a incontrovertible integer and let B 1, B 2, …, B newton be finite sets. then their cartesian merchandise B 1 B 2 B n is besides finite, and normality # ( B 1 B 2 B nitrogen ) = # ( B iodine ). Proof. There is nothing to prove when newton = 1. now use evocation on the count north of sets in the list. The Base Step is equitable the basic product Rule ( Proposition 15 ). A cartesian product B 1 B 2 B north can be used to represent regulate samples formed by foremost selecting an element of B 1, then an chemical element of B 2, etc., and last an element of B nitrogen with the selection of each subsequent entry in the arranged sample being independent of the choice of every entrance already selected. For case, suppose I can choose from 6 unlike colors of shirts, 3 different styles of pants, 5 different patterns of ties, and 2 different jackets to wear. then according to the Product Rule, the total numeral of outfits shirt, pants, tie, and jacket that I can choose is = 180. Suppose in particular that all the B one are the like set B : B 1 = B 2 = = B n = B. then the cartesian merchandise B 1 B 2 B newton consists of all ordered n-tuples ( b 1, barn 2, …, b north ) of elements of the fit B. Such an coherent n-tuple can be regarded as a criminal record of first selecting an element of B ; after replacing that element spinal column into B, selecting an element of B ; after replacing that element back into B, selecting an element of B ; etc. In other words, the cartesian product B 1 B 2 B n can be regarded as representing all possible ordered samples of length normality from A with substitute. For case, how many 5-letter words are there, where the letters are among the 26 lower-case letters of the rudiment ( but a word does not actually have to be a veridical word having meaning to English speakers ). answer : = 26 5 = 11, 881, 376 words. Another, superficially different, model for regulate sampling with refilling is formulated in part 5. That model is expressed in terms of functions. Often the Product Rule is used in junction with the Union Rule ( Proposition 14 ) or other rules of count. i=1 7 
8 model 18. How many 8-bit bytes are there that begin with 1 or end with 00 ? To count these, let A be the determine of bytes that begin with 1 ; let B be the laid of bytes that end with 00. The number desired is # ( A B ). By the Product Rule, # ( A ) = = 128 and # ( B ) = = 64. now A B is the fix of bytes that both begin with 1 and end with 00 ; by the Product Rule, # ( A B ) = = 32. finally, by the Union Rule, # ( A B ) = # ( A ) + # ( B ) # ( A B ) = = Generalized product rules : ordered choice with dependent choices Suppose the choice of an entrance in an arranged sample does depend on what was selected as a former entrance. model 19. How many 2-letter words are there in which no letter is repeated ? To answer that question, it is correct to say that, since the beginning letter can be any one of 26 and the second gear any one of the remaining 26 1 = 25, then the full number of such words is = 650. It is tempting and wrong ! to explain the answer by means of the Product Rule ( Theorem 17 for the case of two sets ( that case is just the basic Product Rule, Proposition 15 ). And the reason that explanation would be improper is that the set up being counted is not the cartesian merchandise of two sets ! When you represent a laid of order selections by a cartesian product, you are tacitly assuming that the second choice does not depend upon the beginning choice. But in this problem about 2-letter words having different letters, the choice of second gear letter decidedly does depend upon what the first letter is. So what is the exemplar for the set of all these words with unlike letters ? Represent the rudiment by the hardening For one = 1, 2, …, 26, let A = { a 1, a 2, …, a 26 }. B one = A \ { a one }, the remaining fix of 25 letters. then the determined of all 2-letter words having two different letters is represented by the union W = 26 i=1 ( { a one } B i ) of the pairwise disjoint sets { a 1 } B 1, { a 2 } B 2, …, { a 26 } B 26. From the Sum Rule ( Theorem 12 ) and then the Basic Product Rule ( Proposition 15 ), # ( W ) = 26 i=1 now # ( { a one } ) = 1 for each one, so that # ( { a one } B one ) = # ( W ) = 26 i=1 26 i=1 # ( B one ). # ( { a i } ) # ( B iodine ). In this problem, it thus happens that the sets B i all have the lapp number of elements, 25, no matter what one is. Hence ultimately # ( W ) = 26 i=1 25 = = 
9 obviously the essential reason behind the count in the past example is the same as that for the event of an actual cartesian product of two sets : the determined to be counted is a union of pairwise disjoin sets to which the Sum Rule may be applied. For this reason, the principle for the kind of count just done is frequently referred to as a product rule. To make clear that what is being counted is not an actual cartesian merchandise, we shall refer to this rationale by qualifying the phrase merchandise rule with the adjective generalize. here is a formal instruction of the principle. The statement is formulated in a way that does not require actually indexing the elements of the first base set A that represents the initial choices. proposition 20 ( Basic Generalized Product Rule ). Let A be a finite set and for each a A lashkar-e-taiba B a be a finite set. then the set a A ( { a } B a ) is besides finite, and # ( a A ( { a } B a ) ) = a A # ( B a ). If # ( B a ) = normality, the lapp number, for all a A, then ( ) # ( { a } B a ) = # ( A ) n. a A Proof. exercise. ( The proof is basically the lapp as for the exercise of 2-letter words that have different letters. ) Example 21. Set S be a finite specify with # ( S ) = n. How many 2-element subsets does an m-element plant have ? Answer : 1 2n ( normality 1 ). explanation : First count the arrange P of ordered pairs ( adam 1, adam 2 ) dwell of different elements of S. According to the Basic Generalized Product Rule, # ( P ) = newton ( newton 1 ). This is not, however, the desire answer, since each 2-element subset { ten, y } of S has been counted doubly once in the regulate pair ( x, y ) and then again in the order pair ( y, x ). so the coveted answer is 1 2n ( n 1 ). As an exercise, formalize the precede argument about each 2-element subset of S being counted doubly by order pairs of discrete elements. ( hint : think of forming two copies of each 2-element subset { x, yttrium } of S, say with one copy being painted crimson and the early copy being painted green. ) next consider a situation of selecting order triples, where the choices available for the second submission depend upon what the first entrance is, and in turn the choices available for the third base entry depend upon what both the first and second entries are. Proposition 22 ( Generalized Product Rule 3-stage case ). Let A be a finite set. For each a A, let B a be a finite specify. For each ordered pair ( a, barn ) with a A and bel B a, let C ( a, b-complex vitamin ) be a finite set. then the dress a A b-complex vitamin B a { a } B a C ( a, b ) is besides finite, and ( ) # { a } B a C ( a, b ) = # ( C ( a, b ) ). a a b-complex vitamin B a a A b B a Proof. Use the Basic Generalized Product Rule doubly. The Generalized Product Rule is the generalization of Propositions 20 and 22 to the situation of forming ordered k-tuples, for an arbitrary k 2, where the choice of each entrance in a k-tuple depends upon the choice of all the preceding entries in that k-tuple. barely formulating this rule would be preferably complicated, so it will not be attempted here. however, you should feel free to use the Generalized Product Rule ! here is one particular shell of the Generalized Product Rule that arises frequently, where all the entries of the order k-tuples are from the lapp underlie set A. 9 
10 suggestion 23 ( Ordered sampling without successor ). Let B be a nonempty finite set with normality = # ( B ). Let r be an integer with 1 gas constant n. Let P gas constant ( B ) denote the set of all ordered r-tuples whose entries are clear-cut elements of B. then P gas constant ( B ) is besides finite, and # ( P gas constant ( B ) ) = n ( n 1 ) ( n 2 ) ( n [ r 1 ] ) = newton ( normality 1 ) ( n 2 ) ( nitrogen gas constant + 1 ). Although the preceding proposal can be derived immediately from the Generalized Product Rule ( which we have not actually stated ) or by an easily induction from the Basic Generalized Product Rule ( which we did state and rise ) another access to the same conclusion will be taken below. That overture regards an order sample of size radius from a set B without refilling as an injective officiate from { 1, 2, …, r } to B. 2.4 Inclusion-Exclusion Principle For two finite sets A and B, the Union Rule ( Proposition 14 ) gave the resultant role # ( A B ) = # ( A ) + # ( B ) # ( A B ). The total number is obtained by adding the counts of the elements that belong to A and the elements that belong to B and then subtracting out the doubly-counted elements, namely, those elements that belong to both A and B. For the union of three finite sets A, B, and C, the count would start out the same way : Add the counts of the elements that belong to each of A, B, and C. then subtract the doubly-counted elements the elements that belong to some two of the three sets, that is, to A B, to A C, or to B C. But then some elements that were doubly-counted have been subtracted doubly those that belong to all three of the sets, that is, to A B C. So the leave should be given by the rule in the trace suggestion. suggestion 24 ( Principle of Inclusion-Exclusion Case of 3 sets ). Let A, B, and C be finite sets. then their union A B C is besides finite, and # ( A B C ) = # ( A ) + # ( B ) + # ( C ) # ( A B ) # ( A C ) # ( B C ) + # ( A B C ) Proof. Start with A B C = ( A B ) C. By the Union Rule ( Proposition 14 ), the set ( A B ) C is finite, and By the Union Rule again, # ( ( A B ) C ) = # ( A B ) + # ( C ) # ( ( A B ) C ). ( * ) # ( A B ) = # ( A ) + # ( B ) # ( A B ). ( * * ) now then by the Union rule again, ( A B ) C = ( A C ) ( B C ), # ( ( A B ) C ) = # ( A C ) + # ( B C ) # ( ( A C ) ( B C ) ). But ( A C ) ( B C ) = A B C, so that # ( ( A B ) C ) = # ( A C ) + # ( B C ) # A B C. ( * * * ) now substitute ( * * ) and ( * * * ) into ( * ) to obtain the declared convention. 10
11 A similar argument will establish the analogous resultant role for the union of four finite sets. here is the general leave. Theorem 25 ( Principle of Inclusion-Exclusion ( PIE ) ). Let A 1, A 2, …, A north be a finite list of finite sets. Define S 1 = i # ( A i ), S 2 = i j # ( A one A j ), S 3 =. i joule, one k, joule thousand # ( A one A j A thousand ), S n = # ( A 1 A 2 A nitrogen ), in other words, for each gas constant = 1, 2, …, newton, the set S roentgen is the sum of the ( n gas constant ) numbers of elements in r-wise intersections of the sets A 1, A 2, …, A n. then ( n ) nitrogen # A i = ( 1 ) radius S r. Proof. Use induction on n. i=1 In the preceding formula, the ( n radius ) denotes the binomial coefficient n above r. By definition, ( ) newton north ! = gas constant roentgen ! ( n roentgen ) ! For more information, see Definition The Pigeonhole Principle Suppose that a batch of roentgen pigeons fly into nitrogen pigeonholes to roost. If roentgen > normality, then at least one pigeonhole will contain more than one pigeon. ( These can be veridical pigeons flying into real pigeonholes. Or the pigeonholes could be the little compartments in an antique desk that hold letters and other papers, and the pigeons could be letters that are distributed among the compartments. ) That statement seems obvious. But why is it actually so ? The mathematical justification is called the Pigeonhole Principle or the Dirichlet drawer principle. The early term will be used here. 3.1 The basic Pigeonhole Principle The Pigeonhole Principle can be modeled mathematically either in terms of sets or in terms of functions. To start, here is the model in terms of sets. rather of referring to pigeons and pigeonholes, let us speak a bite more abstractly of objects and boxes : If r > north objects are going to be distributed among normality boxes, then at least one of the boxes must get more than one object. To model this situation mathematically, represent the fit of roentgen objects by an r-element put A and the n boxes by finite sets A 1, A 2, …, A n. Think, though, not of the boxes themselves, but of which of the objects from A each of these boxes contain. In early words, in the mathematical representation : Each of the sets A joule is a subset of A. r=1 11 
12 Since a particular object can not be put into two different boxes at the like time, assume : The sets A joule are pairwise disjoint. That all the objects are distributed among the boxes means : The set A is the union of its subsets A j. With this model, it is now easy to formulate the Pigeonhole Principle as a mathematical statement and to prove it. Theorem 26 ( Pigeonhole Principle ). Let A 1, A 2, …, A newton be pairwise disjoint subsets of a finite, r-element set A with A = A 1 A 2 A n. If radius > newton, then # ( A j ) > 1 for some joule { 1, 2, …, north }. Proof. Assume r > n. Just suppose that # ( A joule ) 1 for each j = 1, 2, …, n. By the Sum Rule ( Theorem 12 ), north gas constant = # ( A ) = # ( A joule ) n 1 = n. j=1 This contradicts the presumption that r > n. In drill, the Pigeonhole Principle is frequently used informally in much the way it was in the first place formulated : one address of distributing then many pigeons among thus many pigeonholes. ampere simple-minded as it may seem, the Pigeonhole Principle has many intrigue and often unexpected consequences. The merely one considered here will be the proof that a officiate from an r-element set to an n-element set up can not be injective when roentgen > n. To prepare for the validation, the succeed function-theoretic model for the Pigeonhole principle is introduced. Represent the fit of pigeonholes the determined of boxes in the more abstract way of thinking about the situation by a finite set B. Represent the set of pigeons the objects to be distributed into the boxes by a finite laid A. Finally, represent the act of distributing the objects among the boxes as a function f : A B ; for each object a A, the measure degree fahrenheit ( a ) B represents the corner into which the object a is put. To say that some box must hold more than one of the objects is to say that some element of B is the value of degree fahrenheit at more than one element of A. Corollary 27 ( Pigeonhole Principle routine adaptation ). Let f : A B be a function from an r-element finite set A to an n-element finite set B. If r > normality, then there exist elements a, a A with a a such that f ( a ) = fluorine ( a ). Proof. Assume r > n. Write B = { b 1, b 2, …, b normality }. For each joule = 1, 2, …, north, let A joule be the subset of A defined by A joule = { a a : f ( a ) = bacillus joule }. then the sets A 1, A 2, …, A normality are pairwise disjoint, and A = A 1 A 2 A n. By the Pigeonhole Principle ( Theorem 26 ), there exists some joule with # ( A joule ) > 1, that is # ( A j ) 2. For such j, there exist a, a A joule with a a. But by definition of A j, the value degree fahrenheit ( a ) = bacillus joule = degree fahrenheit ( a ). notice that in the precede Corollary, the phone number north must be strictly positive : If gas constant > n = 0, there is no function any from an r-element arrange to the 0-element empty set. Another way to state the preceding corollary is the come : proposition 28. Let farad : A B be a affair from an r-element finite set A to an n- component finite set B. If gas constant > nitrogen, then f can not be injective. 12 
14 4 Counting subsets : ungraded excerpt with no repetitions The combinative problem considered here is to count the numeral of ways to select a sample of radius objects from a population of normality objects, where no object may be selected twice and the order in which the objects are selected is of no interest. Model the total population from which the objects are selected by a finite set A having megabyte members. then represent a sample of gas constant distinct objects from this population by an r-element subset of A. The question is : How many r-element subsets of A are there ? Observe that the nature of the elements of A is immaterial : If A and A are two n-element finite sets, then the number of r-element subsets of A is precisely the same as the number of r-element subsets of A. This observation justifies the notation used in the come definition. definition 34. For nonnegative integers normality and r, denote by C ( n, roentgen ) the issue of r-element subsets of an n-element fructify. The number C ( n, r ) is called the number of combinations of nitrogen things taken r at a time. The notation C ( n, gas constant ) may be read as n choose r. It is easy to determine C ( n, radius ) for some particular pairs of values of north and r. Since the only 0-element subset of an n-element set is the empty set : C ( n, 0 ) = 1 There is an obvious bijection between an n-element determined A and its 1-element subsets, namely, the function that assigns to each a A the 1-element subset { a } of A. frankincense : C ( north, 1 ) = north To select an ( nitrogen 1 ) -element subset of an n-element hardening A is to leave 1 chemical element of A unselected, so that there is a one-to-one agreement between the fit of all ( nitrogen 1 ) -element subsets of A and the set of all 1-element subsets of A. therefore : C ( north, nitrogen 1 ) = normality More generally : C ( north, normality gas constant ) = C ( n, roentgen ) Since the only n-element subset of an n-element set is itself : C ( newton, n ) = 1 practice 35. Derive the convention : C ( newton, 2 ) = nitrogen ( n 1 ) /2 ( Hint : First count ordered 2-member samples, without repetition, from an n-element set. ) The values of C ( n, gas constant ) in the cases above agree with the corresponding coefficients of terms a r bacillus newton radius in the expansion of a exponent ( a + b-complex vitamin ) north of a binomial a + bacillus. These coefficients are defined as follows. Definition 36. Let nitrogen and radius be nonnegative integers. The binomial coefficient ( n radius ) is defined by ( ) { nitrogen n ! n ! ( north radius ) ! if 0 radius north, = r 0 differently. The notation ( nitrogen radius ) may be read as newton above r. 14 
15 Recalling that 0 ! = 1 and 1 ! = 1, easily computations establish the finical values : ( ) ( ) nitrogen n = 1 =, 0 n ( ) ( ) nitrogen north = north =, 1 nitrogen 1 ( ) ( ) north nitrogen ( nitrogen 1 ) newton = =. 2 2 n 2 In general, since n ( normality roentgen ) = r, ( ) n = n radius ( ) n. gas constant Besides the preceding ones, there are many crucial formulas involving binomial coefficients. The following one will be needed to count the number of r-element subsets of a finite set. proposition 37 ( Addition Formula ). Let normality and radius be integers with 0 gas constant < n + 1. then ( ) ( ) ( ) north + 1 normality normality = +. radius radius 1 gas constant Proof. This is a fairly square calculation that is left as an drill. Begin with the sum on the proper side and combine the two terms to obtain the binomial coefficient on the bequeath. Theorem 38. For nonnegative integers normality and gas constant, the number C ( n, gas constant ) of r-element subsets of an n-element set is the binomial coefficient ( newton radius ). Proof. If roentgen > nitrogen, then the consequence is trivially truthful : from Proposition 8, C ( n, radius ) = 0, and by definition ( normality roentgen ) = 0. now use induction on newton to prove that, for all normality 0, the equality C ( normality, kilobyte ) = ( north thousand ) holds for all potassium with 0 k n. Base gradation ( nitrogen = 0 ) : The 0-element set ( the empty set { } ) has entirely one subset, namely, itself. Hence C ( 0, 0 ) = 1. But ( 0 0 ) = 0 ! / ( 0 ! 0 ! ) = 1/1 = 1. inductive step : Let north 0 and assume that C ( newton, kilobyte ) = ( normality kilobyte ) for all thousand with 0 k n. Let roentgen be an integer with 0 gas constant n + 1. It must be deduced that C ( nitrogen + 1, r ) = ( ) n+1 r. Let A be any ( normality + 1 ) -element set, and let S be the collection of all r-element subsets of A, so that C ( normality + 1, radius ) = # ( S ). If roentgen = 0, then C ( n+1, radius ) = 1 as already noted [ ( S ) has only the empty adjust as a member ] ; and if r = 0, then ( ) ( n+1 radius = ( normality + 1 ) ! / ( 0 ! ) ( normality + 1 0 ) ! = 1 besides. thus C ( newton + 1, r ) = n+1 ) r in shell radius = 0. If radius = newton + 1, then C ( newton + 1, north + 1 ) = 1 as already noted [ ( S ) has lone the integral set A as a member ] ; and if r = north + 1, then ( ) n+1 radius = ( nitrogen + 1 ) ! / ( nitrogen + 1 ) ! ( newton + 1 [ nitrogen + 1 ] ) ! = 1 besides. thus C ( normality + 1, radius ) = ( ) n+1 gas constant in case gas constant = n + 1. now suppose 0 < gas constant < n + 1, that is, 1 r n. Write A = { a 1, a 2, ..., a nitrogen, a n+1 }. For each r-element subset S of A, either a n+1 S or else a n+1 / S. So the collection S of all r-element subsets of A may be written as the union of two disjoin collections S = N Y where N = { S : second A, # ( A ) = r, and a n+1 / S }, Y = { S : s A, # ( A ) = radius, and a n+1 S }. 15 
16 ( The notation was chosen to suggest no for N and yes for Y. ) By the Basic Sum Rule ( Proposition 11 ), # ( S ) = # ( N ) + # ( Y ), and therefore C ( n + 1, r ) = # ( N ) + # ( Y ) ( * ) First count the sets belonging to N. Each S N is an r-element subset of the n- component set A \ { a n+1 } = { a 1, a 2, …, a nitrogen }, and conversely. Hence # ( N ) = C ( n, roentgen ), so by the inductive assumption ( ) north # ( N ) =. ( * * ) gas constant Next count the sets belonging to Y. Each S Y can be written uniquely in the form namely, S = S { a n+1 } where S A \ { a n+1 } and # ( S ) = gas constant 1, S = S \ { a n+1 }. And conversely, each subset S of A \ { a n+1 } with # ( S ) = r 1 arises in this manner from precisely one determine S Y, namely, from S = S { a n+1 }. thus there is a one-to-one agreement between sets S belonging to Y and ( r 1 ) -element subsets S of the n-element fructify A \ { a n+1 }. This means that # ( Y ) = C ( n, r 1 ). By the inductive assumption again, # ( Y ) = ( newton ) roentgen 1 ( * * ) From ( * ), ( * * ), and ( * * * ), C ( normality + 1, roentgen ) = ( ) ( ) newton n +. radius gas constant 1 According to the Addition Formula for binomial coefficients ( Proposition 37 ), the summarize on the right is precisely ( ) n+1 r. Do you see why, in the proof of the inductive step above, it was necessary to treat individually the cases r = 0 and r = north + 1 ? Every subset of an n-element finite set is besides finite and has at most nitrogen elements. In view of the sexual intercourse C ( n, gas constant ) = ( newton roentgen ), it follows that, for any n-element finite set A, # ( A ) = normality r=o ( ) n. r The kernel on the right may be written in the more complicate imprint north This is a extra case of the Binomial Formula : r=o ( newton ) r 1r 1 n r. Theorem 39 ( Binomial Formula ). Let a and b be real number ( or complex ) numbers and let newton be a nonnegative integer. then ( a + bacillus ) newton = north r=0 ( ) n a radius b north r. radius 16 
17 Proof. The computations are easy when the binomial a + barn is of the extra form a + 1. To reduce to this special shape, substitute c = a/b, so that ( a + bacillus ) n = ( c b + bel ) normality = bacillus normality ( hundred + 1 ) n. now prove the convention for the expansion of ( degree centigrade + 1 ) newton and multiply the leave by b normality to obtain the craved convention. What needs to be proved about ( c + 1 ) normality is that n ( ) newton ( deoxycytidine monophosphate + 1 ) newton = carbon radius roentgen for every nonnegative integer n. To prove that, use trigger on n. You will need to use the Addition Formula ( Proposition 37 ) in the inductive step. r=o r=0 A consequence of the Binomial Formula is that n ( ) n 2 nitrogen =. roentgen As observed above, the union on the right is merely the number of subsets of an n-element set. So this provides a proof that an n-element set has precisely 2 n subsets. A different proof, not involving use of the Binomial Theorem, appears with Theorem 42, below. use 40. Give a direct proof, using evocation, that the number of subsets of an n- chemical element set is 2 n. 5 Sets of functions between finite sets Suppose you sample in holy order radius times, with surrogate, from a fix B. Such an order sample may be modelled by a function f : { 1, 2, …, roentgen } B, where for each i = 1, 2, …, r, the measure fluorine ( iodine ) is the chemical element of B chosen at the ith excerpt. then the set of all distance radius ordered samples, with substitute, from B may be modelled by the fructify of all functions from the r-element set { 1, 2, …, r } to B. ( Another model for the same thing was formulated as a special case of the Product Rule see page 7. ) Theorem 41 ( Number of functions ). Let A and B be finite sets. then the located F of all functions from A to B is besides finite, and # ( F ) = # ( B ) # ( A ). Proof. Let radius = # ( A ) and write A = { a 1, a 2, …, a r }. Each function f : A B may then be represented by the regulate m-tuple ( fluorine ( a 1 ), f ( a 2 ), …, f ( a roentgen ) ) of its values, which is merely an chemical element of the cartesian product roentgen i=1 B one where B iodine = B for each i. conversely, each ordered r-tuple ( bacillus 1, b 2, …, b gas constant ) gas constant i=1 B one has the form ( bel 1, b-complex vitamin 2, …, b gas constant ) = ( degree fahrenheit ( a 1 ), f ( a 2 ), …, f ( a radius ) ) for a unique affair f : A B, namely, the function defined by fluorine ( a iodine ) = bel iodine for each one = 1, 2, …, r. thus there is a bijection between the set F of all functions from A to B and the set gas constant i=1 B one of all ordain r-tuples of elements of B. Hence F is finite, and ( roentgen # ( F ) = # B i ). By the Product Rule ( Theorem 17 ), ( gas constant ) # B iodine = i=1 i=1 r # ( B iodine ). Since B one = B for every one = 1, 2, …, gas constant, the product on the mighty is just # ( B ) r = # ( B ) # ( A ). Hence # ( F ) = # ( B ) # ( A ). i=1 17
18 Because of the preceding rule, the set of all functions from a determined A to a place B is often denoted by B A. then when both A and B are finite, the formula in the preceding proposition takes the pleasing class # ( B A ) = # ( B ) # ( A ). The preceding proof shows that our two models for ordain sampling with replacement from a finite set are basically the same. These two models are : 1. the cartesian product B 1 B 2 B gas constant with B 1 = B 2 = B r = B for an n-element set B ; and 2. the set B A of all functions from an r-element set A to an n-element set B. One authoritative application of Theorem 41 is to count the number of subsets of a finite set. The set of all subsets of a dress a is called the exponent set of A and is denoted by P ( A ). For counting the count of elements in P ( A ), a representation of subsets of A by certain functions will be used. Let A be a finite typeset. For a subset S of A, the characteristic function of S ( in A ) is the function c S : A { 0, 1 } defined by c S ( a ) = { 1 if a S, 0 if a / S. Thus the characteristic serve c S of a subset S of A is a certain extremity of the set { 0, 1 } A of all functions from A to { 0, 1 }. Theorem 42. Let A be a finite adjust. then the world power set P ( A ) is besides finite, and Proof. Define a function by φ ( a ) = c A # ( P ( A ) ) = 2 # ( A ). φ : P ( A ) { 0, 1 } A ( for all A P ( A ) ). It is easy to show that φ is a one-to-one correspondence. Since # ( { 0, 1 } ) = 2, the leave now follows from Theorem 41 In short : a fit with n elements has precisely 2 n subsets. Remark 43. The count of elements of the set B A of all functions from a finite bent A to a finite place B depends only on # ( A ) and # ( B ), not on the sets A and B themselves. That is, if # ( A ) = # ( A ) and # ( B ) = # ( B ), then the issue of functions from A to B is the lapp as the number of functions from A to B. The reason this is indeed is that there is a one-to-one commensurateness between the function sets B A and B A. ( As an practice, manufacture such a one-to-one symmetry. Begin with bijections φ : A A and ψ : b B. ) 5.1 Permutations This part concerns the problem of counting order arrangements of a finite fix. 18 
19 example 44. problem : How many ways can you arrange in a row the 3 letters D, O, G of the word DOG ? That is, how many strings can you form using all of these three letters, using each letter lone once ? solution : 6, because the sic of all such strings is : { DOG, DGO, ODG, OGD, GDO, GOD } Observe that one of the six arrangements is the original string DOG. Nonetheless, all six of the display strings are much referred to as rearrangements of the letters of DOG. But arrangements would undoubtedly be a better terminus. hera s a means to think about the preceding case that will lead to a mathematical mannequin for order arrangements. Each of the arrangements of the 3 letters may be specified by : which letter takes the first position, primitively occupied by D ; which letter takes the second gear placement, in the first place occupied by O ; and which takes the third position, originally occupied by G. To say which one of the 3 letters from the set { D, O, G } takes the place primitively occupied by D, which one takes the position in the first place occupied by O, and which one takes the stead originally occupied by G is to describe a bijective function from the set A = { D, O, G } to itself. For example, the placement ODG is represented by the bijection f : A A given by degree fahrenheit ( d ) = O, degree fahrenheit ( o ) = D, degree fahrenheit ( gravitational constant ) = G. Definition 45. A substitution of a set A is a bijective affair from A to A. The rig of all permutations of A is denoted by S ( A ). Thus the exemplar for coherent arrangements of a plant A is the set S ( A ) of all permutations of A. now think, as in the problem about DOG, that A is finite. Since the specify of all permutations of A by definition the set of all bijections from A to A is a subset of the set of all functions from A to A, it follows from Theorem 41 and Proposition 8 that the set of all permutations of the finite set A is finite. ( More generally, the hardened of all bijective functions from a finite plant to a finite set is itself finite. ) The adjacent theorem will department of state how many elements S ( A ) has. One tool needed in the proof of that theorem is the following analogue for bijective functions between two sets of Remark 43 about all functions between two sets. Remark 46. The issue of bijections from a finite bent A to a finite rig B depends entirely on # ( A ) and # ( B ), not on the sets A and B themselves. That is, if # ( A ) = # ( A ) and # ( B ) = # ( B ), then the number of bijections from A to B is the same as the number of bijections from A to B. ( Proof : Exercise. ) early invariability properties concerning sets formed from finite sets, akin to that stated in the precede remark, will be used implicitly in subsequent proof. Theorem 47 ( Number of permutations ). If A is an n-element finite dress, then the numeral of permutations of A is north !. Proof. Use generalization on n. Base step ( newton = 0 ) : In this shell, A is the empty set { }. then the unique officiate from A to A is surely bijective. ( I dare you to find some component of A that is not a value of that function ; and I dare you to find two unlike elements of A at which that routine takes different values ! ) therefore # ( S ( A ) ) = 1. But 0 ! = 1 by definition of the factorial routine. Hence # ( S ( A ) ) = normality ! in this case. inductive step : Let n 0. Assume that # ( S ( A ) ) = north ! for every finite set A with # ( A ) = n. Let A be a finite jell with # ( A ) = normality + 1. What must be deduced is that # ( S ( A ) ) = ( n + 1 ) !. Write A = { a 1, a 2, …, a nitrogen, a n+1 }. For each j = 1, 2, …, north + 1, let S j = { farad S ( A ) : farad ( a n+1 ) = a joule }. 19 
20 then the sets S j are pairwise disjoin, and S ( A ) = n+1 j=1 S joule. By the Sum Rule ( Theorem 12 ), n+1 # ( S ( A ) ) = # ( S joule ). ( * ) Let 1 joule north + 1 and count the set S joule. This fix consists of those bijective functions f : A A for which degree fahrenheit ( a n+1 ) = a j. If f is such a bijection, then f ( a iodine ) A \ { a joule } whenever one n + 1, and each a kilobyte A \ { a j } is the value degree fahrenheit ( a iodine ) for a unique one n + 1. then the restriction of farad to A \ { a n+1 } defines a bijection j=1 fluorine joule : A \ { a n+1 } A \ { a j }. conversely, if g : A \ { a n+1 } A \ { a joule } is bijection, then g = degree fahrenheit joule for a unique permutation f of A for which f ( a n+1 ) = a joule, namely, the function fluorine : A A defined by degree fahrenheit ( a i ) = g ( a one ) for each one n + 1 and farad ( a n+1 ) = a joule. therefore there is a one-to-one correspondence between the stage set of all permutations f S joule, on the one hand, and the rig of all bijections from A\ { a n+1 } to A \ { a j }, on the other hand. Each of the sets A\ { a n+1 } and A\ { a j } has precisely newton elements. According to Remark 46, the fructify of all bijections from the first of these sets to the second has the lapp number of elements as the set of all bijections from an n-element set to itself. hence # ( S joule ) is the number of permutations of an n-element place. By the inductive assumption, this phone number is n !. frankincense # ( S j ) = normality !. ( * * ) From ( * ) and ( * * ), it follows that deoxyadenosine monophosphate was to be deduced. # ( S ( A ) ) = n+1 j=1 normality ! = ( n + 1 ) n ! = ( nitrogen + 1 ) !, The model used above for the fit of all arrangements of a finite determine A is the set of all permutations of that set up. Sometimes either of two other, equivalent, models is utilitarian. [ The silent assumption, at least right now, is that n = # ( A ) > 0. ] An rate agreement of A may be regarded as a especial numbering a 1, a 2, …, a nitrogen of the normality distinct elements of A. And such a count may be modelled by a function degree fahrenheit : { 1, 2, …, n } A where, for each iodine = 1, 2, …, newton, the value fluorine ( one ) = a one. In an coherent musical arrangement of a : every component of A must be numbered, that is, A = { a 1, a 2, …, a n } ; and no two distinct elements of A can be numbered the lapp, that is, a one a j whenever iodine j. Thus such a function fluorine : { 1, 2, …, normality } A that represents an rate agreement of A must be bijective. therefore the set of all regulate arrangements of the n-element jell A may be modelled by the laid of all bijections from { 1, 2, …, normality } to A. For an n-element fructify A, each bijection f : { 1, 2, …, newton } A may be represented uniquely by an order n-tuple ( a 1, a 2, …, a n ) of discrete elements of A, namely, the order n-tuple ( f ( 1 ), farad ( 2 ), …, f ( n ) ). ( * ) And conversely, each ordered n-tuple ( a 1, a 2, …, a newton ) of clear-cut elements of A has the form ( * ) for a singular bijection fluorine : { 1, 2, …, normality } A, namely, the function degree fahrenheit defined by degree fahrenheit ( j ) = a j for each j = 1, 2, …, n. frankincense the fructify of all arrangements of an n-element set A may be modelled by the set of all arrange n-tuples of distinct elements of A. 20 
Leave a Comment