📄 chap06.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 6: COUNTING AND PROBABILITY</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="partii.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap05.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="073a_129d">CHAPTER 6: COUNTING AND PROBABILITY<a name="073a_129d"></h1><P>
This chapter reviews elementary combinatorics and probability theory. If you have a good background in these areas, you may want to skim the beginning of the chapter lightly and concentrate on the later sections. Most of the chapters do not require probability, but for some chapters it is essential.<P>
<a name="073a_129c">Section 6.1 reviews elementary results in counting theory, including standard formulas for counting permutations and combinations. The axioms of probability and basic facts concerning probability distributions are presented in Section 6.2. Random variables are introduced in Section 6.3, along with the properties of expectation and variance. Section 6.4 investigates the geometric and binomial distributions that arise from studying Bernoulli trials. The study of the binomial distribution is continued in Section 6.5, an advanced discussion of the "tails" of the distribution. Finally, Section 6.6 illustrates probabilistic analysis via three examples: the birthday paradox, tossing balls randomly into bins, and winning streaks.<P>
<h1><a name="073c_0001">6.1 Counting<a name="073c_0001"></h1><P>
Counting theory tries to answer the question "How many?" without actually enumerating how many. For example, we might ask, "How many different <I>n</I>-bit numbers are there?" or "How many orderings of <I>n</I> distinct elements are there?" In this section, we review the elements of counting theory. Since some of the material assumes a basic understanding of sets, the reader is advised to start by reviewing the material in Section 5.1. <P>
<h2>Rules of sum and product</h2><P>
A set of items that we wish to count can sometimes be expressed as a union of disjoint sets or as a Cartesian product of sets.<P>
<a name="073d_129d"><a name="073d_129e">The <I><B>rule of sum</I></B> says that the number of ways to choose an element from one of two <I>disjoint</I> sets is the sum of the cardinalities of the sets.That is, if <I>A</I> and <I>B</I> are two finite sets with no members in common, then |<I>A</I> <img src="../images/wideu.gif"> <I>B</I>| = |<I>A| + |B|, </I>which follows from equation (5.3). For example, each position on a car's license plate is a letter or a digit. The number of possibilities for each position is therefore 26 + 10 = 36, since there are 26 choices if it is a letter and 10 choices if it is a digit.<P>
<a name="073d_129f"><a name="073d_12a0">The<I><B> rule of product</I></B> says that the number of ways to choose an ordered pair is the number of ways to choose the first element times the number of ways to choose the second element. That is, if <I>A</I> and <I>B</I> are two finite sets, then |<I>A</I> <img src="../images/mult.gif"> <I>B| </I>= |<I>A| </I><img src="../images/dot10.gif"> |<I>B|</I>, which is simply equation (5.4). For example, if an ice-cream parlor offers 28 flavors of ice cream and 4 toppings, the number of possible sundaes with one scoop of ice cream and one topping is 28 <img src="../images/dot10.gif"> 4 = 112.<P>
<P>
<h2>Strings</h2><P>
<a name="073e_12a1"><a name="073e_12a2">A <I><B>string</I></B> over a finite set <I>S</I> is a sequence of elements of <I>S</I>. For example, there are 8 binary strings of length 3:<P>
<pre>000, 001, 010, 011, 100, 101, 110, 111 .</sub></sup></pre><P>
<a name="073e_12a3"><a name="073e_12a4"><a name="073e_12a5">We sometimes call a string of length <I>k</I> a <I><B>k-string</I>.</B> A <I><B>substring</I></B> <I>s</I>' of a string <I>s</I> is an ordered sequence of consecutive elements of <I>s</I>. A <I><B>k-substring</I></B><I> </I>of a string is a substring of length <I>k</I>. For example, 010 is a 3-substring of 01101001 (the 3-substring that begins in position 4), but 111 is not a substring of 01101001.<P>
A <I>k</I>-string over a set <I>S</I> can be viewed as an element of the Cartesian product <I>S<SUP>k</I></SUP> of <I>k</I>-tuples; thus, there are |<I>S|</I><SUP><I>k</I></SUP> strings of length <I>k</I>. For example, the number of binary <I>k</I>-strings is 2<I><SUP>k</I></SUP>. Intuitively, to construct a <I>k</I>-string over an <I>n</I>-set, we have <I>n</I> ways to pick the first element; for each of these choices, we have <I>n</I> ways to pick the second element; and so forth <I>k</I> times. This construction leads to the <I>k</I>-fold product <I>n </I><img src="../images/dot10.gif"> n <I><img src="../images/dot10.gif"><img src="../images/dot10.gif"><img src="../images/dot10.gif"> n</I> = <I>n<SUP>k</I></SUP> as the number of <I>k</I>-strings.<P>
<P>
<h2>Permutations</h2><P>
<a name="073f_12a6">A <I><B>permutation</I></B> of a finite set <I>S</I> is an ordered sequence of all the elements of <I>S</I>, with each element appearing exactly once. For example, if <I>S</I> = {<I>a, b, c</I>}, there are 6 permutations of <I>S</I>:<P>
<pre><I>abc, acb, bac, bca, cab, cba .</I></sub></sup></pre><P>
There are <I>n</I>! permutations of a set of <I>n</I> elements, since the first element of the sequence can be chosen in <I>n</I> ways, the second in <I>n</I> - 1 ways, the third in <I>n</I> - 2 ways, and so on.<P>
<a name="073f_12a7">A <I><B>k-permutation</I></B> of <I>S</I> is an ordered sequence of <I>k</I> elements of <I>S</I>, with no element appearing more than once in the sequence. (Thus, an ordinary permutation is just an <I>n</I>-permutation of an <I>n</I>-set.) The twelve 2-permutations of the set {<I>a, b, c, d</I>} are<P>
<pre><I>ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc.</I></sub></sup></pre><P>
The number of <I>k</I>-permutations of an <I>n</I>-set is<P>
<img src="101_a.gif"><P>
<h4><a name="073f_12a8">(6.1)<a name="073f_12a8"></sub></sup></h4><P>
since there are <I>n</I> ways of choosing the first element, <I>n</I> - 1 ways of choosing the second element, and so on until <I>k</I> elements are selected, the last being a selection from <I>n</I> - <I>k</I> + 1 elements.<P>
<P>
<h2>Combinations</h2><P>
<a name="0740_12a8"><a name="0740_12a9">A <I><B>k-combination</I></B> of an <I>n</I>-set <I>S</I> is simply a <I>k</I>-subset of <I>S</I>. There are six 2-combinations of the 4-set {<I>a, b, c, d</I>}:<P>
<pre><I>ab, ac, ad, bc, bd, cd .</I></sub></sup></pre><P>
(Here we use the shorthand of denoting the 2-set {<I>a,b</I>} by <I>ab</I>, and so on.) We can construct a <I>k</I>-combination of an <I>n-</I>set by choosing <I>k</I> distinct (different) elements from the <I>n-</I>set.<P>
The number of <I>k</I>-combinations of an <I>n-</I>set can be expressed in terms of the number of <I>k</I>-permutations of an <I>n</I>-set. For every <I>k-</I>combination, there are exactly <I>k</I>! permutations of its elements, each of which is a distinct <I>k</I>-permutation of the <I>n</I>-set. Thus, the number of <I>k</I>-combinations of an <I>n</I>-set is the number of <I>k</I>-permutations divided by <I>k</I>!; from equation (6.1), this quantity is<P>
<img src="101_b.gif"><P>
<h4><a name="0740_12aa">(6.2)<a name="0740_12aa"></sub></sup></h4><P>
For <I>k</I> = 0, this formula tells us that the number of ways to choose 0 elements from an <I>n</I>-set is 1 (not 0), since 0! = 1.<P>
<P>
<h2>Binomial coefficients</h2><P>
<a name="0741_12aa"><a name="0741_12ab"><a name="0741_12ac">We use the notation <img src="101_c.gif"> (read "<I>n</I> choose <I>k</I>") to denote the number of <I>k</I>-combinations of an <I>n</I>-set. From equation (6.2), we have<P>
<img src="101_d.gif"><P>
<h4><a name="0741_12ae">(6.3)<a name="0741_12ae"></sub></sup></h4><P>
This formula is symmetric in <I>k</I> and <I>n</I> - <I>k</I>:<P>
<img src="101_e.gif"><P>
<h4><a name="0741_12af">(6.4)<a name="0741_12af"></sub></sup></h4><P>
<a name="0741_12ad">These numbers are also known as <I><B>binomial coefficients</I></B>, due to their appearance in the <I><B>binomial expansion</I></B><I>:</I><P>
<img src="101_f.gif"><P>
<h4><a name="0741_12b0">(6.5)<a name="0741_12b0"></sub></sup></h4><P>
A special case of the binomial expansion occurs when <I>x</I> = <I>y</I> = 1:<P>
<img src="102_a.gif"><P>
<h4><a name="0741_12b1">(6.6)<a name="0741_12b1"></sub></sup></h4><P>
This formula corresponds to counting the 2<I><SUP>n</I></SUP> binary <I>n</I>-strings by the number of 1's they contain: there are <img src="102_b.gif"> binary <I>n</I>-strings containing exactly <I>k </I>1's, since there are <img src="102_c.gif"> ways to choose <I>k</I> out of the <I>n</I> positions in which to place the 1's.<P>
There are many identities involving binomial coefficients. The exercises at the end of this section give you the opportunity to prove a few.<P>
<P>
<h2>Binomial bounds</h2><P>
<a name="0742_12ae">We sometimes need to bound the size of a binomial coefficient. For 1 <img src="../images/lteq12.gif"> <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>, we have the lower bound<P>
<img src="102_d.gif"><P>
<h4><a name="0742_12b1">(6.7)<a name="0742_12b1"></sub></sup></h4><P>
Taking advantage of the inequality <I>k</I>! <img src="../images/gteq.gif"> (<I>k</I>/<I>e</I>)<I><SUP>k </I></SUP>derived from Stirling's formula (2.12), we obtain the upper bounds<P>
<img src="102_e.gif"><P>
<h4><a name="0742_12b2">(6.8)<a name="0742_12b2"></sub></sup></h4><P>
<h4><a name="0742_12b3">(6.9)<a name="0742_12b3"></sub></sup></h4><P>
For all 0 <img src="../images/lteq12.gif"> <I>k</I> <img src="../images/lteq12.gif"> <I>n</I>, we can use induction (see Exercise 6.1-12) to prove the bound<P>
<img src="102_f.gif"><P>
<h4><a name="0742_12b4">(6.10)<a name="0742_12b4"></sub></sup></h4><P>
where for convenience we assume that 0<SUP>0</SUP> = 1. For <I>k</I> = <img src="../images/lambdauc.gif"><I>n</I>, where 0 <img src="../images/lteq12.gif"> <img src="../images/lambdauc.gif"> <img src="../images/lteq12.gif"> 1, this bound can be rewritten as<P>
<img src="102_g.gif"><P>
<h4><a name="0742_12b5">(6.11)<a name="0742_12b5"></sub></sup></h4><P>
<h4><a name="0742_12b6">(6.12)<a name="0742_12b6"></sub></sup></h4><P>
where<P>
<pre><I>H</I>(<img src="../images/lambdauc.gif">) = -<img src="../images/lambdauc.gif">lg<img src="../images/lambdauc.gif"> - (1 - <img src="../images/lambdauc.gif">) lg (1 - <img src="../images/lambdauc.gif">)</sub></sup></pre><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -