Robert P. Dobrow

Probability


Скачать книгу

alt="k"/> of these factors to choose an x from, and the remaining n minus k factors to choose a y from. There are StartBinomialOrMatrix n Choose k EndBinomialOrMatrix ways to do this. Thus, the coefficient of x Superscript k Baseline y Superscript n minus k is StartBinomialOrMatrix n Choose k EndBinomialOrMatrix, which gives the result. image

2 Superscript n Baseline equals sigma-summation Underscript k equals 0 Overscript n Endscripts StartBinomialOrMatrix n Choose k EndBinomialOrMatrix 1 Superscript k Baseline 1 Superscript n minus k Baseline equals sigma-summation Underscript k equals 0 Overscript n Endscripts StartBinomialOrMatrix n Choose k EndBinomialOrMatrix period Schematic illustration of Pascal's triangle.

      There is a combinatorial interpretation of this identity. The left-hand side counts the number of sets of size n. The right-hand side counts the number of such sets by summing the number of subsets of size 0, size 1 comma ellipsis, and size n.

      (1.5)StartBinomialOrMatrix n Choose k EndBinomialOrMatrix equals StartBinomialOrMatrix n minus 1 Choose k minus 1 EndBinomialOrMatrix plus StartBinomialOrMatrix n minus 1 Choose k EndBinomialOrMatrix period

      The algebraic proof of this identity is an exercise in working with factorials.

StartLayout 1st Row 1st Column StartBinomialOrMatrix n minus 1 Choose k minus 1 EndBinomialOrMatrix plus StartBinomialOrMatrix n minus 1 Choose k EndBinomialOrMatrix 2nd Column equals StartFraction left-parenthesis n minus 1 right-parenthesis factorial Over left-parenthesis k minus 1 right-parenthesis factorial left-parenthesis n minus k right-parenthesis factorial EndFraction plus StartFraction left-parenthesis n minus 1 right-parenthesis factorial Over k factorial left-parenthesis n minus 1 minus k right-parenthesis factorial EndFraction 2nd Row 1st Column Blank 2nd Column equals StartFraction left-parenthesis n minus 1 right-parenthesis factorial k Over k factorial left-parenthesis n minus k right-parenthesis factorial EndFraction plus StartFraction left-parenthesis n minus k right-parenthesis left-parenthesis n minus 1 right-parenthesis factorial Over k factorial left-parenthesis n minus k right-parenthesis factorial EndFraction 3rd Row 1st Column Blank 2nd Column equals StartFraction left-parenthesis n minus 1 right-parenthesis factorial left-parenthesis k plus left-parenthesis n minus k right-parenthesis Over k factorial left-parenthesis n minus k right-parenthesis factorial EndFraction 4th Row 1st Column Blank 2nd Column equals StartFraction left-parenthesis n minus 1 right-parenthesis factorial n Over k factorial left-parenthesis n minus k right-parenthesis factorial EndFraction 5th Row 1st Column Blank 2nd Column equals StartFraction n factorial Over k factorial left-parenthesis n minus k right-parenthesis factorial EndFraction equals StartBinomialOrMatrix n Choose k EndBinomialOrMatrix period EndLayout

      Here is a combinatorial proof:

       Question: There are students in the room, including Addison. How many ways are there to pick a group of students?

       Answer #1: Choose students from the set of students in ways.

       Answer #2: Pick students that include Addison. Then pick students that do not include Addison. If Addison is included, there are ways to pick the remaining students in the group. If Addison is not included, there are ways to pick the group (choosing from everyone except Addison). Thus, there are ways to pick a group of students.

      The two solutions answer the same question, proving the desired identity.

       Example 1.28 Ballot problem. This classic problem introduced by Joseph Louis François Bertrand in 1887 asks, “In an election where candidate A receives votes and candidate B receives votes with , what is the probability that A will be strictly ahead of B throughout the count?” The problem assumes that votes for A and B are equally likely.For instance, if A receives votes and B receives votes, the possible vote counts are given in Table 1.5. Of the 10 possible voting outcomes, only the first two show A always ahead throughout the count. The desired probability is We show that the solution to the ballot problem is A voting outcome can be thought of as a list of length with As and Bs. Thus, there are possible voting outcomes.TABLE 1.5. Voting outcomes for the ballot problem.Net votes for AVoting patternduring the countAAABB1,2,3,2,1AABAB1,2,1,2,1AABBA1,2,1,0,1ABABA1,0,1,0,1ABAAB1,0,1,2,1ABBAA1,0,1,0,1BAAAB1,0,1,2,1BAABA1,0,1,0,1BABAA1,0,1,0,1BBAAA1,2,0,1,2A receives three votes and B receives two votes.FIGURE 1.4: Illustrating the correspondence between “bad” lists that start with A and lists that start with B.Consider the number of outcomes in which A is always ahead. Clearly, such an outcome must begin with a vote for A. The number of outcomes that begin with A is , because the first element of the list is fixed and there are positions to fill with A's. Some of these outcomes are “good” (A stays ahead throughout) and some are “bad”. We need to subtract off the number of “bad” lists.To count such lists, we give a one-to-one correspondence between “bad” lists that start with A and general lists that start with B. To do so, we represent a voting outcome by a path where the vertical axis represents the number of votes for A. Thus, when a path crosses the horizontal axis, it represents a tie.See the example in Figure 1.4. The left diagram corresponds to the voting outcome AABABBBAAA. The outcome is “bad” in that there is eventually a tie and the path crosses the horizontal axis. For such a path, “reflect” the portion of the path up until the tie across the axis, giving the outcome in the right diagram. The reflection results in a path that starts with B.Conversely, consider a path that starts with B. As