#21:The Art of Counting,Part II March14,2009
.(2)
(n−k)!
Explain why equation(2)is equal to equation(1).(Hint:write out the factorials and see )
1c Brent Yorgey2008.License:Creative Commons Attribution-Noncommercial3.0US.
The number of permutations of k out of n things is implemented on many nPr
calculators(probably including yours)as a function called nPr.For example,
6nPr3tells you how many ways there are to put three out of six things in
some order,that is,the number of permutations of three out of six objects.
2Combinations
What if we just want to know the number of ways of choosing a certain combinations
number of things from a bigger set of possibilities,but we don’t care about
the order?For example,suppose you are at the store and there are six
kinds of fruit to choose from(apples,bananas,cherries,dates,eggplants1,
andfigs),but you only have enough money to buy exactly three,and you
want to know how many different choices you can make.In this case,the
order in which you buy your three fruits doesn’t make any difference;the
only thing that matters is which three fruits you get.A set of objects chosen
from some larger set,where we don’t care about the order of the objects,is
called a combination.
Problem  6.So,how many ways are there to buy three out of the six fruity goodness
fruits?For now,just list the different possibilities(you can abbreviate the
fruits using just theirfirst letter).Which three would you buy?
Problem7.How many permutations of three out of six fruits are there?
(For example,maybe you plan to buy the fruits one at a time instead of all
at once,on Monday,Wednesday,and Friday,so now you care about which
order you buy them in.)
Problem8.Is your answer to Problem7bigger or smaller than your answer
to Problem6?Why?How much bigger or smaller is it?
Let’s think about how to count the number of ways to choose k out of n counting
combinations things,when we don’t care about the order.We already know how to count them when we do care about the order,and want to count each ordering
separately,but this is too many.For example,if we’re trying to count the
number of ways to choose two out of three things,we could list all the
permutations of two out of three things—AB,BA,AC,CA,BC,CB—but
this is too many,we’ve listed each combination of things twice!Since we
don’t care about the order,AB is really the same as BA,AC is the same as
CA,and BC is the same as CB,so there are three ways to choose two out
of three things,not six.sort of things什么意思
But herein lies the key.Suppose we are choosing k out of n things.We combinations from
permutations already know how to count the permutations of k out of n things;as we have noted,this overcounts the combinations,but we canfigure out exactly by
how much it overcounts.If we count permutations,we count every possible
order of each group of k things,but we instead want to just count this group
once.Well,how many possible orders are there of k things?Easy—there
are k!(that’s k factorial,not me being excited about how easy it is).So
if we just take the number of permutations and divide by k!,we get the
number of combinations.
C(n,k)= n k =P(n,k)k!(n−k)!.(3) Combinations come up so often that they have a special notation: n k , binomial coefficients
pronounced“n choose k”,denotes the number of combinations of k out of
n things. n k is also often called a“binomial coefficient”(for reasons we
will see later).You can write it in L A T E X as\binom{n}{k}.Your calculator
probably has a function to compute combinations called nCr.
Problem9.Compute n k for every value of n from0to7and every value
of k from0to n(that is,compute 00 ; 10 and 11 ; 20 , 21 ,and 22 ;and so
on).Make a table with n down the side and k along the top.What patterns
do you notice?Can you explain any of the patterns?
Problem10.Compute 105 .
Problem11.Go back and look at Problem17from last week’s assign-
ment,and compare it with your table from Problem9,and your answer to
Problem10.What do you notice?Can you explain the relationship?
3More problems
Problem12.How many different poker hands are there?(A poker hand
isfive cards.)
Problem13.Remember Fred from Problem17in last week’s assignment?
What if his school was at7th and K streets?How many ways could he walk
to school then?
3c Brent Yorgey2008.License:Creative Commons Attribution-Noncommercial3.0US.
Problem14.Fred likes going to Joe’s Pizza Parlor,where you can get a Small,Medium,Large,or Ridiculous pizza with your choice of any three toppings.In fact,he likes it so much that he goes once every day and eats an entire pizza.Out of principle,however,Fred never orders a pizza that he has ordered before.(Fred likes Trying New Things.)If Joe’s has seventeen toppings to choose from,how long will Fred be able to go to Joe’s before he is forced to order a pizza that he has ordered before?
Problem15.Each day,after his daily pizza,Fred also likes going to the Tastie-Freeze Ice Cream Store and getting a banana split.A banana split consists of three scoops of ice cream(each of the three scoops must be a different kind of ice cream)and any two different toppings.Recall that Tastie-Freeze has thirty kinds of ice cream and four toppings.How many different banana splits could Fred order?
Problem16.What if the three scoops in a banana split do not necessarily have to be different(Fred could get three scoops of the same kind of ice cream,or two of one kind and one of another)?How many different banana splits are there now?(Hint:break the types of banana splits down into splits with three different kinds of ice cream,with two kinds,and with one kind,and count each sort of split separately.Keep in mind that the order of the scoops doesn’t matter—but getting two scoops of chocolate and one of vanilla IS different than getting two vanilla and one chocolate!)
4c Brent Yorgey2008.License:Creative Commons Attribution-Noncommercial3.0US.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。