{"id":15810,"date":"2012-12-10T09:01:59","date_gmt":"2012-12-10T16:01:59","guid":{"rendered":"https:\/\/gmatclub.com\/blog\/?p=15810"},"modified":"2012-12-07T15:00:18","modified_gmt":"2012-12-07T22:00:18","slug":"gmat-math-calculating-combinations","status":"publish","type":"post","link":"https:\/\/gmatclub.com\/blog\/gmat-math-calculating-combinations\/","title":{"rendered":"GMAT Math: Calculating Combinations"},"content":{"rendered":"

\"\"First, a few practice questions.\u00a0 Remember ---\u00a0no calculator<\/a>!<\/p>\n

1) A radio station has to choose three days of the seven in a week to broadcast a certain program, and that set will repeat each week.\u00a0 The program can be broadcast equally on any of the seven weekdays ---- weekdays vs. weekends don't matter at all ----\u00a0 nor does it matter whether the days the program airs are adjacent or not.\u00a0 Absolutely any three of the seven weekdays can be chosen.\u00a0\u00a0 How many different three-day combinations of the seven weekdays can be constructed?<\/p>\n

    \n
      \n
    1. 9<\/li>\n
    2. 15<\/li>\n
    3. 21<\/li>\n
    4. 35<\/li>\n
    5. 56<\/li>\n
        2) Claudia can choose any two of four different candles and any 8 of 9 different flowers for a centerpiece arrangement.\u00a0 Given these choices, how many centerpiece arrangements can she design?<\/p>\n
          \n
        1. 54<\/li>\n
        2. 72<\/li>\n
        3. 96<\/li>\n
        4. 144<\/li>\n
        5. 432<\/li>\n
            3) A newly-wed couple is using a website to design an eBook Wedding Album to distribute to their friends and families.\u00a0 The template they have chosen has places for 3 large photos and 19 smaller photos.\u00a0 The couple has 6 large photos they could use for those three slots, and 21 smaller photos they could use for those 19 slots.\u00a0 Given these choices, how many different possible albums could they create?<\/p>\n
              \n
            1. 3,150<\/li>\n
            2. 4,200<\/li>\n
            3. 5,040<\/li>\n
            4. 20,520<\/li>\n
            5. 84,000<\/li>\n
                In this post, we'll discuss how to handle questions like this --- without a calculator.<\/ol>\n<\/ol>\n<\/ol>\n<\/ol>\n<\/ol>\n<\/ol>\n<\/ol>\n

                 <\/p>\n

                Combinations<\/h2>\n

                Mathematically, a\u00a0combination<\/strong>\u00a0is a group of things, irrespective of order.\u00a0 For example, {A, B, D} and {D, A, B} and {B, A, D} are all the same combination --- order doesn't matter at all. The expression nCr (read \"n choose r\") is the expression for the number of combinations of r things, r choices, you can make from a pool of n unique items.\u00a0 For example,<\/p>\n

                6C3 = the number of combinations of three one can choose from a pool of six unique items.<\/p>\n

                In a previous post about\u00a0combinations<\/a>, I give the following formula for nCr<\/p>\n

                \"\"<\/a><\/p>\n

                where the exclamation point (\"!\") is the\u00a0factorial<\/a>\u00a0symbol --- n! means the product of all the positive integers from n down to 1.\u00a0 Using this formula, we could compute the value of 6C3<\/p>\n

                \"\"<\/a><\/p>\n

                So, it turns out, there are twenty ways to pick a set of three items from a pool of six unique items.\u00a0 That's one way to calculate nCr, but it's not the only way.<\/p>\n

                 <\/p>\n

                Pascal's Triangle<\/h2>\n

                The mathematician and philosopher\u00a0Blaise Pascal<\/a>\u00a0(1623 \u2013 1662) created a magical triangular array of numbers known now as\u00a0Pascal's Triangle<\/a>:<\/p>\n

                \"\"<\/a><\/p>\n

                How does this pattern work?\u00a0 Well, of course, the edges are diagonals of 1's.\u00a0 Every inside number is the sum of the two numbers above it in the previous row, diagonally to the left and diagonally to the right.\u00a0 For example, the 2 is the sum 1+1; both 3's are the sum 1+2; both 4's are the sums 1+3; the 6 is the sum 3+3, etc.\u00a0 They often show Pascal's Triangle to grade school students to give them practice with addition.<\/p>\n

                Despite its relatively easy origins, Pascal's Triangle is a treasure trove of miraculous mathematical properties.\u00a0 Most relevant for us right now is: Pascal's Triangle is, among other things, an array of all possible nCr's.<\/p>\n

                nCr = the rth entry of the nth row of Pascal's Triangle<\/p>\n

                In that definition, we have to be careful --- we have to start counting\u00a0at zero<\/em>\u00a0instead of one.\u00a0 The top 1 on Pascal's Triangle is the zeroth row, zeroth entry, 0C0 = 1 (a relatively meaningless number in terms of combinations!)\u00a0 The next row (1, 1) is the first row, and the next row is the second row (1, 2, 1), etc.\u00a0 Notice that the second number in any row (as well as the penultimate number in any row) equals the row number. The first number (always 1) is actually the zeroth entry, so that second number would actually be the first entry --- the first entry of the nth row always equals n.\u00a0 In other words<\/p>\n

                nC1 = n<\/p>\n

                That makes sense: if we have n different items, we have exactly n ways of selecting any one item.\u00a0 Those entries, the first entries of each row, line along a diagonal down the left side of the triangle.\u00a0 Because of the complete symmetry of the triangle, this always equals the numbers on the corresponding diagonals on the right side, which would be the (n-1) entries of each row.\u00a0 Thus:<\/p>\n

                nC1 = nC(n-1) = n<\/p>\n

                When you have to figure out nCr when n & r are both relatively small numbers, it may be easier simply to jot down the first few rows of Pascal's Triangle.\u00a0 For example, with what we have showing, we can see that 6C3, the 3rd entry of the 6th row, is 20 --- the same as the answer we found via the factorials formula.<\/p>\n

                Things get even more interesting when we move to the next diagonal in, shown in green here:<\/p>\n

                \"\"<\/a><\/p>\n

                These numbers, the set of the second entries in each row, are the\u00a0triangular numbers<\/a>.\u00a0 Among other things, the second entry in the n row is the sum of the first n-1 positive integers.\u00a0 For example<\/p>\n

                3 = 2 + 1<\/p>\n

                6 = 3 + 2 + 1<\/p>\n

                10 = 4 + 3 + 2 + 1\u00a0 etc.<\/p>\n

                The formula for this is:<\/p>\n

                \"\"<\/a><\/p>\n

                Because we have a formula, we can calculate this for much higher numbers.\u00a0 For 21C2, we would have to write out everything to the twenty-first row of Pascal's Triangle, an arduous undertaking.\u00a0 Rather, we could simply use the formula<\/p>\n

                \"\"<\/a><\/p>\n

                Notice that the symmetry of Pascal's Triangle also provides tremendous insight into the nature of the nCr numbers.\u00a0 First of all, in any row, the second entry, the triangular number in that row, must be equal to the third-to-last entry of the row, that is, the (n-2) entry of the row.\u00a0 Thus<\/p>\n

                \"\"<\/a><\/p>\n

                Thus, via the triangular numbers, we have a formula, not only for the second entry of each row, but also for the third-to-last entry of every row.\u00a0 Thus, it's very easy to figure out the first three or last three numbers in any row.\u00a0 More generally, symmetry guarantees that:<\/p>\n

                nCr = nC(n-r)<\/p>\n

                If you think about combinations this makes sense: if we have a pool of n unique items, then every time we choose a unique set of r items, we necessarily exclude a corresponding unique set of (n-r) items.\u00a0 In other words, there is necessarily a 1-to-1 correspondence between unique sets of r elements and unique sets of the other (n-r) elements ---- because there's a 1-to-1 correspondence, the number of each must always be the same.\u00a0 This is precisely what that equation says.<\/p>\n

                 <\/p>\n

                Practice<\/h2>\n

                That discussion was liberally peppered with hints about how to do the above three questions.\u00a0 If you had trouble with them on the first pass, you may want to give them a second look before proceeding to the explanations below.\u00a0 Here's an additional question from inside Magoosh:<\/p>\n

                4)\u00a0https:\/\/gmat.magoosh.com\/questions\/847<\/a><\/p>\n

                 <\/p>\n

                Practice question explanations<\/h2>\n

                1) Behind the story, we are really being asked to evaluate 7C3.\u00a0 We could use the factorial formula, but above we conveniently happen to have Pascal's Triangle written out to the seventh row.\u00a0 We see that 7C3, the third entry of the seventh row, is 35.\u00a0 Answer =\u00a0D<\/strong>.<\/p>\n

                2) For this one, we have to use the\u00a0Fundamental Counting Principle<\/a>\u00a0(FCP) as well as information about combinations.\u00a0 For the flowers, we want 9C8,\u00a0 which by the symmetry of Pascal's Triangle, has to equal 9C1, the first entry in the row, which of course equals the row number.<\/p>\n

                9C8 = 9C1 = 9<\/p>\n

                That's the number of flower combinations.\u00a0 For the candles, 4C2, we read the second entry of the fourth row of Pascal's Triangle.<\/p>\n

                4C2 = 6<\/p>\n

                Now, by the FCP, we multiply these for the total number of centerpiece arrangements: 6*9 = 54.\u00a0 Answer =\u00a0A<\/strong><\/p>\n

                3) For the large photos, we need 6C3, which we calculated in the article:<\/p>\n

                6C3 = 20<\/p>\n

                For the smaller photos, we need 21C19, which by symmetry must equal 21C2, and we have a formula for that.\u00a0 In fact, in the article above, we already calculated that 21C2 = 210.<\/p>\n

                Now, by the FCP, we just multiply these: total number of possible albums = 20*210 = 4200.\u00a0 Answer =\u00a0B<\/strong><\/p>\n

                This post was written by Mike McGarry, GMAT expert at Magoosh<\/a>, and originally posted here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

                First, a few practice questions.\u00a0 Remember —\u00a0no calculator! 1) A radio station has to choose three days of the seven in a week to broadcast a certain program, and that…<\/p>\n","protected":false},"author":133,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[783,243,736],"tags":[],"class_list":["post-15810","post","type-post","status-publish","format-standard","hentry","category-magoosh-blog","category-blog","category-quant-gmat","entry"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/posts\/15810","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/users\/133"}],"replies":[{"embeddable":true,"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/comments?post=15810"}],"version-history":[{"count":3,"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/posts\/15810\/revisions"}],"predecessor-version":[{"id":15814,"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/posts\/15810\/revisions\/15814"}],"wp:attachment":[{"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/media?parent=15810"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/categories?post=15810"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/gmatclub.com\/blog\/wp-json\/wp\/v2\/tags?post=15810"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}