rel="nofollow" href="#fb3_img_img_721de1c7-7109-5c57-82db-48bfe3da9e73.png" alt="k"/> of these factors to choose an Let
FIGURE 1.3: Pascal's triangle.
There is a combinatorial interpretation of this identity. The left-hand side counts the number of sets of size
Binomial coefficients appear in the famous Pascal's triangle, shown in Figure 1.3. Each entry of the triangle is the sum of the two numbers above it. The entries are all binomial coefficients. Enumerate the rows starting at
(1.5)
The algebraic proof of this identity is an exercise in working with factorials.
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
