Factorials

• Sep 2nd 2008, 03:21 AM
Number Cruncher 20
Factorials
Hi,

Does anyone know whether it is possible to simplify a factorial as follows:

$\displaystyle {n\choose i}{n-m\choose i-m}$

= (n-m)! / ((i-m)!(n-m-i-m)!)
=(n-m)!/((i-m)!(n-i)!)
=(n-m)!/(i-m+n-i)!
=(n-m)!/(n-m)!
=1
• Sep 2nd 2008, 03:57 AM
flyingsquirrel
Hello,
Quote:

Originally Posted by Number Cruncher 20
Does anyone know whether it is possible to simplify a factorial as follows:

$\displaystyle {n\choose i}{n-m\choose i-m}$

= (n-m)! / ((i-m)!(n-m-i-m)!)

No... your forgot $\displaystyle \tbinom{n}{i}=\tfrac{n!}{i!(n-i)!}$. We have

\displaystyle \begin{aligned} {n\choose i}{n-m\choose i-m}&=\frac{n!}{i!(n-i)!}\cdot \frac{(n-m)!}{(i-m)![n-m-(i-m)]!}\\&=\frac{n!}{i!(n-i)!}\cdot \frac{(n-m)!}{(i-m)!(n-i)!}\\&= \frac{(n-m)!n!}{i!(i-m)!(n-i)!^2}\end{aligned}

and it seems this can't be further simplified. If you were asked to simplify $\displaystyle \tbinom{n}{m}\tbinom{n-m}{i-m}$ then we could derive the equality $\displaystyle \tbinom{n}{m}\tbinom{n-m}{i-m}=\tbinom{n}{i}\tbinom{i}{m}$ but that's not what you're asked to do, is it?
• Sep 2nd 2008, 04:16 AM
Number Cruncher 20
no, what ive been asked is to derive a closed formed expression for

(a) s = http://www.mathhelpforum.com/math-he...488598ba-1.gif for n= 0,1,2,....

(b) t = http://www.mathhelpforum.com/math-he...27c930f6-1.gif for n=0,1,2, .. and m = 0,1,2,...n

ive done the first part and showed that its equal to 1 when n = 0 and 0 when n not equal to 0. for the second part ive been given a hint that

http://www.mathhelpforum.com/math-he...fb3cf705-1.gif for http://www.mathhelpforum.com/math-he...195e4ccc-1.gif.

and to use this and part a to find a closed form expression for (b). i get the part a and the hint but i just dont see how to go from there to solving part b.
• Sep 2nd 2008, 04:57 AM
flyingsquirrel
Quote:

Originally Posted by Number Cruncher 20
and to use this and part a to find a closed form expression for (b). i get the part a and the hint but i just dont see how to go from there to solving part b.

We have

$\displaystyle t=\sum_{i=m}^n(-1)^i\binom{n}{i}\binom{i}{m}=\sum_{i=m}^n(-1)^i\binom{n}{m}\binom{n-m}{i-m}$

since we are told that $\displaystyle \tbinom{n}{i}\tbinom{i}{m}=\tbinom{n}{m}\tbinom{n-m}{i-m}$. As $\displaystyle \tbinom{n}{m}$ doesn't depend on $\displaystyle i$ we can factor this term to get

$\displaystyle t=\binom{n}{m}\sum_{i=m}^n(-1)^i\binom{n-m}{i-m}$.

Using the result of question (a), can you find a closed formed expression for $\displaystyle \sum_{i=m}^n(-1)^i\binom{n-m}{i-m}$ and thus for $\displaystyle t$ ?

Hint (highlight to read) : * change the index of summation to j = i-m *
• Sep 2nd 2008, 05:43 AM
Number Cruncher 20
I havent done summations for a while. Have i changed the variables properly so that we get:

$\displaystyle \binom{n}{m}\sum_{j=o}^n(-1)^(j+m)\binom{n-m}{j}$
• Sep 2nd 2008, 05:55 AM
flyingsquirrel
Quote:

Originally Posted by Number Cruncher 20
I havent done summations for a while. Have i changed the variables properly so that we get:

$\displaystyle \binom{n}{m}\sum_{j=o}^n(-1)^(j+m)\binom{n-m}{j}$

That's almost it, there is only a little mistake : for $\displaystyle i=n,\,j=n-m$ so

$\displaystyle t=\binom{n}{m}\sum_{j=0}^{{\color{blue}n-m}}(-1)^{j+m}\binom{n-m}{j}$.

Factoring $\displaystyle (-1)^m$ we get

$\displaystyle t=(-1)^m\binom{n}{m}\sum_{j=0}^{n-m}(-1)^j\binom{n-m}{j}$

and now you can use the answer to the first question to conclude.
• Sep 2nd 2008, 06:06 AM
Number Cruncher 20
Thank you for your help its really appreciated.
• Sep 2nd 2008, 06:29 AM
Number Cruncher 20
One last thing, but should the sum read:

(-1)^(j+2m) or is it right as (-1)^(j+m)
• Sep 2nd 2008, 06:39 AM
flyingsquirrel
Quote:

Originally Posted by Number Cruncher 20
One last thing, but should the sum read:

(-1)^(j+2m) or is it right as (-1)^(j+m)

If you're talking about the following sum
Quote:

Originally Posted by flyingsquirrel
$\displaystyle t=\binom{n}{m}\sum_{j=0}^{{\color{blue}n-m}}(-1)^{j+m}\binom{n-m}{j}$

then it is right as $\displaystyle (-1)^{j+m}$ since this term comes from $\displaystyle (-1)^{i}$ where we've substituted $\displaystyle i=j+m$. Why do you think it should be $\displaystyle (-1)^{j+2m}$ ?
• Sep 2nd 2008, 06:47 AM
Number Cruncher 20
sorry my bad i forgot the restrictions on the range of n and m so i thought it had to be $\displaystyle (-1)^{2m}$ for it to be 1.

Thanks again
• Sep 2nd 2008, 06:52 AM
Number Cruncher 20
what i meant is that you get
$\displaystyle (-1)^{m} \binom{n}{m} (0)^{n-m}$

and when n=m

if m and n are odd then t = -1 and when m and n are even then t is 1

is that the right answer.