#set document(title: "2.2 Binomial Coefficients", author: "OpenStax / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 2.2#h(0.6em)Binomial Coefficients #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ In chess, a rook can move only in straight lines (not diagonally). Fill in each square of the chess board below with the number of different shortest paths the rook, in the upper left corner, can take to get to that square. For example, one square is already filled in. There are six different paths from the rook to the square: DDRR (down down right right), DRDR, DRRD, RDDR, RDRD and RRDD. #figure(figph[An 8x8 checkerboard containing an image of a rook chess piece in the top left corner. The square in the third row, third column contains the number 6.], alt: "An 8x8 checkerboard containing an image of a rook chess piece in the top left corner. The square in the third row, third column contains the number 6.", caption: none) ] Here are some apparently different discrete objects we can count: subsets, bit strings, lattice paths, and binomial coefficients. We will give an example of each type of counting problem (and say what these things even are). As we will see, these counting problems are surprisingly similar. === Subsets Subsets should be familiar, otherwise read over Sets again. Suppose we look at the set #math.equation(block: false, alt: "A equals open brace 1 , 2 , 3 , 4 , 5 close brace")[$A = \{ 1 , 2 , 3 , 4 , 5 \}$]. How many subsets of #math.equation(block: false, alt: "A")[$A$] contain exactly 3 elements? First, a simpler question: How many subsets of #math.equation(block: false, alt: "A")[$A$] are there total? In other words, what is #math.equation(block: false, alt: "vertical bar P open parenthesis A close parenthesis vertical bar")[$| P ( A ) |$] (the cardinality of the power set of #math.equation(block: false, alt: "A")[$A$])? Think about how we would build a subset. We need to decide, for each of the elements of #math.equation(block: false, alt: "A")[$A$], whether or not to include the element in our subset. So we need to decide “yes” or “no” for the element 1. And for each choice we make, we need to decide “yes” or “no” for the element 2. And so on. For each of the 5 elements, we have 2 choices. Therefore the number of subsets is simply #math.equation(block: false, alt: "2 times 2 times 2 times 2 times 2 equals 2 to the power 5")[$2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 2^(5)$] (by the multiplicative principle). Of those 32 subsets, how many have 3 elements? This is not obvious. Note that we cannot just use the multiplicative principle. Maybe we want to say we have 2 choices (yes/no) for the first element, 2 choices for the second, 2 choices for the third, and then only 1 choice for the other two. But what if we said “no” to one of the first three elements? Then we would have two choices for the 4th element. What a mess! Another (bad) idea: we need to pick three elements to be in our subset. There are 5 elements to choose from. So there are 5 choices for the first element, and for each of those 4 choices for the second, and then 3 for the third (last) element. The multiplicative principle would say then that there are a total of #math.equation(block: false, alt: "5 times 4 times 3 equals 60")[$5 ⋅ 4 ⋅ 3 = 60$] ways to select the 3-element subset. But this cannot be correct (#math.equation(block: false, alt: "60 greater than 32")[$60 > 32$] for one thing). One of the outcomes we would get from these choices would be the set #math.equation(block: false, alt: "open brace 3 , 2 , 5 close brace")[$\{ 3 , 2 , 5 \}$], by choosing the element 3 first, then the element 2, then the element 5. Another outcome would be #math.equation(block: false, alt: "open brace 5 , 2 , 3 close brace")[$\{ 5 , 2 , 3 \}$] by choosing the element 5 first, then the element 2, then the element 3. But these are the same set! We can correct this by dividing: for each set of three elements, there are 6 outcomes counted among our 60 (since there are 3 choices for which element we list first, 2 for which we list second, and 1 for which we list last). So we expect there to be 10 3-element subsets of #math.equation(block: false, alt: "A")[$A$]. Is this right? Well, we could list out all 10 of them, being very systematic in doing so, to make sure we don't miss any or list any twice. Or we could try to count how many subsets of #math.equation(block: false, alt: "A")[$A$] #emph[don't] have 3 elements in them. How many have no elements? Just 1 (the empty set). How many have 5? Again, just 1. These are the cases in which we say “no” to all elements, or “yes” to all elements. Okay, what about the subsets which contain a single element? There are 5 of these. We must say “yes” to exactly one element, and there are 5 to choose from. This is also the number of subsets containing 4 elements. Those are the ones for which we must say “no” to exactly one element. So far we have counted 12 of the 32 subsets. We have not yet counted the subsets with cardinality 2 and with cardinality 3. There are a total of 20 subsets left to split up between these two groups. But the number of each must be the same! If we say “yes” to exactly two elements, that can be accomplished in exactly the same number of ways as the number of ways we can say “no” to exactly two elements. So the number of 2-element subsets is equal to the number of 3-element subsets. Together there are 20 of these subsets, so 10 each. #figure(table( columns: 7, align: left, inset: 6pt, table.header([Number of elements:], [0], [1], [2], [3], [4], [5]), [Number of subsets:], [1], [5], [10], [10], [5], [1], )) === Bit Strings “Bit” is short for “binary digit,” so a #strong[bit string] is a string of binary digits. The #strong[binary digits] are simply the numbers 0 and 1. All of the following are bit strings: #math.equation(block: true, alt: "1001011111010101010")[$1001 #h(1em) 0 #h(1em) 1111 #h(1em) 1010101010$] . The number of bits (0's or 1's) in the string is the #strong[length] of the string; the strings above have lengths 4, 1, 4, and 10 respectively. We also can ask how many of the bits are 1's. The number of 1's in a bit string is the #strong[weight] of the string; the weights of the above strings are 2, 0, 4, and 5 respectively. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Bit Strings] - An #strong[#math.equation(block: false, alt: "n")[$n$]-bit string] is a bit string of length #math.equation(block: false, alt: "n")[$n$]. That is, it is a string containing #math.equation(block: false, alt: "n")[$n$] symbols, each of which is a bit, either 0 or 1. - The #strong[weight] of a bit string is the number of 1's in it. - #math.equation(block: false, alt: "B to the power n")[$bold(B)^(n)$] is the #emph[set] of all #math.equation(block: false, alt: "n")[$n$]-bit strings. - #math.equation(block: false, alt: "B sub k to the power n")[$bold(B)_(k)^(n)$] is the set of all #math.equation(block: false, alt: "n")[$n$]-bit strings of weight #math.equation(block: false, alt: "k")[$k$]. ] For example, the elements of the set #math.equation(block: false, alt: "B sub 2 cubed")[$bold(B)_(2)^(3)$] are the bit strings 011, 101, and 110. Those are the only strings containing three bits exactly two of which are 1's. The counting questions: How many bit strings have length 5? How many of those have weight 3? In other words, we are asking for the cardinalities #math.equation(block: false, alt: "vertical bar B to the power 5 vertical bar")[$| bold(B)^(5) |$] and #math.equation(block: false, alt: "vertical bar B sub 3 to the power 5 vertical bar")[$| bold(B)_(3)^(5) |$]. To find the number of 5-bit strings is straight forward. We have 5 bits, and each can either be a 0 or a 1. So there are 2 choices for the first bit, 2 choices for the second, and so on. By the multiplicative principle, there are #math.equation(block: false, alt: "2 times 2 times 2 times 2 times 2 equals 2 to the power 5 equals 32")[$2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 = 2^(5) = 32$] such strings. Finding the number of 5-bit strings of weight 3 is harder. Think about how such a string could start. The first bit must be either a 0 or a 1. In the first case (the string starts with a 0), we must then decide on four more bits. To have a total of three 1's, among those four remaining bits there must be three 1's. To count all of these strings, we must include all 4-bit strings of weight 3. In the second case (the string starts with a 1), we still have four bits to choose, but now only two of them can be 1's, so we should look at all the 4-bit strings of weight 2. So the strings in #math.equation(block: false, alt: "B sub 3 to the power 5")[$bold(B)_(3)^(5)$] all have the form #math.equation(block: false, alt: "1 B sub 2 to the power 4")[$1 bold(B)_(2)^(4)$] (that is, a 1 followed by a string from #math.equation(block: false, alt: "B sub 2 to the power 4")[$bold(B)_(2)^(4)$]) or #math.equation(block: false, alt: "0 B sub 3 to the power 4")[$0 bold(B)_(3)^(4)$]. These two sets are disjoint, so we can use the additive principle: #math.equation(block: true, alt: "vertical bar B sub 3 to the power 5 vertical bar equals vertical bar B sub 2 to the power 4 vertical bar plus vertical bar B sub 3 to the power 4 vertical bar")[$| bold(B)_(3)^(5) | = | bold(B)_(2)^(4) | + | bold(B)_(3)^(4) |$] . This is an example of a #strong[recurrence relation]. We represented one instance of our counting problem in terms of two simpler instances of the problem. If only we knew the cardinalities of #math.equation(block: false, alt: "B sub 2 to the power 4")[$bold(B)_(2)^(4)$] and #math.equation(block: false, alt: "B sub 3 to the power 4")[$bold(B)_(3)^(4)$]. Repeating the same reasoning, #math.equation(block: true, alt: "vertical bar B sub 2 to the power 4 vertical bar equals vertical bar B sub 1 cubed vertical bar plus vertical bar B sub 2 cubed vertical bar and vertical bar B sub 3 to the power 4 vertical bar equals vertical bar B sub 2 cubed vertical bar plus vertical bar B sub 3 cubed vertical bar")[$| bold(B)_(2)^(4) | = | bold(B)_(1)^(3) | + | bold(B)_(2)^(3) | #h(1em) "and" #h(1em) | bold(B)_(3)^(4) | = | bold(B)_(2)^(3) | + | bold(B)_(3)^(3) |$] . We can keep going down, but this should be good enough. Both #math.equation(block: false, alt: "B sub 1 cubed")[$bold(B)_(1)^(3)$] and #math.equation(block: false, alt: "B sub 2 cubed")[$bold(B)_(2)^(3)$] contain 3 bit strings: we must pick one of the three bits to be a 1 (three ways to do that) or one of the three bits to be a 0 (three ways to do that). Also, #math.equation(block: false, alt: "B sub 3 cubed")[$bold(B)_(3)^(3)$] contains just one string: 111. Thus #math.equation(block: false, alt: "vertical bar B sub 2 to the power 4 vertical bar equals 6")[$| bold(B)_(2)^(4) | = 6$] and #math.equation(block: false, alt: "vertical bar B sub 3 to the power 4 vertical bar equals 4")[$| bold(B)_(3)^(4) | = 4$], which puts #math.equation(block: false, alt: "B sub 3 to the power 5")[$bold(B)_(3)^(5)$] at a total of 10 strings. But wait —32 and 10 were the answers to the counting questions about subsets. Coincidence? Not at all. Each bit string can be thought of as a #emph[code] for a subset. To represent the subsets of #math.equation(block: false, alt: "A equals open brace 1 , 2 , 3 , 4 , 5 close brace")[$A = \{ 1 , 2 , 3 , 4 , 5 \}$], we can use 5-bit strings, one bit for each element of #math.equation(block: false, alt: "A")[$A$]. Each bit in the string is a 0 if its corresponding element of #math.equation(block: false, alt: "A")[$A$] is not in the subset, and a 1 if the element of #math.equation(block: false, alt: "A")[$A$] is in the subset. Remember, deciding the subset amounted to a sequence of five yes/no votes for the elements of #math.equation(block: false, alt: "A")[$A$]. Instead of yes, we put a 1; instead of no, we put a 0. For example, the bit string #math.equation(block: false, alt: "11001")[$11001$] represents the subset #math.equation(block: false, alt: "open brace 1 , 2 , 5 close brace")[$\{ 1 , 2 , 5 \}$] since the first, second and fifth bits are 1's. The subset #math.equation(block: false, alt: "open brace 3 , 5 close brace")[$\{ 3 , 5 \}$] would be coded by the string #math.equation(block: false, alt: "00101")[$00101$]. What we really have here is a bijection from #math.equation(block: false, alt: "P open parenthesis A close parenthesis")[$P ( A )$] to #math.equation(block: false, alt: "B to the power 5")[$bold(B)^(5)$]. Now for a subset to contain exactly three elements, the corresponding bit string must contain exactly three 1's. In other words, the weight must be 3. Thus counting the number of 3-element subsets of #math.equation(block: false, alt: "A")[$A$] is the same as counting the number 5-bit strings of weight 3. === Lattice Paths The #strong[integer lattice] is the set of all points in the Cartesian plane for which both the #math.equation(block: false, alt: "x")[$x$] and #math.equation(block: false, alt: "y")[$y$] coordinates are integers. If you like to draw graphs on graph paper, the lattice is the set of all the intersections of the grid lines. A #strong[lattice path] is one of the shortest possible paths connecting two points on the lattice, moving only horizontally and vertically. For example, here are three possible lattice paths from the point #math.equation(block: false, alt: "open parenthesis 0 , 0 close parenthesis")[$( 0 , 0 )$] to #math.equation(block: false, alt: "open parenthesis 3 , 2 close parenthesis")[$( 3 , 2 )$]: #figure(figph[A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom left dot to the third dot on the bottom row, then turns up and runs to the top dot in that column, then turns right and runs to the top-right dot.], alt: "A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom left dot to the third dot on the bottom row, then turns up and runs to the top dot in that column, then turns right and runs to the top-right dot.", caption: none) #figure(figph[A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom up to the top left dot, and then to the top-right dot.], alt: "A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom up to the top left dot, and then to the top-right dot.", caption: none) #figure(figph[A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom left dot to the second dot on the bottom row, then turns up and runs to the next dot above it, then turns right and runs to the middle right dot, and finally turns up and runs to the top-right dot.], alt: "A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). A bold line runs from the bottom left dot to the second dot on the bottom row, then turns up and runs to the next dot above it, then turns right and runs to the middle right dot, and finally turns up and runs to the top-right dot.", caption: none) Notice to ensure the path is the #emph[shortest] possible, each move must be either to the right or up. Additionally, in this case, note that no matter what path we take, we must make three steps right and two steps up. No matter what order we make these steps, there will always be 5 steps. Thus each path has #emph[length] 5. The counting question: how many lattice paths are there between #math.equation(block: false, alt: "open parenthesis 0 , 0 close parenthesis")[$( 0 , 0 )$] and #math.equation(block: false, alt: "open parenthesis 3 , 2 close parenthesis")[$( 3 , 2 )$]? We could try to draw all of these, or instead of drawing them, maybe just list which direction we travel on each of the 5 steps. One path might be RRUUR, or maybe UURRR, or perhaps RURRU (those correspond to the three paths drawn above). So how many such strings of R's and U's are there? Notice that each of these strings must contain 5 symbols. Exactly 3 of them must be R's (since our destination is 3 units to the right). This seems awfully familiar. In fact, what if we used #math.equation(block: false, alt: "1")[$1$]'s instead of R's and 0's instead of U's? Then we would just have 5-bit strings of weight 3. There are 10 of those, so there are 10 lattice paths from (0,0) to (3,2). The correspondence between bit strings and lattice paths does not stop there. Here is another way to count lattice paths. Consider the lattice shown below: #figure(figph[A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). The dot on the top row directly to the left of (3,2) is labeled A; the dot directly below (3,2) is labeled B.], alt: "A grid of 12 dots arranged in a 4-wide by 3-high rectangle. The lower-left dot is labeled (0,0). The top right dot is labeled (3,2). The dot on the top row directly to the left of (3,2) is labeled A; the dot directly below (3,2) is labeled B.", caption: none) Any lattice path from (0,0) to (3,2) must pass through exactly one of #math.equation(block: false, alt: "A")[$A$] and #math.equation(block: false, alt: "B")[$B$]. The point #math.equation(block: false, alt: "A")[$A$] is 4 steps away from (0,0) and two of them are towards the right. The number of lattice paths to #math.equation(block: false, alt: "A")[$A$] is the same as the number of 4-bit strings of weight 2, namely 6. The point #math.equation(block: false, alt: "B")[$B$] is 4 steps away from (0,0), but now 3 of them are towards the right. So the number of paths to point #math.equation(block: false, alt: "B")[$B$] is the same as the number of 4-bit strings of weight 3, namely 4. So the total number of paths to (3,2) is just #math.equation(block: false, alt: "6 plus 4")[$6 + 4$]. This is the same way we calculated the number of 5-bit strings of weight 3. The point: the exact same recurrence relation exists for bit strings and for lattice paths. === Binomial Coefficients #strong[Binomial coefficients] are the coefficients in the expanded version of a binomial, such as #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis to the power 5")[$( x + y )^(5)$]. What happens when we multiply such a binomial out? We will expand #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis to the power n")[$( x + y )^(n)$] for various values of #math.equation(block: false, alt: "n")[$n$]. Each of these are done by multiplying everything out (i.e., FOIL-ing) and then collecting like terms. #math.equation(block: true, alt: "open parenthesis x plus y close parenthesis to the power 1 equals x plus y")[$( x + y )^(1) = x + y$] #math.equation(block: true, alt: "open parenthesis x plus y close parenthesis squared equals x squared plus 2 x y plus y squared")[$( x + y )^(2) = x^(2) + 2 x y + y^(2)$] #math.equation(block: true, alt: "open parenthesis x plus y close parenthesis cubed equals x cubed plus 3 x squared y plus 3 x y squared plus y cubed")[$( x + y )^(3) = x^(3) + 3 x^(2) y + 3 x y^(2) + y^(3)$] #math.equation(block: true, alt: "open parenthesis x plus y close parenthesis to the power 4 equals x to the power 4 plus 4 x cubed y plus 6 x squared y squared plus 4 x y cubed plus y to the power 4")[$( x + y )^(4) = x^(4) + 4 x^(3) y + 6 x^(2) y^(2) + 4 x y^(3) + y^(4)$] . In fact, there is a quicker way to expand the above binomials. For example, consider the next one, #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis to the power 5")[$( x + y )^(5)$]. What we are really doing is multiplying out, #math.equation(block: true, alt: "open parenthesis x plus y close parenthesis open parenthesis x plus y close parenthesis open parenthesis x plus y close parenthesis open parenthesis x plus y close parenthesis open parenthesis x plus y close parenthesis")[$( x + y ) ( x + y ) ( x + y ) ( x + y ) ( x + y )$] . If that looks daunting, go back to the case of #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis cubed equals open parenthesis x plus y close parenthesis open parenthesis x plus y close parenthesis open parenthesis x plus y close parenthesis")[$( x + y )^(3) = ( x + y ) ( x + y ) ( x + y )$]. Why do we only have one #math.equation(block: false, alt: "x cubed")[$x^(3)$] and #math.equation(block: false, alt: "y cubed")[$y^(3)$] but three #math.equation(block: false, alt: "x squared y")[$x^(2) y$] and #math.equation(block: false, alt: "x y squared")[$x y^(2)$] terms? Every time we distribute over an #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis")[$( x + y )$] we create two copies of what is left, one multiplied by #math.equation(block: false, alt: "x")[$x$], the other multiplied by #math.equation(block: false, alt: "y")[$y$]. To get #math.equation(block: false, alt: "x cubed")[$x^(3)$], we need to pick the “multiplied by #math.equation(block: false, alt: "x")[$x$]” side every time (we don't have any #math.equation(block: false, alt: "y")[$y$]'s in the term). This will only happen once. On the other hand, to get #math.equation(block: false, alt: "x squared y")[$x^(2) y$] we need to select the #math.equation(block: false, alt: "x")[$x$] side twice and the #math.equation(block: false, alt: "y")[$y$] side once. In other words, we need to pick one of the three #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis")[$( x + y )$] terms to “contribute” their #math.equation(block: false, alt: "y")[$y$]. Similarly, in the expansion of #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis to the power 5")[$( x + y )^(5)$], there will be only one #math.equation(block: false, alt: "x to the power 5")[$x^(5)$] term and one #math.equation(block: false, alt: "y to the power 5")[$y^(5)$] term. This is because to get an #math.equation(block: false, alt: "x to the power 5")[$x^(5)$], we need to use the #math.equation(block: false, alt: "x")[$x$] term in each of the copies of the binomial #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis")[$( x + y )$], and similarly for #math.equation(block: false, alt: "y to the power 5")[$y^(5)$]. What about #math.equation(block: false, alt: "x to the power 4 y")[$x^(4) y$]? To get terms like this, we need to use four #math.equation(block: false, alt: "x")[$x$]'s and one #math.equation(block: false, alt: "y")[$y$], so we need exactly one of the five binomials to contribute a #math.equation(block: false, alt: "y")[$y$]. There are 5 choices for this, so there are 5 ways to get #math.equation(block: false, alt: "x to the power 4 y")[$x^(4) y$], so the coefficient of #math.equation(block: false, alt: "x to the power 4 y")[$x^(4) y$] is 5. This is also the coefficient for #math.equation(block: false, alt: "x y to the power 4")[$x y^(4)$] for the same (but opposite) reason: there are 5 ways to pick which of the 5 binomials contribute the single #math.equation(block: false, alt: "x")[$x$]. So far we have #math.equation(block: true, alt: "open parenthesis x plus y close parenthesis to the power 5 equals x to the power 5 plus 5 x to the power 4 y plus ? bar x cubed y squared plus ? bar x squared y cubed plus 5 x y to the power 4 plus y to the power 5")[$( x + y )^(5) = x^(5) + 5 x^(4) y + underline(" " ? " ") " " x^(3) y^(2) + underline(" " ? " ") " " x^(2) y^(3) + 5 x y^(4) + y^(5)$] . We still need the coefficients of #math.equation(block: false, alt: "x cubed y squared")[$x^(3) y^(2)$] and #math.equation(block: false, alt: "x squared y cubed")[$x^(2) y^(3)$]. In both cases, we need to pick exactly 3 of the 5 binomials to contribute one variable, the other two to contribute the other. Wait. This sounds familiar. We have 5 things, each can be one of two things, and we need a total of 3 of one of them. That's just like taking 5 bits and making sure exactly 3 of them are 1's. So the coefficient of #math.equation(block: false, alt: "x cubed y squared")[$x^(3) y^(2)$] (and also #math.equation(block: false, alt: "x squared y cubed")[$x^(2) y^(3)$]) will be exactly the same as the number of bit strings of length 5 and weight 3, which we found earlier to be 10. So we have: #math.equation(block: true, alt: "open parenthesis x plus y close parenthesis to the power 5 equals x to the power 5 plus 5 x to the power 4 y plus 10 x cubed y squared plus 10 x squared y cubed plus 5 x y to the power 4 plus y to the power 5")[$( x + y )^(5) = x^(5) + 5 x^(4) y + 10 x^(3) y^(2) + 10 x^(2) y^(3) + 5 x y^(4) + y^(5)$] . These numbers we keep seeing over and over again. They are the number of subsets of a particular size, the number of bit strings of a particular weight, the number of lattice paths, and the coefficients of these binomial products. We will call them #strong[binomial coefficients]. We even have a special symbol for them: #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$]. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Binomial Coefficients] For each integer #math.equation(block: false, alt: "n greater than or equal to 0")[$n ≥ 0$] and integer #math.equation(block: false, alt: "k")[$k$] with #math.equation(block: false, alt: "0 less than or equal to k less than or equal to n")[$0 ≤ k ≤ n$] there is a number #math.equation(block: true, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$] , read “#math.equation(block: false, alt: "n")[$n$] choose #math.equation(block: false, alt: "k")[$k$].” We have: - #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis equals vertical bar B sub k to the power n vertical bar")[$( binom(n, k) ) = | bold(B)_(k)^(n) |$], the number of #math.equation(block: false, alt: "n")[$n$]-bit strings of weight #math.equation(block: false, alt: "k")[$k$]. - #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$] is the number of subsets of a set of size #math.equation(block: false, alt: "n")[$n$] each with cardinality #math.equation(block: false, alt: "k")[$k$]. - #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$] is the number of lattice paths of length #math.equation(block: false, alt: "n")[$n$] containing #math.equation(block: false, alt: "k")[$k$] steps to the right. - #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$] is the coefficient of #math.equation(block: false, alt: "x to the power k y to the power n minus k")[$x^(k) y^(n − k)$] in the expansion of #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis to the power n")[$( x + y )^(n)$]. - #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$] is the number of ways to select #math.equation(block: false, alt: "k")[$k$] objects from a total of #math.equation(block: false, alt: "n")[$n$] objects. ] The last bullet point is usually taken as the definition of #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$]. Out of #math.equation(block: false, alt: "n")[$n$] objects we must choose #math.equation(block: false, alt: "k")[$k$] of them, so there are #math.equation(block: false, alt: "n")[$n$] choose #math.equation(block: false, alt: "k")[$k$] ways of doing this. Each of our counting problems above can be viewed in this way: - How many subsets of #math.equation(block: false, alt: "open brace 1 , 2 , 3 , 4 , 5 close brace")[$\{ 1 , 2 , 3 , 4 , 5 \}$] contain exactly 3 elements? We must choose #math.equation(block: false, alt: "3")[$3$] of the 5 elements to be in our subset. There are #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$] ways to do this, so there are #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$] such subsets. - How many bit strings have length 5 and weight 3? We must choose #math.equation(block: false, alt: "3")[$3$] of the 5 bits to be 1's. There are #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$] ways to do this, so there are #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$] such bit strings. - How many lattice paths are there from (0,0) to (3,2)? We must choose 3 of the 5 steps to be towards the right. There are #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$] ways to do this, so there are #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$] such lattice paths. - What is the coefficient of #math.equation(block: false, alt: "x cubed y squared")[$x^(3) y^(2)$] in the expansion of #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis to the power 5")[$( x + y )^(5)$]? We must choose 3 of the 5 copies of the binomial to contribute an #math.equation(block: false, alt: "x")[$x$]. There are #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$] ways to do this, so the coefficient is #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$]. It should be clear that in each case above, we have the right answer. All we had to do is phrase the question correctly and it became obvious that #math.equation(block: false, alt: "open parenthesis the fraction 5 over 3 close parenthesis")[$( binom(5, 3) )$] is correct. However, this does not tell us that the answer is in fact 10 in each case. We will eventually find a formula for #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$], but for now, look back at how we arrived at the answer 10 in our counting problems above. It all came down to bit strings, and we have a recurrence relation for bit strings: #math.equation(block: true, alt: "vertical bar B sub k to the power n vertical bar equals vertical bar B sub k minus 1 to the power n minus 1 vertical bar plus vertical bar B sub k to the power n minus 1 vertical bar")[$| bold(B)_(k)^(n) | = | bold(B)_(k − 1)^(n − 1) | + | bold(B)_(k)^(n − 1) |$] . Remember, this is because we can start the bit string with either a 1 or a 0. In both cases, we have #math.equation(block: false, alt: "n minus 1")[$n − 1$] more bits to pick. The strings starting with 1 must contain #math.equation(block: false, alt: "k minus 1")[$k − 1$] more 1's, while the strings starting with 0 still need #math.equation(block: false, alt: "k")[$k$] more 1's. Since #math.equation(block: false, alt: "vertical bar B sub k to the power n vertical bar equals open parenthesis the fraction n over k close parenthesis")[$| bold(B)_(k)^(n) | = ( binom(n, k) )$], the same recurrence relation holds for binomial coefficients: #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Recurrence relation for #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$]] #math.equation(block: true, alt: "open parenthesis the fraction n over k close parenthesis equals open parenthesis the fraction n minus 1 over k minus 1 close parenthesis plus open parenthesis the fraction n minus 1 over k close parenthesis")[$( binom(n, k) ) = ( binom(n − 1, k − 1) ) + ( binom(n − 1, k) )$] . ] === Pascal's Triangle Let's arrange the binomial coefficients #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$] into a triangle like follows: #figure(figph[Triangular array of binomial coefficients. Each lower row extends equally on both sides beyond the row above. Top row contains 0 choose 0. Second row contains 1 choose 0 and 1 choose 1 (from left to right). Third row contains 2 choose 0, 2 choose 1, and 2 choose 2. Below that the row contains 3 choose 0, 3 choose 1, 3 choose 2, and 3 choose 3. The bottom row contains 4 choose 0 through 4 choose 4.], alt: "Triangular array of binomial coefficients. Each lower row extends equally on both sides beyond the row above. Top row contains 0 choose 0. Second row contains 1 choose 0 and 1 choose 1 (from left to right). Third row contains 2 choose 0, 2 choose 1, and 2 choose 2. Below that the row contains 3 choose 0, 3 choose 1, 3 choose 2, and 3 choose 3. The bottom row contains 4 choose 0 through 4 choose 4.", caption: none) This can continue as far down as we like. The recurrence relation for #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$] tells us that each entry in the triangle is the sum of the two entries above it. The entries on the sides of the triangle are always 1. This is because #math.equation(block: false, alt: "open parenthesis the fraction n over 0 close parenthesis equals 1")[$( binom(n, 0) ) = 1$] for all #math.equation(block: false, alt: "n")[$n$] since there is only one way to pick 0 of #math.equation(block: false, alt: "n")[$n$] objects and #math.equation(block: false, alt: "open parenthesis the fraction n over n close parenthesis equals 1")[$( binom(n, n) ) = 1$] since there is one way to select all #math.equation(block: false, alt: "n")[$n$] out of #math.equation(block: false, alt: "n")[$n$] objects. Using the recurrence relation, and the fact that the sides of the triangle are 1's, we can easily replace all the entries above with the correct values of #math.equation(block: false, alt: "open parenthesis the fraction n over k close parenthesis")[$( binom(n, k) )$]. Doing so gives us #strong[Pascal's triangle]. We can use Pascal's triangle to calculate binomial coefficients. For example, using the triangle below, we can find #math.equation(block: false, alt: "open parenthesis the fraction 12 over 6 close parenthesis equals 924")[$( binom(12, 6) ) = 924$]. #figure(figph[The first 17 rows of Pascal's Triangle. A triangular array of hexagons, each row containing one more hexagon that the row above it. In each hexagon is an integer: 1's on the border of the triangle, and every integer inside the triangle the sum of the two integers above it.], alt: "The first 17 rows of Pascal's Triangle. A triangular array of hexagons, each row containing one more hexagon that the row above it. In each hexagon is an integer: 1's on the border of the triangle, and every integer inside the triangle the sum of the two integers above it.", caption: none) Explain why the coefficient of #math.equation(block: false, alt: "x to the power 5 y cubed")[$x^(5) y^(3)$] the same as the coefficient of #math.equation(block: false, alt: "x cubed y to the power 5")[$x^(3) y^(5)$] in the expansion of #math.equation(block: false, alt: "open parenthesis x plus y close parenthesis to the power 8")[$( x + y )^(8)$]?