Combinatorics Theorems and Examples with Practical Applications
Explanation of combinatorics theorems, such as the Division Rule and Rearranging with Duplicates, along with practical examples like counting anagrams and organizing pairs. The Pigeonhole Principle is also illustrated, showcasing applications in various scenarios with clear steps and outcomes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Theorem 9.11 (Division Rule) Let A and B be arbitrary sets. Suppose that there exists a function f : A B such that, for every b B, there are exactly k elements a1, , ak A such that f(ai) = b. (That is, |{a A : f(a) = b}| = k for all b B.) Then |A| = k |B|. What does this mean in practice? The idea is that if we count a number of possibilities in such a way that we consistently double or triple, or n-tuple count, then the true number of possibilities is the original count divided by the repetitions. Example: I need to select two different students from list of 15 applications for a research project where the positions are equivalent. I have 15 choices for the first student that I pick and 14 choices for the second pick or 15*14 choices. But I have double counted, since the positions are equivalent, it does not matter which student I choose first. So the true. Number of choices is 15*14/2 = 105.
Example: How many anagrams (not necessarily words) are there of anagram? anagram has seven letters so there are 7! orderings of the letters, but the order of the three a s does not matter, so we have over-counted by a factor of 3!. The correct number is 7!/3! = 210 Example: How many different orderings of the letters of baggage are there? Again 7 letters so 7! Orderings. However both the three g s and the two a s can be in any order for over-count by a factor of 3!2!. Total is 7!/3!2! = 105
Theorem 9.12 (Rearranging with duplicates) The number of ways to rearrange a sequence containing k different distinct elements {x1, , xk}, where element xiappears nitimes, is (n1+ n2 + + nk)! / (n1!) (n2!) (nk!). The previous examples were examples of this theorem, with some 1! Factors left out.
A more complicated example: Suppose in my class of ten students, I want to have pairs of students work together on the labs. How many different ways can the ten students be divided into lab-pairs? There are 10! Orderings of the students and we can take the first two for a pair and the second two for a pair, etc. How much double -counting have we done? In each pair, the order does not matter, so for each of the 5 pairs, we have over counted by a factor of 2 or a total of 25. So the total should be 10!/ 25. Is this all of the double -counting have we done? No the order of the pairs does not matter! So we have 5! different ways to order the pairs. The final total is 10!/ 5! 25= 10*9*8*7*6/32 = 945
Pigeonhole principle: If |A| > |B| and f:A B is any function, then there exists two distinct elements of A, a1and a2, such that f(a1) = f(a2). In other words, there is some b in B that is hit twice by the function f. The name comes from the idea that in a dovecote a structure with a set of perches of cubby-holes for pigeons/doves if there are more pigeons than perches, at least two pigeons must share (or a pigeon must be left out) Example: In a class of 15 students at Colgate, at least two students get the same grade, because there are only 13 possible grades (A, B, C, D with + or -, and F).
For finite sets we have |A| = |B| if and only if there is a one-to-one and onto function f:A B. In fact, this is one way to define what we mean by saying A and B have the same cardinality. Let s extend this definition of equal cardinality to infinite sets. Show that Z+and 2Z+= {y: x Z with y = 2x} have the same cardinality. f: Z+ 2Z+is one-to-one and onto! So a subset of Z+, the positive even integers, has the same cardinality. We call a set with the same cardinality as Z+countable.
The set of positive rational numbers is countable. Consider the grid 1/1 1/2 1/3 1/4 1/5 .. Map Z+ to the rationals by following the arrows, skipping fractions not in lowest terms: f is defined by this and is one-to-one and onto. 1 2 3 4 5 6 7 1/1 2/1 1/2 3/1 1/3 4/1 3/2 skip 2/2. skip 4/2,3/3,2/4 2/1 2/2 2/3 2/4 2/5 3/1 3/2 3/3 3/4 3/5 4/1 4/2 4/3 4/4 4/5 5/1 5/2 5/3 5/4 5/5 8 2/3 9 1/4 10 5/1 11 1/5 12 6/1
The real numbers R, are not countable. In fact, the set [0,1) = {r R : 0 <= r < 1} is not countable. Proof by contradiction: Assume [0,1) is countable. Then there is an f: Z+ {[0,1) that is 1-1 and onto List the function (the dijare the successive digits of each real number) 1 f(1) = 0.d11d12d13d14d15d16 2 f(2) = 0.d21d22d23d24d25d26 3 f(3) = 0.d31d32d33d34d35d36 4 f(4) = 0.d41d42d43d44d45d46 Construct the real number x = 0.x11x12x13x14x15x16 where if d11= 1 then x11= 0 and if d11!= 1, then x11= 1. x 0,1) but there is no n Z+with f(n) = x. This contradicts our assumption, so [0,1) and hence R, are not countable. This is the diagonalization argument.
The book uses the diagonalization argument to prove that |Z+| < |P(Z+)|. The power set of the positive integers is not countable.
Permutations and Combinations A permutation is an ordering of distinct elements We can have a permutation of all the elements in a set S. There are |S|! We can have permutations of k elements from a set S (k < |S|). There are |S|!/(n-k)! This follows from our multiplication rule A combination is a subset of elements from a given set S, where order does not matter. There is only one subset of the same size as S. If n = |S|, then the number of subsets of S of size k is n!/k!(n-k)! This follows from our division rule for double counting, we have n!/(n-k)! Orderings of k elements from above, but we don t care about the order of the k elements, so we have overcounted by a factor of k!, to get n!/k!(n-k)! (nk) = n!/k!(n-k)! We say this is n choose k
How many 8-bit strings with exactly 3 ones? Choose 3 out of 8 positions to make ones. (83) = 8!/3!5! = 56 How many possible draw poker hands from 52 card deck? (5 cards in a hand) (525) = 52!/5!47! = 2,598,960 How many draw poker hands have 4 of a kind? 13 (value of the four) * 48 (other card) = 624 How many draw poker hands have exactly one pair? 13 (val of pair) (42) (which suits) (123) (other vals) 43(suits of others)= 1,098,240
Example of the repetition-allowed order-doesnt matter case. You have five hours to study on a given day. Assuming you assign one- hour blocks to three classes, not necessarily together, how many possible assignments. n is 3, k is 5, so (n+k-1k) = (75) = 21.
Binomial Theorem: (a + b)n = (nn) an + (nn-1) an-1b + (nn-2) an-2b2+ + (n1) abn-1 + (n0) bn (a+b)2 = a2 + 2ab+ b2 (a+b)3 = a3 + 3a2b + 3ab2 + b3 etc. Why? For each power of a, k, we need to choose k of the (a+b) factors that contribute an a, the rest contribute a b. This is (nk)
Facts about combinations (nk) = (nn-k) (nk) = (n-1k) + (n-1k-1) Pascal s identity Why: To find (nk) consider one item. If you include it, then you have (n-1k-1) more choices. If you do not include it, you have (n-1k) more choices. These are the only possibilities, so the total number is their sum
