Description
Objective: To learn how to utilize basic recursion for a certain relation.
Description: You are to implement a program that calculates a given Binomial Coefficient. This is defined by the following formula:
𝑛 𝑛!
( ) =
𝑘 𝑘! (𝑛 − 𝑘)!
Where “!” represents a factorial, which is defined as such:
𝑛! = 𝑛 ∗ (𝑛 − 1) ∗ (𝑛 − 2) ∗ (𝑛 − (𝑛 − 1))
Ex: 5! = 5 * 4 * 3 * 2 * 1 = 120 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
0! = 1 (by the definition of factorial)
WARNING: LOTS OF MATH ON PAGE!
DO NOT PANIC! It is JUST to explain where this comes from Feel free to skip this page if you do not care.
That said, it may help you understand the assignment better…
How is this useful in any way, shape, or form? Well, let us take a look at the following binomial:
(𝑥+𝑦)3
What if we want to expand this out? Well, we could either just do it the old-fashioned way, or…
3 3 3 3
( ) 𝑥3𝑦0 + ( ) 𝑥2𝑦1 + ( ) 𝑥1𝑦2 + ( ) 𝑥0𝑦3
0 1 2 3
↓ ↓ ↓ ↓
!!!
↓ ↓ ↓ ↓
| ↓ | ↓ | ↓ | ↓ |
1𝑥3𝑦0 + 3𝑥2𝑦1 + 3𝑥1𝑦2 + 1𝑥0𝑦3
This is why this relation is called a Binomial Coefficient, as it determines the coefficient of a certain binomial. This is useful for big coefficients (like (x+y)^50)
TRIVIA: Notice how each Binomial Coefficient’s inverse Binomial Coefficient was exactly the same as itself? See: (31) was equal to (32). This is always true, no matter what.
READ THIS PAGE!
Function: What you will be programming is a single function that takes two inputs, n and k, and 𝑛
finds the Binomial Coefficient of ( ). While this technically can be done without recursion, 𝑘
it is highly, HIGHLY recommended you use recursion for this.
IMPORTANT: You will need to be aware of the base cases of this relationship.
HINT: On the previous page (if you read it), notice how the coefficient was equal to 1 when k was either equal to 0 or equal to n?
HINT 2: There are two base cases, both of which are based on the value of k.
HINT 3: Reread the above two hints, it literally tells you what the two base cases are.
The function is defined as such:
def Binomial_Coefficient(n, k): #(Please spell this right)
# code goes here
Oh yeah, one more thing…
READ THIS PAGE!
PASCALS IDENTITY: Given n objects, how many ways can we pick k of them?
For all of k and n when 1≤𝑘<𝑛
𝑛 𝑛 − 1 𝑛 − 1
( ) = ( ) + ( )
𝑘 𝑘 − 1 𝑘
𝑛
REMEMBER: Your Binomial_Coefficient function is essentially (𝑘) in code form. Think
about how Pascals Identity can be applied via recursive calls. Also, don’t forget the BASE CASES mentioned on the previous page!
That’s all folks, get to it.
