Falling Factorial

Definition of Combination:
\displaystyle \boxed {  {_n}C_k = \frac {n!}{k!(n-k)!}  = \binom{n}{k}  }

Example:
\displaystyle  {_5}C_3 = \frac {5!}{3!(5-3)!}  = \frac {5!}{3!2!}  = \frac {5.4.3.2.1}{3.2.1.2.1}  = \frac {5.4.3}{3.2.1}  = \binom{5}{3}

Combinations are even simpler to write with ‘Falling Factorial’ x^{\underline {n}}

\boxed {  x^{\underline {n}} = \underbrace {(x-0)(x-1)(x-2)... (x-(n-1))}_{n factors}  }

Example:
5^{\underline {5}} = \underbrace {(5-0)(5-1)(5-2)... (5-(5-1))}_{5 \: factors} = 5.4.3.2.1= 5!
\boxed {  n^{\underline {n}} = n!    }

(2n)^{\underline {n+1}}  = \underbrace {(2n). (2n-1). (2n-2).... (2n-(n-1)).(2n-(n))}_{(n+1) \: terms}

(2n)^{\underline {n+1}}  = \underbrace {(2n). (2n-1). (2n-2).... (n+1)}_{(n)\: terms}.(n)

\boxed {  (2n)^{\underline {n+1}}  = (2n)^{\underline {n}}.(n)    }

\displaystyle  \binom{n}{k}  = \frac {n!}{k!(n-k)!}  = \frac {(n-0).(n-1)... (n-(k-1))}  { (k-0).(k-1)... (k-(k-1)) }  = \frac { n^{\underline {k}}}  {k^{\underline {k}}}

\displaystyle \boxed {  \binom{n}{k}  = \frac { n^{\underline {k}}}  {k^{\underline {k}}}   }

\text {Prove:} \binom {2n}{n} - \binom {2n}{n+1} =  \frac {1}{n+1} \binom {2n}{n}

\text {Proof:}

\binom {2n}{n} - \binom {2n}{n+1}  = \frac  {(2n)^{\underline {n}}}  {n^{\underline {n}}}  - \frac  {(2n)^{\underline {n+1}}}  {(n+1)^{\underline {n+1}}}

= \frac  {(2n)^{\underline {n}}}  {n^{\underline {n}}}  - \frac  {(2n)^{\underline {n}}(n)}  {(n+1)!}

= \frac  {(2n)^{\underline {n}}}  {n^{\underline {n}}}  - \frac  {(2n)^{\underline {n}}(n)}  {(n+1).(n)^{\underline {n}} }  [since (n+1)! = (n+1).n! ]

= \frac  {(n+1).(2n)^{\underline {n}}  - (2n)^{\underline {n}}(n)  }  {(n+1).(n)^{\underline {n}} }

= \frac  {(n+1-n).(2n)^{\underline {n}}  }  {(n+1).(n)^{\underline {n}} }

= \frac {1}{n+1}  \frac  {(2n)^{\underline {n}}}  {(n)^{\underline {n}} }

\boxed{  \binom {2n}{n} - \binom {2n}{n+1} = \frac {1}{n+1} \binom {2n}{n}    }

Ref: “The Math Girls

Advertisements

One thought on “Falling Factorial

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s