## 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: ^{(}^{3}_{1}) was equal to ^{(}^{3}_{2}). 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.