Counting Il There are(5)different 5-topping pizzas, if 14 toppings are available he k-element subsets of an n-element set are sometimes called k-combinations. There are a great many similar-sounding terms: permutations, r-permutations, permutations with repetition, combinations with repetition, permutations with indistinguishable ob- cts, and so on For example the bookkeeper rule is sometimes called the "formula for permutations with indistinguishable objects". Broadly speaking, permutations concern se- quences and combinations concern subsets. However, the counting rules weve taught you are sufficient to solve all these sorts of problems without knowing this jargon, so we'll p it 1.4 Word of caution Someday you might refer to the bookkeeper Rule in front of a roomful of colleagues and discover that theyre all staring back at you blankly. This is not because theyre dumb, but rather because we just made up the name"Bookkeeper Rule". However, the rule is excellent and the name is apt, so we suggest that you play through: You know? The Bookkeeper Rule? Don' t you guys know anything??? 2 Binomial theorem Counting gives insight into one of the basic theorems of algebra. a binomial is a sum of two terms, such as a+ b Now lets consider a postive, integral power of a binomial Suppose we multiply out this expression completely for, say, n=4 (a+b)=aaaa + aaab+aaba + aabb +abaa +abab +abba +abbb + baaa+ baab+baba t babb +bbaa+bab+bbba +bbbb terms with k copies of b and n- k copies of a is of as and bs. Therefore, the number of notice that there is one term for every sequence by the Bookkeeper Rule. Now lets group equivalent terms, such as aaab aaba abaa baaa. Then the coefficient of a"-b is(r). So for n =4, this means +2=(0)+()+()+()+() In general, this reasoning gives the Binomial Theorem� � � � � � � � � � � � � � � � Counting III 3 • There are 14 different 5­topping pizzas, if 14 toppings are available. 5 The k­element subsets of an n­element set are sometimes called k­combinations. There are a great many similar­sounding terms: permutations, r­permutations, permutations with repetition, combinations with repetition, permutations with indistinguishable ob￾jects, and so on. For example, the Bookkeeper Rule is sometimes called the “formula for permutations with indistinguishable objects”. Broadly speaking, permutations concern se￾quences and combinations concern subsets. However, the counting rules we’ve taught you are sufficient to solve all these sorts of problems without knowing this jargon, so we’ll skip it. 1.4 Word of Caution Someday you might refer to the Bookkeeper Rule in front of a roomful of colleagues and discover that they’re all staring back at you blankly. This is not because they’re dumb, but rather because we just made up the name “Bookkeeper Rule”. However, the rule is excellent and the name is apt, so we suggest that you play through: “You know? The Bookkeeper Rule? Don’t you guys know anything???” 2 Binomial Theorem Counting gives insight into one of the basic theorems of algebra. A binomial is a sum of two terms, such as a + b. Now let’s consider a postive, integral power of a binomial: (a + b) n Suppose we multiply out this expression completely for, say, n = 4: (a + b) 4 = aaaa + aaab + aaba + aabb + abaa + abab + abba + abbb + baaa + baab + baba + babb + bbaa + bbab + bbba + bbbb Notice that there is one term for every sequence of a’s and b’s. Therefore, the number of terms with k copies of b and n − k copies of a is: n! n = k! (n − k)! k by the Bookkeeper Rule. Now let’s group equivalent terms, such as aaab = aaba = abaa = n baaa. Then the coefficient of an−kbk is . So for n = 4, this means: k 4 4 4 4 4 4 b0 2 b2 1 b3 0 b4 (a + b) 4 = a + a 3 b1 + a + a + a 0 · 1 · 2 · 3 · 4 · In general, this reasoning gives the Binomial Theorem: