--- tags: mth225, dailyprep --- # Daily Prep 4.2 -- MTH 225 ## Overview Today's lesson is the first of a two-part look at the **binomial coefficient**. This is a number that plays a highly important role in combinatorics and computer science. We'll see that this number can be defined in three different ways, each of which conveys different information: * As a solution to a counting problem, namely the number of ways to select $k$ items from a set of $n$ items; * As a recursively defined function; and * As a closed formula involving the factorial function. In the first lesson, we'll be focusing on understanding all of these different ways of looking at the binomial coefficient, and why they are all equivalent ways of defining it. ## Learning objectives **Basic Learning Objectives:** *Before* our class meeting, use the Resources listed below to learn all of the following. You should be reasonably fluent with all of these tasks prior to our meeting; we will field questions on these, but they will not be retaught. * Define the binomial coefficient in terms of the solution to a counting problem. * State the recurrence relation that defines the binomial coefficient. **Advanced Learning Objectives:** *During and after* our class meeting, we will work on learning the following. Fluency with these is not required prior to class. * Derive and state a closed formula for $\binom{n}{k}$. * Compute values of the binomial coefficient using recursion, Pascal's Triangle, and the closed formula. * Explain why the three ways of defining the binomial coefficient are all equivalent. * Identify when the binomial coefficient can be used to solve a counting problem, and then use it to solve the problem. ## Resources for learning **Video:** Watch these videos. The first, second, and fourth were made for an earlier section of this course in Fall 2020; **these have no captions** so if you need closed-captioning, please let me know. The other two are on [the MTH 225 playlist](https://vimeo.com/showcase/8667148) (total running time 36:10). **UPDATED NOTE 2021-10-08:** There are **five (5) videos to watch** for this lesson. The **third** and **fifth** of these are embedded below. The **first, second, and fourth** are hosted on Panopto. However, as discussed on Campuswire, there were issues with some students not being able to play back the videos when embedded here on this document. So, I have **put them in a folder on Blackboard**. You can access it by going to *Blackboard > Daily Prep > Videos for Daily Prep 4.2*. **If you can see the videos in that folder but cannot play them back, do not contact me first -- contact the Blackboard help desk** at the number or email found in the syllabus. + Video 1: "Binomial coefficient video 1/Counting Subsets and Bitstrings" in the folder on Blackboard + Video 2: "Binomial coefficient video 2/Counting the k-element subsets of a set" in the folder on Blackboard + Video 3: Below. <iframe src="https://player.vimeo.com/video/618985119?h=e4f69b4a08" width="640" height="360" frameborder="0" allow="autoplay; fullscreen; picture-in-picture" allowfullscreen></iframe> + Video 4: "Binomial coefficient video 4/Why counting subsets and counting bit strings are the same" in the folder on Blackboard + Video 5: Below. <div style="padding:56.25% 0 0 0;position:relative;"><iframe src="https://player.vimeo.com/video/621554165?h=1c5061a980&amp;badge=0&amp;autopause=0&amp;player_id=0&amp;app_id=58479" frameborder="0" allow="autoplay; fullscreen; picture-in-picture" allowfullscreen style="position:absolute;top:0;left:0;width:100%;height:100%;" title="Screencast 4.7: The Binomial Coefficient"></iframe></div><script src="https://player.vimeo.com/api/player.js"></script> **Text:** [Section 1.2 in the text](http://discrete.openmathbooks.org/dmoi3/sec_counting-binom.html) deals with this content. You are free to search for and use other resources in addition to, or instead of the above, as long as you can work the exercises below. **Python:** Python has the binomial coefficient built in, but it's not part of the standard library. Instead, you have to first import the `scipy` (Scientific Python) module, specifically the `special` module for special CS functions. Then, the function is called `binom`. To import the module, you must first enter `import scipy.special` and then the function is called by entering `scipy.special.binom(a,b)` if you want to compute $\binom{a}{b}$. Here's an example of use, calculating $\binom{5}{2}$: ```python= import scipy.special scipy.special.binom(5,2) ``` This returns `10.0` --- notice it's a floating point number, not an integer. And here's a alternate, homemade version of this function that you can use instead if you want --- just cut and paste the code into your Python environment then execute it. It avoids having to load a library, uses recursion (specifically the recurrence relation stressed in the videos), and returns an integer, not a float. But, it's *super slow* for large values due to the recursion. ```python= # Alternative formulation of the binomial coefficient. # Uses recursion, and returns an integer. # BUT: It's VERY SLOW for large values of n and k. # The regular version in the scipy library is WAY faster. def binom(n,k): if k == 0: return 1 if n == k: return 1 else: return binom(n-1,k) + binom(n-1, k-1) ``` ## Exercises Once you have watched the videos above, go to this form and complete all the non-optional items on it: https://docs.google.com/forms/d/e/1FAIpQLSeSahhFTDDEqKnBPXDY0Zfs_yRFchuibodaiN80V1UUKTzo6w/viewform ## Submission and grading **Submitting your work:** Your work is submitted when you submit the Google Form. You should receive an email receipt indicating that the work was submitted successfully. **How this is graded:** The pre-class portion of the Daily Prep is graded either 0 points or 1 point, on the basis of completeness and effort. Wrong answers are not penalized. Earning a "1" requires that you: - Turn the work in before its deadline; - Leave no item blank or skipped, even accidentally; and - Give a good-faith effort at a correct answer on every non-optional item. More information can be found in the [Specifications for Satisfactory Work in MTH 225](/Cy6P0rGZQzuOM3NwZ3ZuMw) document. When you arrive for the class meeting, you'll be put into a group of 2-3 to complete a quiz over this material, which will be graded on a 0/1 scale on the basis of correctness.